Дайте асимптотическую верхнюю границу для высоты дерева двоичного поиска с n-узлами, в котором средняя глубина узла равна Θ (lg n)

Question

В последнее время я пытаюсь решить все упражнения в CLRS. но есть некоторые из них, я не могу понять. Вот один из них, из упражнения CLRS 12.4-2:

Опишите бинарное дерево поиска на n узлах так, чтобы средняя глубина узла в дереве была Θ (lg n), а высота дерева была ω (lg n). Дайте асимптотическую верхнюю границу для высоты дерева двоичного поиска с n-узлами, в котором средняя глубина узла равна Θ (lg n).

Может кто-нибудь поделиться некоторыми идеями или ссылками для решения этой проблемы? Спасибо.

Answer 1

Итак, давайте предположим, что мы строим дерево следующим образом: учитывая n узлов, возьмем f (n) узлов и отложим их в сторону. Затем создайте дерево, построив идеальное двоичное дерево, в котором корень имеет левое поддерево, представляющее собой идеальное двоичное дерево из n - f (n) - 1 узлов, и правое поддерево, представляющее собой цепочку длиной f (n). Мы выберем f (n) позже.

Так какова средняя глубина дерева? Поскольку мы просто хотим получить асимптотическую оценку, давайте выберем n так, чтобы n - f (n) - 1 было на единицу меньше идеальной степени двух, скажем, 2 ^ k - 1. В этом случае сумма высот в этом часть дерева равна 1 * 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2 ^ (k-1) * k, что составляет (IIRC) около k 2 ^ k, что составляет примерно (n - f (n)) log (n - f (n)) по нашему выбору k. В другой части дерева общая глубина составляет около f (n) ^ 2. Это означает, что средняя длина пути составляет около ((n - f (n)) log (n - f (n)) + f (n) ^ 2) / n. Кроме того, высота дерева f (n). Поэтому мы хотим максимизировать f (n) при сохранении средней глубины O (log n).

Для этого нам нужно найти f (n) такое, что

1. n - f (n) = & Theta; (n), или логарифм в числителе исчезает, а высота не является логарифмической,
2. f (n) ^ 2 / n = O (log n), или второй член в числителе становится слишком большим.

Если вы выберете f (n) = & Theta; (sqrt (n log n)), я думаю, что 1 и 2 удовлетворены максимально. Так что я бы поспорил (хотя я мог быть совершенно неправ в этом), что это так хорошо, как вы можете получить. Вы получаете дерево высоты & Theta; (sqrt (n log n)), которое имеет среднюю глубину & ​​Theta; (Log n).

Надеюсь, это поможет! Если моя математика далеко, пожалуйста, дайте мне знать. Сейчас уже поздно, и я не сделал свою обычную двойную проверку. : -)

Answer 2

Если вы пытаетесь максимизировать высоту дерева, одновременно минимизируя среднюю глубину всех узлов дерева, однозначной наилучшей формой будет форма "зонтика", например, полное двоичное деревос k узлами и высотой = lg k, где 0

Теперь давайте вычислим общую глубину всех узлов.Сумма глубин узлов полной части равна сумме [j * 2 ^ j], где сумма берется от j = 0 до j = lg k.По некоторой алгебре доминирующий член результата равен 2k lg k.

Далее, сумма глубин хвостовой части задается суммой [i + lg k], где сумма берется из i= 0 до i = nk.По некоторой алгебре результат примерно равен (nk) lg k + (1/2) (nk) ^ 2.

Следовательно, суммируя две части выше вместе и деля на n, средняя глубина всехузлы есть (1 + k / n) lg k + (nk) ^ 2 / (2n).Обратите внимание, что, поскольку 0

lg k + n - k = O (sqrt (n lg n))

, это асимптотически больше, чем обычное O (lg n), и является асимптотически самым высоким, которое вы можете сделать деревом, сохраняя при этом среднюю глубину равной O (lg n)

Answer 3

сначала максимизируйте высоту дерева.(есть дерево, где у каждого узла есть только один дочерний узел, поэтому длинная цепочка идет вниз).

Проверьте среднюю глубину.(очевидно, что средняя глубина будет слишком высокой).

в то время как средняя глубина слишком велика, вы должны уменьшить высоту дерева на единицу.Есть много способов уменьшить высоту дерева на один.Выберите способ, который минимизирует среднюю высоту.(По индукции докажите, что каждый раз вы должны выбирать тот, который минимизирует среднюю высоту).Продолжайте движение, пока не попадете под требования среднего роста.(например, рассчитать с помощью индукции формулу для высоты и средней глубины).