|
Прошитое двоичное дерево Прошитое двоичное дерево — это вариант двоичного дерева, который позволяет производить быстрый обход — если дан указатель на узел в прошитом дереве, можно легко найти следующий по порядку узел (и/или предыдущий). ПредпосылкиДвоичные деревья, включая двоичные деревья поиска (но не ограничиваясь ими) и их варианты, могут быть использованы для сохранения множества элементов в определённом порядке. Например, двоичное дерево поиска предполагает, что элементы данных упорядочены каким-либо образом и сохраняют этот порядок при вставке и удалении. Одна полезная операция над таким деревом — обход, то есть посещение элементов дерева в порядке, в котором они будут запомнены (который соответствует упорядочению узлов в случае дерева двоичного поиска). Алгоритм простого рекурсивного обхода, который посещает каждый узел дерева двоичного поиска, следующий. Предположим, что t — указатель на узел или nil. «Посещение» t может означать любую операцию с этим узлом t или приписанным ему содержимым. Алгоритм обхода(t):
Проблема этого алгоритма заключается в том, что ввиду рекурсии алгоритм использует пространство стека, пропорциональное высоте дерева. Если дерево достаточно сбалансировано, эта величина достигает O(log n) для дерева из n элементов. В наихудшем случае, когда дерево принимает форму цепочки, высота дерева равна n, так что алгоритм потребует пространство стека величиной O(n). В 1968, Дональд Кнут задал вопрос, существует ли нерекурсивный алгоритм центрированного обхода, который не использует стек и оставляет дерево неизменным. Одно из решений этой проблемы — прошивка дерева, представленная Джеймсом Х. Моррисом в 1979[1][2]. ОпределениеПрошитое дерево определяется следующим образом:
Можно также найти родителя узла из прошитого двоичного дерева без явного использования указателя на родителя или стека, хотя медленнее. Это полезно, когда стек имеет ограничение, или когда стек указателей на родителей недоступен (для нахождения указателя на родителя с помощью поиска в глубину). Чтобы понять, как это возможно, рассмотрим узел k, имеющий правого потомка r. Тогда левый указатель узла r должен быть либо потомком, либо указателем обратно на k. В случае, когда r имеет левого потомка, то левый потомок должен иметь своего левого потомка, либо указатель назад к k, и так далее для всех последующих левых потомков. Таким образом, перебирая последовательно цепочку левых указателей из r, мы, в конце концов, находим прошивочный указатель обратно на k. Ситуация симметрична, когда q является левым потомком p, в этом случае мы можем проследовать правые потомки узла q для получения прошивочного указателя на p. Типы прошитых двоичных деревьев
На языке Python: def parent(node):
if node is node.tree.root:
return None
else:
x = node
y = node
while True:
if is_thread(y):
p = y.right
if p is None or p.left is not node:
p = x
while not is_thread(p.left):
p = p.left
p = p.left
return p
elif is_thread(x):
p = x.left
if p is None or p.right is not node:
p = y
while not is_thread(p.right):
p = p.right
p = p.right
return p
x = x.left
y = y.right
Массив центрированного обходаПрошивка — это ссылки на предшествующий и последующий узлы данного узла согласно центрированному обходу. Если порядок прошитого дерева — это ABCDEFGHI, узел D предшествует E, а F следует за узлом E.
Пример
Попытаемся сформировать прошитое дерево из обычного двоичного дерева
Упорядочение вершин центрированного обхода для дерева выше — D B A E C. Таким образом, соответствующее прошитое двоичное дерево будет выглядеть следующим образом
Нулевой указательВ прошитом m-кратно двоичном дереве с n узлами, существует n*m — (n-1) пустых ссылок. Нерекурсивный центрированный обход для прошитого двоичного дереваКак нерекурсивный метод обхода, метод должен быть итеративной процедурой, все шаги обхода узла должны быть в цикле, так что то же самое можно применить ко всем узлам дерева. Мы снова предположим центрированный обход дерева. Тогда для любого узла мы обходим сначала левое поддерево (если оно существует и в случае, если мы не обходили его ранее). Затем мы посещаем (то есть печатаем значение узлов в нашем случае) сам узел, а уж затем обходим правое поддерево (если оно существует). Если правого дерева нет, проверяем прошитую ссылку и делаем прошитую вершину текущим узлом в рассмотрении. Смотрите пример ниже.
АлгоритмШаг-1: Для текущего узла проверяем, имеется ли левый потомок, которого нет в списке посещённых. Если такой имеется, переходим к шагу 2, иначе — к шагу 3. Шаг-2: Помещаем левого потомка в список посещённых узлов и делаем его текущим узлом. Переходим к шагу 6. Шаг-3: Печатаем узел и если узел имеет правого потомка, переходим к шагу 4, иначе переходим к шагу 5. Шаг-4: Делаем правого потомка текущим узлом. Шаг-5: Если существует прошивочный узел, делаем его текущим узлом. Шаг-6: Если все узлы напечатаны, завершаем работу, иначе переходим к шагу 1.
Примечания
Литература
Ссылки
|
