ВУЗ:
Составители:
40
Пусть INFO(P) – буква, изображённая в поле INFO узла NODE(P)
дерева, представленного на рис. 15. Тогда, если Р указывает на корень это-
го дерева, имеем: INFO(P) = A, INFO(P*) = B, INFO(P$) = E, INFO($P) = B,
INFO(#P) = C.
Заметим, что в рассматриваемом дереве, как, впрочем, и в любом
бинарном дереве, имеется больше нулевых связей, чем других указате-
лей. Поэтому для более эффективного использования памяти ЭВМ при-
меняют представления бинарных деревьев в виде так называемых про-
шитых деревьев. При этом нулевые связи заменяют связями-нитями,
идущими в другие части дерева и облегчающими его прохождение. Про-
шитое дерево, эквивалентное дереву на рис. 15, изображено на рис. 16.
На нём штриховые линии обозначают связи-нити, которые всегда идут к
узлу, находящемуся выше. Теперь каждый узел имеет две связи: или две
обычные связи, идущие к левому и правому поддеревьям (например, узел С);
или две связи-нити (например, узел Н); или по одной связи каждого типа
(например, узел В). Нити, исходящие из D и J, особые, они возникают в
«самом левом» и «самом правом» узлах, а их значение будет объяснено
позже.
Рис. 16. Прошитое бинарное дерево
Различие штриховых и сплошных связей обеспечивается с помо-
щью двух дополнительных однобитовых полей LTAG и RTAG в каждом
узле списка таких, что:
если LTAG(P) = “−”, то LLINK(P) = $P;
если LTAG(P) = “+”, то LLINK(P) = Q ≠ Λ;
(30)
если RTAG(P) = “−”, то RLINK(P) = P$;
если RTAG(P) = “+”, то RLINK(P) = Q ≠ Λ;
На рисунках 17 и 18 представлены схемы проведения левых и пра-
вых связей-нитей в простейшем (k = 0) и общем (k > 0) случаях. Здесь
A
E
F
B
C
G
H
J
D
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
