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

Итак, давайте предположим, что мы строим дерево таким образом: даны 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) = (n), или логарифмический член в числителе исчезает и высота не является логарифмической,
2. f(n)^2/n = O(log n), или второй член в числителе становится слишком большим.

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

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

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

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

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

Если вы пытаетесь максимизировать высоту дерева, сводя к минимуму среднюю глубину всех узлов дерева, однозначно лучшей формой будет форма «зонтик», например полное бинарное дерево с k узлами и высотой = lg k, где 0 ‹ k ‹ n, вместе с одним путем или «хвостом» из n-k узлов, выходящих из одного из листьев полной части. Высота этого дерева примерно равна lg k + n - k.

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

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

Следовательно, суммируя две приведенные выше части вместе и разделив на n, средняя глубина всех узлов равна (1 + k/n) lg k + (n-k)^2/(2n). Обратите внимание, что поскольку 0 ‹ k ‹ n, первое слагаемое здесь равно O(lg n), независимо от того, какое k мы выбираем. Следовательно, нам нужно только убедиться, что второй член равен O(lg n). Для этого мы требуем, чтобы (n-k)^2 = O(n lg n) или k = n - O(sqrt(n lg n)). При таком выборе высота дерева

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

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