ВУЗ:
Составители:
115
Рис. 40. Сбалансированное бинарное дерево
В качестве примера несбалансированного бинарного дерева может
служить дерево знаков зодиака (см. рис. 39), поскольку для узлов
AQUARIUS и GEMINI нарушено условие для величины разности высот
поддеревьев.
Подчеркнём, что сбалансированные бинарные деревья представляют
собой компромисс между оптимальными бинарными деревьями (все
внешние узлы которых должны размещаться на двух соседних уровнях) и
произвольными бинарными деревьями. А путь поиска по сбалансирован-
ному дереву не превышает пути поиска по оптимальному дереву более
чем на 45%.
Теорема (Адельсон-Вельского и Ландиса). Высота сбалансиро-
ванного дерева с N внутренними узлами ограничена значениями
)1lg( +N
и
3277.0)2lg(4405.1 −+N
.
Рассмотрим, что произойдёт при вставке нового узла в сбалансиро-
ванное дерево с использованием алгоритма Т (поиска по дереву со встав-
кой) из предыдущего параграфа. Дерево, представленное на рис. 40, ос-
танется сбалансированным, если новый узел займёт место одного из
внешних узлов 4, 5, 6, 7, 10 или 13, а в других случаях потребуется опре-
делённая реорганизации бинарного дерева.
Вообще необходимость реорганизации дерева возникает, когда в
нём имеется узел с фактором сбалансированности +1 и после вставки
нового узла его правое поддерево становится выше, или в случае, когда
фактор сбалансированности узла равен –1 и выше становится его левое
поддерево.
На рисунке 41 большие прямоугольники α, β, γ и δ представляют
поддеревья с соответствующими высотами. Случай а) имеет место, когда
новый элемент увеличивает высоту правого поддерева узла B с h до h + 1,
а случай б) – когда увеличивается высота левого поддерева узла В. В по-
+
–
•
• •
+
•
•
•
4 5 •
– –
•
0 1
2 3
6 7
•
10
•
•
•
13
8 9 11
12
14
15
16
17
F
D
K
B
E
H
N
A
C G J
M
P
I L
O
Q
Страницы
- « первая
- ‹ предыдущая
- …
- 113
- 114
- 115
- 116
- 117
- …
- следующая ›
- последняя »
