Доказательство того, что случайно построенное двоичное дерево поиска имеет логарифмическую высоту

10

Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )nO(logn)

user1675999
источник
1
Какой вопрос? Какой пример? Пожалуйста, отредактируйте и дайте полную информацию.
Ран Г.
3
Пожалуйста, избегайте использования сокращений (таких как BST) и предполагайте, что у большинства из нас нет книги CLRS. Если бы вы могли скопировать эту теорему здесь и объяснить, что же вы не понимаете, вы получите больше ответов.
Ран Г.
2
Это будет зависеть от того, как построено двоичное дерево поиска. (Даже если результат не поможет, доказательство будет.) Некоторые подробности будут полезны.
Питер Шор

Ответы:

21

Давайте сначала подумаем об этом интуитивно. В лучшем случае дерево идеально сбалансировано; в худшем случае дерево совершенно не сбалансировано:

Сбалансированное по высоте дерево двоичного поискаНаихудшее двоичное дерево поиска

Начиная с корневого узла , это левое дерево имеет вдвое больше узлов на каждой последующей глубине, так что дерево имеет узел и высота (что в данном случае 3). С небольшой математикой , то есть он имеет высота. Для совершенно неуравновешенного дерева высота дерева просто . Итак, у нас есть свои границы.n = h i = 0 2 i = 2 h + 1 - 1 h n 2 h + 1 - 1 h log 2 ( n + 1 ) - 1 l o g 2 n O ( log n ) n - 1 O ( n )pn=i=0h2i=2h+11hn2h+11hlog2(n+1)1log2nO(logn)n1O(n)

Если бы мы строили сбалансированное дерево из упорядоченного списка , мы бы выбрали средний элемент в качестве нашего корневого узла. Если вместо этого мы случайным образом строим дерево, то любой из узлов с равной вероятностью будет выбран, а высота нашего дерева равна: Мы знаем, что в двоичном дереве поиска левое поддерево должно содержать только ключи меньше корневого узла. Таким образом, если мы случайным образом выберем элемент , левое поддерево имеет элементы а правое поддерево имеет элементов, поэтому более компактно:п ч е я г ч т т т е е = 1 + макс ( ч е я г ч т л е е т с у б т т е е , ч е я г ч т г я г ч т ев U Ь т т е е{1,2,,n}ni t h i - 1 n - i h n = 1 + max ( h i - 1 , h n - i ) E [ h n ] = 1

heighttree=1+max(heightleft subtree,heightright subtree)
ithi1nihn=1+max(hi1,hni), Исходя из этого, имеет смысл, что если каждый элемент с одинаковой вероятностью будет выбран, ожидаемое значение является просто средним числом всех случаев (а не средневзвешенным). Следовательно:E[hn]=1ni=1n[1+max(hi1,hni)]

Как я уверен, вы заметили, что я немного отклонился от того, как CLRS доказывает это, потому что CLRS использует два относительно распространенных метода проверки, которые приводят в замешательство непосвященных. Во-первых, использовать показатели (или логарифмы) того, что мы хотим найти (в данном случае высоту), что заставляет математику работать немного более чисто; второе - использовать индикаторные функции (которые я здесь просто проигнорирую). CLRS определяет экспоненциальную высоту как , поэтому аналогичное повторение равно . Y n = 2 × max ( Y i - 1 , Y n - i )Yn=2hnYn=2×max(Yi1,Yni)

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

E[Yn]=i=1n1nE[2×max(Yi1,Yni)]=2ni=1nE[max(Yi1,Yni)]
1nici=ciiE[ax]=aE[x]maxфункция с чем-то большим, потому что в противном случае упрощение трудно. Если мы рассуждаем о неотрицательном , : , затем: , что последний шаг следует из наблюдения, что для , и и выполняется все путь к , и , поэтому каждый членXYE[max(X,Y)]E[max(X,Y)+min(X,Y)]=E[X]+E[Y]
E[Yn]2ni=1n(E[Yi1]+E[Yni])=2ni=0n12E[Yi]
i=1Yi1=Y0Yni=Yn1i=nYi1=Yn1Yni=Y0Y0к появляется дважды, так что мы можем заменить весь суммирование с аналогичным один. Хорошей новостью является то, что у нас есть повторение ; Плохая новость в том, что мы не намного дальше, чем начали.Yn1E[Yn]4ni=0n1E[Yi]

В этот момент CLRS извлекает доказательство индукции из своего ... репертуара математического опыта, который включает в себя идентификатор они оставляют пользователю для подтверждения. Что важно в их выборе, так это то, что его самый большой член равен , и помните, что мы используем экспоненциальную высоту такую ​​что , Возможно, кто-то прокомментирует, почему именно этот бином был выбран. Общая идея, однако, состоит в том, чтобы связать сверху наше повторение с выражением для некоторой константы .E[Yn]14(n+33)i=0n1(i+33)=(n+34)n3Yn=2hnhn=log2n3=3log2nO(logn)nkk

Чтобы закончить с одним вкладышем:

2E[Xn]E[Yn]4ni=0n1E[Yi]14(n+33)=(n+3)(n+2)(n+1)24E[hn]=O(logn)
Merbs
источник
ВАУ, СПАСИБО !!!! Даже если я не знаю об ожидаемой стоимости, этот вид имеет смысл. Я не делал осторожный курс по математике, прежде чем делать алгоритмы. Я буду публиковать больше комментариев, если у меня есть некоторые сомнения. Спасибо, Мербс.
user1675999
но почему именно экспоненциальная высота меньше или равна выбранному биному? Я до сих пор не понимаю, почему мы не можем выбрать другой бином с другим по величине термином и сделать точно такую ​​же математику ... возможно, я глуп, но я просто не понимаю, почему ... и до этого точного доказательства имеет смысл, тогда им просто нужно было что-то вытащить совершенно
неожиданно
@ Zeks Итак, мы можем выбрать другие биномы с большими терминами. Если термин все еще является полиномиальным ( n^k), то вывод тот же, потому что kон отброшен в нотации big-O (способ 3 был отброшен). Но если мы подставим что-то в exponential ( e^n), это будет правильная верхняя граница, но не жесткая . Мы знаем, что ожидаемая высота, по крайней мере, логарифмическая, поэтому определение, что она максимально логарифмическая, делает ее жесткой.
Merbs
@DavidNathan Я не понимаю твоего беспокойства - ты сомневаешься, что 1 / n является константой или что ее можно вынести за пределы суммирования? Оно, как и константа 2, в значительной степени вынесено в иллюстративных целях, чтобы упростить оставшееся доказательство.
Merbs