Как доказать, что средняя высота дерева двоичного поиска равна O (logn)?

Question

Я думал о доказательстве, но не смог набросать вещи на бумаге У меня было, хотя, отношение рекуррентности для высоты дерева двоичного поиска было бы

T (n) = T (k) + T (nk-1) + 1

Где k - количество элементов в левом поддереве, если root и nk-1 - на правом поддереве root (и n = общее количество узлов)

(Поправьте меня, если вещь выше это неправильно)

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

Мое утверждение: у меня будет приблизительно половина случаев из всех возможных .. Пример

Root

(0, N -1) ИЛИ (1, Н-2) ИЛИ. , (N-1,0)

Где N - общее количество узлов. Сейчас я рассматриваю половину вышеупомянутых дел для расчета среднего случая ... (я не знаю, правильно ли я это делаю или нет. Оценка по этому вопросу будет наиболее ценной)

Итак, я получаю:

T (n) = T (n / 2) + T (n / 2) + 1

T (n) = 2T (n / 2) + 1

Теперь, когда я применяю мастер-метод для получения приблизительного ответа по полученному рекуррентному соотношению .. Я получаю O (n).

Теперь, как мне действовать ...? (Мое ожидание было вместо n, я должен был получить logn) Но это не сработало .. Так что, плз, предложите, как мне действовать дальше. (Является ли мой подход вообще правильным ... с самого начала, расскажите мне об этом?)

Answer 1

Из «Алгоритмов» Роберта Седжвика и Кевина Уэйна

Определение. Двоичное дерево поиска (BST) - это двоичное дерево, где каждый узел имеет сопоставимый ключ (и соответствующее значение) и удовлетворяет ограничению, заключающемуся в том, что ключ в любом узле больше, чем ключи во всех узлах в левом поддереве этого узла, и меньше, чем ключи во всех узлах в правом поддереве этого узла.

Предложение C. Для поиска совпадений в BST, построенном из N случайных ключей, требуется ~ 2 ln N (около 1,39 lg N) сравнивает, в среднем.

Доказательство: Количество сравнений, используемых для поиска, заканчивающегося в данном узле, равно 1 плюс глубина. Добавляя глубины всех узлов, мы получаем величину, известную как длина внутреннего пути дерева. Таким образом, искомая величина равна 1 плюс средняя длина внутреннего пути BST, которую мы можем проанализировать с помощью того же аргумента, который мы использовали для предложения K в разделе 2.3: Пусть CN - общая длина внутреннего пути BST, построенного из вставки N случайным образом упорядоченные отдельные ключи, так что средняя стоимость попадания поиска составляет 1 CN / N. У нас C0 = C1 = 0, а для N> 1 мы можем записать рекуррентное отношение, которое напрямую отражает рекурсивную структуру BST:

CN = N 1 (C0 CN1) / N + (C1 CN2) / N. , , (CN1 C0) / N

Член N 1 учитывает, что root вносит 1 в длину пути каждого из других N 1 узлов в дереве; остальная часть выражения учитывает поддеревья, которые с равной вероятностью могут быть любого из N размеров. После перестановки членов это повторение почти идентично тому, которое мы решили в разделе 2.3 для быстрой сортировки, и мы можем вывести приближение CN ~ 2N ln N

. Я также рекомендую вам проверить эту лекцию Mit Деревья бинарного поиска, BST Sort

Также проверьте главу 3.2 из книг Алгоритмы, в ней подробно описаны деревья бинарного поиска