WikiSort.ru - Программирование

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

Предпосылки

Двоичные деревья, включая двоичные деревья поиска (но не ограничиваясь ими) и их варианты, могут быть использованы для сохранения множества элементов в определённом порядке. Например, двоичное дерево поиска предполагает, что элементы данных упорядочены каким-либо образом и сохраняют этот порядок при вставке и удалении. Одна полезная операция над таким деревом — обход, то есть посещение элементов дерева в порядке, в котором они будут запомнены (который соответствует упорядочению узлов в случае дерева двоичного поиска).

Алгоритм простого рекурсивного обхода, который посещает каждый узел дерева двоичного поиска, следующий. Предположим, что t — указатель на узел или nil. «Посещение» t может означать любую операцию с этим узлом t или приписанным ему содержимым.

Проблема этого алгоритма заключается в том, что ввиду рекурсии алгоритм использует пространство стека, пропорциональное высоте дерева. Если дерево плохо сбалансировано, эта величина достигает O(log n) для дерева из n элементов. В наихудшем случае, когда дерево принимает форму цепочки, высота дерева равна n, так что алгоритм затребует пространство стека величиной O(n).

В 1968, Дональд Кнут задал вопрос, существует ли нерекурсивный алгоритм центрированного обхода, который не использует стек и оставляет дерево неизменным. Одно из решений этой проблемы — прошивка дерева, представленная Джеймсом Х. Моррисом в 1979^[1][2].

Определение

Прошитое дерево определяется следующим образом:

«Двоичное дерево прошивается путём присвоения всем указателям правого потомка, которые обычно были бы нулевыми указателями, указателей на следующий по порядку узел данного узла (если такой существует), а всем указателям левого потомка, которые обычно были бы нулевыми указателями, указателей на предыдущие узлы в упорядочении»^[3].

Можно также найти родителя узла из прошитого двоичного дерева без явного использования указателя на родителя или стека, хотя медленнее. Это полезно, когда стек имеет ограничение, или когда стек указателей на родителей недоступен (для нахождения указателя на родителя с помощью поиска в глубину).

Чтобы понять, как это возможно, рассмотрим узел k, имеющий правого потомка r. Тогда левый указатель узла r должен быть либо потомком, либо указателем обратно на k. В случае, когда r имеет левого потомка, то левый потомок должен иметь своего левого потомка, либо указатель назад к k, и так далее для всех последующих левых потомков. Таким образом, перебирая последовательно цепочку левых указателей из r, мы, в конце концов, находим прошивочный указатель обратно на k. Ситуация симметрична, когда q является левым потомком p, в этом случае мы можем проследовать правые потомки узла q для получения прошивочного указателя на p.

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

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

На языке 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) пустых ссылок.

Нерекурсивный центрированный обход для прошитого двоичного дерева

Как нерекурсивный метод обхода, метод должен быть итеративной процедурой, все шаги обхода узла должны быть в цикле, так что то же самое можно применить ко всем узлам дерева. Мы снова предположим центрированный обход дерева. Тогда для любого узла мы обходим сначала левое поддерево (если оно существует и в случае, если мы не обходили его ранее). Затем мы посещаем (то есть печатаем значение узлов в нашем случае) сам узел, а уж затем обходим правое поддерево (если оно существует). Если правого дерева нет, проверяем прошитую ссылку и делаем прошитую вершину текущим узлом в рассмотрении. Смотрите пример ниже.

Примечания

Литература

• Joseph H. Morris. Traversing binary trees simply and cheaply // Information Processing Letters. — 1979. — Т. 9, вып. 5. — DOI:10.1016/0020-0190(79)90068-1.
• Prabhaker Mateti, Ravi Manghirmalani. Morris' tree traversal algorithm reconsidered // Science of Computer Programming. — 1988. — Т. 11. — С. 29–43. — DOI:10.1016/0167-6423(88)90063-9.
• Christopher J. Van Wyk. Data Structures and C Programs. — 1988. — С. 175. — ISBN 978-0-201-16116-8.

Ссылки

• Tutorial on threaded binary trees
• GNU libavl 2.0.2, Section on threaded binary search trees

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.