Методы программирования. Громов Ю.Ю - 117 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

117
На рисунке 43 изображено дерево, представленное на рис. 40, после
вставки нового ключа R и выполнения балансировки. Например, если
вставить новый R узел в позицию 17 дерева, представленного на рис. 40,
то после однократного поворота получится сбалансированное дерево,
изображённое на рис. 43. Заметим, что при этом изменились некоторые
факторы сбалансированности.
Рис. 43. Сбалансированное дерево после вставки нового ключа R
Детали процедуры вставки могут быть разработаны различными
способами. При этом кажется, что невозможно избежать использования
вспомогательного стека, поскольку требуется запоминать узлы, затрону-
тые при вставке. Однако описанный ниже алгоритм позволяет обойтись
без стека.
Алгоритм А. (Поиск со вставкой по сбалансированному дереву.)
Дана таблица записей в форме сбалансированного бинарного дерева,
описанного выше. Алгоритм производит поиск данного аргумента K.
Если K отсутствует в таблице, то в соответствующее место дерева встав-
ляется узел, в котором содержится K, и дерево при необходимости балан-
сируется.
Предполагается, что, как и в алгоритме Т из предыдущего парагра-
фа, узлы дерева имеют поля KEY, LLINK и RLINK. Кроме того, имеется
новое поле
B(P) – фактор сбалансированности узла NODE(P),
представляющий разность высот его правого и левого поддеревьев. В нём
всегда содержится только одно из трёх значений: +1, 0 или –1. На верши-
не дерева по адресу HEAD расположен специальный узел, поле RLINK
которого указывает на корень дерева, а LLINK(HEAD) используется для
хранения полной высоты дерева (знание высоты не является необходи-
мым для этого алгоритма, однако полезно при конкатенации, которая
4 5
0 1 2 3
6 7 0
13
8 9
11
12
14
15
16
17
•
F
–
D
•
K
+
H
+
N
–
M
+ P
•
B
•
E
•
G
–
J
•
L
•
O
+
Q
•
A
•
C
•
I
•
R
18

Страницы