Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )
10
Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )
Ответы:
Давайте сначала подумаем об этом интуитивно. В лучшем случае дерево идеально сбалансировано; в худшем случае дерево совершенно не сбалансировано:
Начиная с корневого узла , это левое дерево имеет вдвое больше узлов на каждой последующей глубине, так что дерево имеет узел и высота (что в данном случае 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 )п n = ∑чася = 02я= 2ч + 1- 1 час n ≤ 2ч + 1- 1 → h ≤ ⌈ log2( П + 1 ) - 1 ⌉ & le ; ⌊ л о г2н ⌋ O ( журналн ) n - 1 → O ( n )
Если бы мы строили сбалансированное дерево из упорядоченного списка , мы бы выбрали средний элемент в качестве нашего корневого узла. Если вместо этого мы случайным образом строим дерево, то любой из узлов с равной вероятностью будет выбран, а высота нашего дерева равна: Мы знаем, что в двоичном дереве поиска левое поддерево должно содержать только ключи меньше корневого узла. Таким образом, если мы случайным образом выберем элемент , левое поддерево имеет элементы а правое поддерево имеет элементов, поэтому более компактно:п ч е я г ч т т т е е = 1 + макс ( ч е я г ч т л е е т с у б т т е е , ч е я г ч т г я г ч т ев U Ь т т е е{ 1 , 2 , … , n } N i t h i - 1 n - i h n = 1 + max ( h i - 1 , h n - i ) E [ h n ] = 1
Как я уверен, вы заметили, что я немного отклонился от того, как CLRS доказывает это, потому что CLRS использует два относительно распространенных метода проверки, которые приводят в замешательство непосвященных. Во-первых, использовать показатели (или логарифмы) того, что мы хотим найти (в данном случае высоту), что заставляет математику работать немного более чисто; второе - использовать индикаторные функции (которые я здесь просто проигнорирую). CLRS определяет экспоненциальную высоту как , поэтому аналогичное повторение равно . Y n = 2 × max ( Y i - 1 , Y n - i )YN= 2часN YN= 2 × max ( Yя - 1, Yн - я)
Предполагая независимость (что каждая ничья элемента (из доступных элементов), являющаяся корнем поддерева, не зависит от всех предыдущих ничьих), мы по-прежнему имеем отношение: для которого я сделал два шага: (1) перемещение снаружи, потому что это константа, и одним из свойств суммирования является то, что , и (2) перемещение 2 снаружи, потому что оно также является константой, и одним из свойств ожидаемых значений является . Теперь мы собираемся заменить1
В этот момент CLRS извлекает доказательство индукции из своего ... репертуара математического опыта, который включает в себя идентификатор они оставляют пользователю для подтверждения. Что важно в их выборе, так это то, что его самый большой член равен , и помните, что мы используем экспоненциальную высоту такую что , Возможно, кто-то прокомментирует, почему именно этот бином был выбран. Общая идея, однако, состоит в том, чтобы связать сверху наше повторение с выражением для некоторой константы .Е[ YN] ≤ 14( п+33) Σn - 1я = 0( я+33) = ( n+34) N3 YN= 2часN часN= журнал2N3= 3 журнала2n → O ( журналн ) NК К
Чтобы закончить с одним вкладышем:
источник
n^k
), то вывод тот же, потому чтоk
он отброшен в нотации big-O (способ 3 был отброшен). Но если мы подставим что-то в exponential (e^n
), это будет правильная верхняя граница, но не жесткая . Мы знаем, что ожидаемая высота, по крайней мере, логарифмическая, поэтому определение, что она максимально логарифмическая, делает ее жесткой.