Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish


Download 0.86 Mb.
bet10/16
Sana18.06.2023
Hajmi0.86 Mb.
#1578342
1   ...   6   7   8   9   10   11   12   13   ...   16
Bog'liq
14 mavzu “Dag‘al kuch” usuli bilan tartiblashtirishi

Прошитые деревья

Прошитые деревья

В бинарном дереве, содержащем N узлов, на каждый узел, кроме корня указывает ровно одна связь. Всего связей 2*N; непустых - N-1, следовательно, N+1 связь пуста.

Пустые связи существуют только для того, чтобы обозначить, что дальше в этом направлении пути нет, для чего достаточно одного бита.

Возникает вопрос: а нельзя ли более рационально использовать пространство, занимаемое пустыми связями.

Прошитые деревья используют место, занимаемое пустыми связями для хранения указателей, упрощающих прохождение дерева. Эти дополнительные связи называют нитями, откуда и появился термин прошитые. Введем обозначения:

Прошитые деревья используют место, занимаемое пустыми связями для хранения указателей, упрощающих прохождение дерева. Эти дополнительные связи называют нитями, откуда и появился термин прошитые. Введем обозначения:

*P – предшественник узла P в обратном порядке,

P* – последователь узла P в обратном порядке,

+P – предшественник в прямом порядке,

P+ – последователь в прямом порядке

Дерево может быть прошито для обхода в одном из порядков.

Дерево может быть прошито для обхода в одном из порядков.

Рассмотрим дерево, прошитое для обхода в обратном порядке. Вместо пустых левых связей будем хранить указатель на предшественника в обратном порядке, вместо пустых правых связей – указатель на последователя. Эти связи будем называть "нитями”.

На рис. изображено прошитое дерево. Пунктиром изображены нити.

Типы прошитых двоичных деревьев

Типы прошитых двоичных деревьев

1. Одиночное прошивание: каждый узел прошивается указателем либо на предыдущий по порядку узел, либо на следующий по порядку узел (левый или правый).

2. Двойное прошивание: каждый узел прошивается указателем как на предыдущий узел, так и на следующий (левый и правый).


Download 0.86 Mb.

Do'stlaringiz bilan baham:
1   ...   6   7   8   9   10   11   12   13   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling