Прошитые БД

Эффективность прохождения дерева рекурсивными и нерекурсивными алгоритмами может быть увеличена, если использовать пустые указатели на отсутствующие поддеревья для хранения в них адресов узлов преемников, которые надо посетить при заданном порядке прохождения БД. Такой указатель называется нитью. Его следует отличать, например, с помощью отрицательных значений, от указателей в дереве, которые используются с левым и правым поддеревьями. Операция, заменяющая пустые указатели на нити, называется прошивка. Она может выполняться по-разному. Если нити заменяют пустые указатели в узлах с пустыми правыми поддеревьями, при просмотре в симметричном порядке, то БД называется симметрично прошитым справа. Абсолютная величина отрицательного значения нити узла Р есть индекс узла, являющегося преемником узла Р при просмотре в симметричном порядке. Похожим образом может быть определено БД, симметрично прошитое слева: дерево, в котором каждый пустой левый указатель изменен так, что он содержит нить – связь к предшественнику данного узла при просмотре в симметричном порядке. Симметрично прошитое БД – БД, которое симметрично прошито слева и справа. Однако БД, симметрично прошитое слева, не дает тех преимуществ, что БД, симметрично прошитое справа. На рис. 23 показано БД, симметрично прошитым справа. На нем пунктирными линиями обозначены прошивочные нити.

Рис. 23 – Симметрично прошитое справа БД

Также используются БД, прямо прошитые слева и справа. В них пустые правые и левые указатели узлов заменены соответственно на их преемников и предшественников при прямом порядке просмотра. Прошитые БД эффективно проходятся без использования стека.

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

Рассмотрим вставку новой вершины слева от заданной в симметрично прошитое БД (рис. 24). На рис. 25 показано результирующее БД.

Рис. 24 – Исходное симметрично прошитое БД

Рис. 25 – Прошитое дерево после вставки в него нового элемента

Здесь требовалось вставить вершину I вкачестве левого поддерева вершины А, если А не имеет левого поддерева. В противном случае новая вершина вставляется между А и ее левым сыном.

Для удобства создания и обхода дерева используется дополнительная головная вершина Head, которая служит при симметричном обходе предшественником его первой вершины и приемником всех его концевых вершин.

Дата добавления: 2015-07-16