Максимизировать высоту дерева, минимизируя количество детей любого узла?

Question

В настоящее время я столкнулся со следующей проблемой:

Дано дерево с неизменяемым корневым узлом и n дочерними элементами.Мне нужно оптимизировать это дерево таким образом, чтобы:

1. Количество дочерних элементов любого узла было минимальным (речь идет только о прямых дочерних узлах узла, а не об их дочерних элементах и ​​т. П.)
2. В результате этого высота дерева максимизируется
3. Дерево убывает по порядку, так что всегда узел> дочерний

Все узлы являются <корневым узлом.Тем не менее, иногда узел является только <корневым узлом и ни <, ни> другим узлом.

Любые идеи, советы и тому подобное будут приняты с благодарностью.

Спасибо.

Answer 1

Я согласен с Алексеем, я думаю, что вы хотите сделать, это связанный список с пользовательской функцией вставки, которая вставляет элементы в определенном порядке. Это было основано на вашем вопросе.

Теперь я не знаю, что именно вы пытаетесь сделать здесь, но если цель состоит в том, чтобы сохранить эффективную отсортированную коллекцию объектов, я бы предположил использовать Двоичное дерево поиска . Пройдя по этому дереву по порядку, будет очень легко и вернуть отсортированный список предметов. Вставки и удаления тоже довольно просты и имеют среднюю сложность O (log n).

Answer 2

Из вашего описания это звучит так, как будто вы просто хотите: (1) отсортировать узлы в порядке убывания, затем (2) сделать каждый узел дочерним по отношению к своему предшественнику, если его значение строго меньше, чем у предшественника, ибрат или сестра его предшественника в противном случае.Таким образом, высота дерева - это просто число различных значений, которое является самым большим, которое может быть дано вашему третьему условию.

Я не могу не подозревать, что вы хотите чего-то более сложного.Я что-то упускаю из виду?