О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 5
Текст из файла (страница 5)
12. Левое поддерево короче правого и height(T4) < height(B).Балансировка: двойной поворот2. Правое поддерево стало ниже левого на 2 уровня (случай,симметричный случаю 1).a. У левого сына высота левого поддерева больше, либо равна высоте правого поддерева.Случай, симметричный случаю 1а.b. У левого сына высота левого поддерева меньше высотыправого поддерева.Случай, симметричный случаю 1b.Здесь мнемоническое правило такое же, как и в случае добавленияузла – если самые глубокие узлы находятся справа или слева, топроизводится одинарный поворот опорного узла в противоположную сторону, а если они находятся посередине, то производитсядвойной поворот.Далее приведена реализация операции удаления узла из АВЛдерева с использованием описанной выше процедуры восстановления баланса.AVL-DELETE(T, x)/* На вход подается дерево T и узел x, который надо удалить издерева.
*/291 deleted = TREE-DELETE(T, x)/* В строках 2–5 проходим по всем узлам, лежащим на пути отродителя удаленного узла к корню, и восстанавливаем в каждомиз них баланс, если он был нарушен. */2 current ← parent[deleted]3 while current ≠ NULL do4AVL-RESTORE-BALANCE(T, current)5current ← parent[current]3.3 Оценка сложности поиска в АВЛ-деревеДва крайних случая АВЛ-деревьев это:(а) совершенное дерево – все узлы имеют показатель баланса 0;(б) дерево Фибоначчи – все узлы, кроме листовых, имеют показатель баланса +1, либо все узлы, кроме листовых, имеют показательбаланса –1.Примеры приведены на Рис.
14.+1+1000(а)0000+10+100(б)Рис. 14. Крайние случаи АВЛ-деревьев: (а) совершенное дерево;(б) дерево ФибоначчиНе для каждого набора ключей можно построить совершенное дерево, равно как и не для каждого набора ключей можно построитьдерево Фибоначчи. Но эти деревья позволяют оценить диапазонвозможных высот АВЛ-деревьев. Совершенное дерево являетсячастным случаем идеально сбалансированного дерева, поэтому30оно имеет минимально возможную высоту для данного количестваузлов. Дерево Фибоначчи, напротив, имеет максимально возможную высоту для данного количества узлов, при условии, что сохраняются свойства АВЛ-дерева.В совершенном дереве у каждого узла, кроме листовых, ровно двасына.
Тогда количество узлов m равно 1 + 2 + 22 + … Количествотаких слагаемых равно количеству уровней в дереве, т.е. на единицубольше высоты этого дерева. Если количество слагаемых равно h +1, то степень двойки в последнем слагаемом будет равна h:m = 1 + 2 + 22 + … + 2h = 2h+1 – 1.Поэтому высота совершенного дерева вычисляется какh = log2(m + 1) – 1(1)Покажем, что дерево Фибоначчи имеет минимально возможнуювысоту для заданного количества узлов среди всех АВЛ-деревьев.Если переформулировать свойсто дерева Фибоначчи, то получится,что при заданной высоте оно имеет минимальное количество узловиз всех возможных АВЛ-деревьев. Пусть Wh – множество АВЛдеревьев заданной высоты h с минимально возможным количествомузлов, а wh – количество узлов в каждом из этих деревьев. Тогда w0= 1 и w1 = 2.
Пусть T – некоторое дерево из множества Wh высоты h≥ 2, а TL и TR – его левое и правое поддеревья. Поскольку T имеетвысоту h, то либо TL, либо TR имеет высоту h – 1. Не ограничиваяобщности рассуждений, предположим, что TR имеет высоту h – 1.Поскольку T является АВЛ-деревом, и оба его поддерева TL и TRтакже являются АВЛ-деревьями, TR является АВЛ-деревом высотыh – 1.
Более того, оно должно АВЛ-деревом высоты h – 1 с минимально возможным количеством узлов, потому как иначе оно моглобы быть заменено деревом той же высоты, но с меньшим количеством узлов, чтобы все дерево T имело минимально возможное количество узлов.
Поэтому TR Wh1 . Аналогично, поскольку T является АВЛ-деревом, разность высот его левого и правого поддеревьев не должна превышать 1 по модулю, а высота дерева равна h,высота дерева TL может быть равна либо h – 1, либо h – 2. Но Т31должно иметь минимальное количество узлов, поэтому TL Wh2 .Следовательно, wh = 1 + wh-2 + wh-1. Поскольку w0 = 1 и w1 = 2, первые несколько значений wh будут равны 1, 2, 4, 7, 12, 20, ... .
Можнодоказать по индукции, что wh = fh+3 – 1.Для оценки высоты дерева Фибоначчи потребуется привести некоторые выкладки.Из определения дерева Фибоначчи следует, что для любого узла,кроме листовых, разность высот левого и правого поддеревьевравна 1 либо –1. Не ограничивая общности рассуждений, будемсчитать, что эта разность равна 1. Таким образом, если высота дерева равна h, то высоты левого и правого поддеревьев равны h – 2и h – 1 соответственно. Это свойство выполняется для любогоподдерева дерева Фибоначчи.Определение 3: Числа Фибоначчи – это элементы числовой последовательности, где первые два числа равны 1, а каждое последующее число равно сумме двух предыдущих:f1 = 1, f2 = 1, fn = fn-1 + fn-2, n >=3, n .(2)Теорема 1. Число узлов в дереве Фибоначчи Fh высоты h равноm(h) = fh+2 – 1.Доказательство (по индукции)Базис: m(0) = f2 – 1 = 0, m(1) = f3 – 1 = 1.Шаг: по определению m(h) = m(h – 1) + m(h – 2) + 1.Имеем m(h) = (fh+1 – 1) + (fh – 1) + 1 = fh+2 – 1, т.к.
fh+1 + fh = fh+2 (следует из Определения 1). Теорема доказана.Теорема 2. Пусть C1 и C2 таковы, что уравнениеr2 – C1r – C2 = 0(3)имеет два различных корня r1 и r2, r1 ≠ r2. Пусть последовательность an такова, чтоan = α1r1n + α2r2n.32(4)Тогда выполняется соотношениеan = C1an-1 + C2an-2.(5)Доказательство. r1 и r2 – корни уравнения (3), тогда r1 = C1r1 + C2и r22 = C1r2 + C2.2Имеем:C1an-1 + C2an-2 = C1(α1r1n-1 + α2r2n-1) + C2(α1r1n-2 + α2r2n-2) =α1r1n-2(C1r1 + C2) + α2r2n-2(C1r2 + C2) =α1r1n-2 r12 + α2r2n-2 r22 = α1r1n + α2r2n = an.(6)Теорема доказана.Теорема 3. Пусть C1 и C2 таковы, что уравнение (3) имеет два различных действительных корня r1 и r2, r1 ≠ r2.Пусть последовательность an задана значениями своих первыхчленов a0 и a1 и рекуррентным соотношением (5).
Тогда для некоторых α1 и α2 и любого n = 1,2,… выполняется соотношение (4).Доказательство. Подберем такие α1 и α2, чтобы выполнялось соотношение (4):a0 = α1 + α2, и(7)a1 = α1r1 + α2r2.(8)Для этого рассмотрим совокупность (7) и (8) как систему линейныхуравнений, которую надо решить относительно α1 и α2. Получим:1 a1 a0 r2,r1 r22 a1 a0 r1.r1 r2Соотношение (4) выполняется для a0 и a1.
Действительно,a0 1r10 2 r20 и a1 1r11 2r21 . Докажем по индукции, чтоесли соотношение выполняется для an-2 и an-1, то оно выполняетсядля an. Для этого повторим в обратном порядке вывод (5) из (4),33который проводился при доказательстве Теоремы 2, т.е. выведем(4) из (5). Для этого необходимо выписать цепочку (6) в обратномпорядке:α1r1n + α2r2n = α1r1n-2 r12 + α2r2n-2 r22 =α1r1n-2(C1r1 + C2) + α2r2n-2(C1r2 + C2) =n-1C1(α1r1 + α2r2n-1) + C2(α1r1n-2 + α2r2n-2) = C1an-1 + C2an-2 = an.Теорема доказана.Применим доказанные теоремы к числам Фибоначчи. Соотношение (2) эквивалентно соотношению (5) при С1 = С2 = 1.
Уравнение(3) при этом записывается какr2 – r – 1 = 0и имеет корни r1 1 51 5и r2 . Следовательно, согласно22Теореме 3:f0 1 2 0 ,f1 1 (1 51 5) 2 () 1,221 f n 1r1n 2 r2n 11,2 ,551 1 5 n 1 1 5 n() () .2255Согласно Теореме 1m(h) f h 2 1 1 1 5 h2 1 1 5 h2() () 122551 1 5 h 2()12534m( h ) 1 Введем обозначение 1 1 5 h2()25.1 5. Тогда2m(h) 1 1 h25(9)Логарифмируя обе части (9), получаемlog2 (m(h) 1) log2 (1) (h 2) log 2 ,5log2 (m(h) 1) log2 ( 5) (h 2)log2 ,h2log 2 (m 1) log 2 5,log 2 log 2 откудаh 1.44log2 (m 1) 0.32.(10)Таким образом, учитывая оценку высоты совершенного дерева (1)и оценку высоты дерева Фибоначчи (10) получаем, что высота hАВЛ-дерева из m узлов находится в диапазонеlog2 (m 1) h 1.44log2 (m 1) 0.32 .(11)Это соотношение (11) задает оценку количества сравнений припоиске узла в АВЛ-дереве на пути от корня к этому узлу. Если,например, в АВЛ-дереве 106 вершин, то его высота, а, следовательно, и сложность поиска узла в нем, не превысит 29.3.4 Задачи351.
Обосновать, почему после поворота дерево поиска остается деревом поиска.2. Обосновать, почему при вставке узла в АВЛ-дерево выполнения одинарного или двойного поворота поддерева с корнем вопорном узле (первый узел, в котором нарушен баланс, на пути отдобавленного узла к корню) достаточно для восстановления баланса во всем дереве.3. Доказать по индукции, что минимальное количество узлов вАВЛ-дереве заданной высоты h равно fh+3 – 1, где fh+3 – (h+3)-е число Фибоначчи.4. Существуют ли два АВЛ-дерева, у которых высота h (0 ≤ h ≤ 10)одинакова, а число вершин различается на 800? Привести ответ(«да» или «нет» и его обоснование). Замечание: пустое деревоимеет высоту 0, а дерево из одного узла – высоту 1.5. Существуют ли два АВЛ-дерева, у которых высота h (0 ≤ h ≤ 11)одинакова, а число вершин различается на 1712? Привести ответ(«да» или «нет» и его обоснование).6.
Пусть в АВЛ-дереве используется стандартный алгоритм поиска по ключу и пусть для нахождения некоторого ключа пришлосьпросмотреть 11 вершин дерева. Каково минимально возможноечисло вершин в таком дереве? Ответ обосновать.7. Ключи 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 добавляются в изначальнопустое АВЛ-дерево в некоторой последовательности. Существуетли такая последовательность добавления этих ключей, при которой не будет необходимости выполнять повороты при вставке?Ответ обосновать.8. В первоначально пустое АВЛ-дерево были занесены (согласностандартному алгоритму вставки) в указанном порядке следующиеключи: 20, 15, 9, 18, 40, 35, 51, 27, 37, 36.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
