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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

43
− прохождение прошитых деревьев осуществляется несколько бы-
стрее, чем непрошитых;
− для алгоритма Т требуется больший объём памяти ЭВМ из-за не-
обходимости применения стека;
− использование алгоритма S даёт возможность перейти от Р к Р$,
не проходя всё бинарное дерево.
Таким образом, прошитое бинарное дерево с точки зрения его про-
хождения имеет преимущества перед непрошитым. Заметим, что упомя-
нутые преимущества прошитых деревьев свелись бы на нет, если бы в
самом начале было затруднительно проведение связей-нитей. Однако
идея прошитых деревьев вполне работоспособна в силу того, что про-
шить деревья довольно легко. Это можно сделать с помощью следующе-
го алгоритма.
Алгоритм I. (Включение узла в прошитое бинарное дерево.)
Данный алгоритм присоединяет одиночный узел NODE(Q) в качестве
правого поддерева узла NODE(P), если правое поддерево пусто (т.е. если
RTAG(P) = ”−”), и включает NODE(Q) между NODE(P) и NODE(RLINK(P))
в противном случае. Предполагается, что бинарное дерево, в котором
производится включение, является прошитым как на рис. 19.
I1. [Установка признаков и связей.]
RLINK(Q) ← RLINK(P), RTAG(Q) ← RTAG(P), RLINK(P) ← Q,
RTAG(P) ← ”+”, LLINK(Q) ← P, LTAG(Q) ← ”−”.
I2. [RLINK(P) − нить?]
Если RTAG(Q) = ”+”, то LLINK(Q$) ← Q. (Здесь адрес Q$ определя-
ется алгоритмом S, который будет работать должным образом, даже если
LLINK(Q$) теперь указывает на узел NODE(P), а не на узел NODE(Q).
Необходимость в этом шаге возникает только в том случае, когда проис-
ходит включение в середину прошитого дерева, а не просто включение
«нового листа».) ■
Заметим, что поменяв ролями левое и правое поддеревья, а также
заменив Q$ на $Q на шаге I2, получим алгоритм I ’, производящий по-
добным же образом включение влево.
Кроме рассмотренных представлений нигде не прошитых и всюду
прошитых деревьев имеется представление, называемое право-
прошитыми бинарными деревьями. В них пустые правые поддеревья
представляются связями-нитями RLINK, а для пустых левых поддеревьев
LLINK = Λ. Аналогичным способом строятся левопрошитые бинарные
деревья. Если в алгоритме S на шаге S2 проверку LTAG = ”+” заменить на
”LLINK ≠ Λ”, то получим алгоритм для прохождения в обратном порядке
правопрошитых бинарных деревьев. Отметим, что на практике чаще все-
го встречается случай, когда требуется проведение нитей только с одной
стороны.

Страницы