10. Операции над деревьями
 

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

• создание дерева;
• поиск (локализация) элемента в дереве;
• включение элемента в дерево;
• обработка данных в вершинах дерева;
• удаление элемента из дерева;
• сохранение и восстановление бинарного дерева;
• уничтожение бинарного дерева.

Эти операции рассматриваются применительно к двоичным деревьям, размещаемым в динамической памяти.

Создание дерева. Для управления деревом как динамической структурой необходимо наличие дескриптора. Если дескриптор построен в динамической памяти, то доступ к дереву осуществляется через цепочку указателей, как показано.

Доступ к дереву посредством дескриптора

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

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

Поскольку новые элементы можно включать в дерево поиска в любой момент выполнения программы, то создание дерева сводится к управлению вызовом функции включения элемента. Функции включения в обычное и сбалансированное деревья поиска будем рассматривать ниже.

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

Алгоритм поиска зависит от вида дерева. В идеально сбалансированном дереве поиск приходится проводить обходом вершин дерева в некоторой последовательности. Минимальная длина поиска равна 1, максимальная — n, а средняя — n/2.

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

Включение элемента в дерево. Особенности операций включения зависят от вида дерева.

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

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

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

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

Включение элемента в сбалансированное АВЛ -дерево поиска. Операция включения выполняется в два этапа. Поскольку сбалансированное дерево является частным случаем обычного дерева поиска, то на первом этапе выполняется включение элемента в дерево точно так же, как и при включении в обычное дерево, проходом по пути поиска, получением динамической памяти и формированием в ней новой вершины дерева. Дополнительна новой вершине устанавливается признак её сбалансированности, равный 0, так как новая вершина не имеет поддеревьев.

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

Пример. Пусть имеется дерево с вершинами 3 и 2. Высота поддеревьев| вершины 3 h_L = 1, h_R = 0, признак сбалансированности bal₃=-1, у вершины 2 h_L =h_R = 0, bal₂=0. Добавим вершину 1, у неё h_L =h_R = 0, bal₁=0. Возвращаемся в вершину 2, теперь у нее h_L = 1, h_R= 0. bal₂=-1, но критерий сбалансированности поддерева соблюдается. В вершине 3 стало h_L = 2, h_R = 0, т.е. критерий сбалансированности нарушен, дерево нужно перестраивать. Это достигается так называемым однократным LL-поворотом, в результате получаем сбалансированное дерево с вершиной 2. Необходимые операции балансировки заключаются в обмене указателями t_i и T по кругу по часовой стрелке. Кроме этого необходимо также изменить показатели сбалансированности вершин (см. рис.).

Рис. Балансировка однократным LL-поворотом

Рис. Балансировка однократным RR-поворотом

Более сложные ситуации приводят к двукратным поворот поворот направо и налево (двукратный .RL-поворот) и noeoj налево и направо (двукратный .LR-поворот). Пример двукраг го RL-noeopoma демонстрируется включением в дерево с Bepi нами 5 и 7 новой вершины 6 (рис. 3.12). Возникла несбалансир ванность в вершине 5. Вначале выполняется правый поворот трёх вершин, затем левый поворот двух вершин (7 и 6). При включении в дерево с вершинами 9 и 3 новой верг ны 8 возникает несбалансированность поддерева с корнем Она устраняется двукратным LR-поворотом: сначала лев! поворот трех вершин, затем правый поворот двух вершин 3'| 8 (рис.3.13).

Рис. Балансировка двукратным RL поворотом

Рис. Балансировка двукратным LR поворотом

Порядок построения сбалансированного дерева из исходной последовательности элементов с ключами [8]: 4, 5, 7, 2, 1, 3, 6, можно проследить по следующему рисунку

На рис. приведено сбалансированное АВЛ - дерево, построенное из последовательности ключей 9,17,20,16,12,21,6,3,11, 4,19,14,13,1,5,2,8,18,7,10,15.

Включение элемента в рандомизированное дерево поиска. Напомним, что привставке нового узла в дерево, состоящее из N узлов, вероятность появления нового узла в корне дерева должна быть равна 1/(N + 1). Следовательно, для реализации алгоритма вставки необходимо, во-первых, чтобы каждый узел дерева содержал счетчик узлов в дереве (поддереве), во-вторых, имел генератор случайных чисел и, в-третьих, обеспечил вставку элемента в корень дерева.

Для поддержания счетчика узлов необходимо в структуре элемента дерева предусмотреть соответствующий элемент целого типа. Для определенности примем, что структура элемента имеет вид:
define struct RECORD
{ int DATA;   /* ключ+данные, здесь только ключ */
RECORD *LPTR, *RPTR;   /* указатели на дочерние узлы */
int N; /* счетчик узлов */
int bal;     /* признак сбалансированности в АВЛ-деревьях */
}

Счетчик в заданном узле равен сумме чисел узлов в левом и правом поддеревьях + 1 (сам узел). Тогда счетчик для данного узла Т определится по рекурсивной функции:
int count(RECORT *T)
{if (T==NULL) return 0 ;
else
return (count(T->LPTR) + count(T->RPTR) +1);
}

Для установки счетчиков во всех узлах дерева достаточно выполнить обход всех узлов и при посещении каждого узла выполнить функцию count для этого узла. Установку счетчиков в узлах дерева можно выполнить и в процессе включения элемента в дерево. Это легко достигается в бинарном дереве поиска, но более сложно в АВЛ- и рандомизированном деревьях поиска. В качестве датчика случайных чисел можно использовать стандартную функцию rand().

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

В ротации узла участвуют три связи (указателя): в ротации вправо — указатель на корень, на левый дочерний узел и на правый дочерний узел дочернего узла (на правую внучку); в ротации влево — указатель на корень, на правый дочерний узел и на левый дочерний узел дочернего узла. Ротация выполняется за счет обменов значениями указателей. При ротации вправо правая связь левого дочернего узла становится левой связью старого корня. Правая связь нового корня указывает на старый корень, а указатель на старый корень заменяется указателем на левый корень. При ротации влево левая связь правого дочернего узла становится правой связью старого корня. Левая связь нового корня указывает на старый корень, а указатель на старый корень заменяется указателем на правый корень.

При работе с деревьями к одним элементам обращаются чаще к другим реже. Встречаются ситуации, когда необходимо повторно обращаться к элементам, к которым обращались позже всех. Время доступа к таким элементам можно было бы сократить, поместив их ближе к корню дерева. Для этого достаточно поместить в корень дерева узел, к которому обращались последний раз. Тогда чаще используемые элементы и окажутся вблизи корня.

Вставка элемента в рандомизированное дерево проходит так. Начиная с корня дерева, осуществляется движение по ветвям дерева, как и при вставке в обычное дерево поиска. При посещении каждого узла по очередному случайному числу, выработанному генератором случайных чисел, определяется вероятность вставки элемента именно в этот узел h (корень поддерева) по условию: rand() < RAND_MAX / (N_h + 1), где rand() — случайное число, RAND_MAX — максимальное случайное число, N_h — счетчик узлов в данном узле, ≤ 0.

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

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

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

Левый нисходящий обход Lpreorder — движение сверху от корневой вершины к листьям .

Рис. Левый нисходящий обход дерева:

Левый восходящий обход Lpostorder – снизу вверх, от листьев вверх к корню:

• Левый восходящий обход левого поддерева;
• левый восходящий обход правого поддерева;
• обработка данных в узле.

Левый смешанный обход Linorder — слева направо, от самого левого листа вверх к корню, затем вниз к самому правому листу:

• левый смешанный обход левого поддерева;
• обработка данных в узле;
• левый смешанный обход правого поддерева.

Схема: A. R. В левое поддерево, обработка узла, правое поддерево.

При всех обходах движение по ветвям дерева продолжается до тех пор, пока указатель на узел дерева не станет нулевым.

Применяются и правые обходы: правый нисходящий Rpreorder (R, В, А), правый восходящий Rpostorder (В, A, R), правый смешанный Rinorder (В, R, А). Их алгоритмы получаются из алго¬ритмов левых обходов, если «левый» заменить на «правый». Поэтому их иногда именуют обратными обходами.

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

Функции обхода могут быть как рекурсивными, так и итеративными. Наиболее просто реализуются рекурсивные функции первых шести видов обхода, в которых рекурсивный обход соответствует рекурсивной структуре дерева. В них, естественно, используются системные стеки. В нерекурсивных функциях приходится использовать явный стек, который, как известно, реализует правило LIFO — последним пришел — первым ушел.

Обход по уровням (корень — первый уровень — второй уровень — ...) не соответствует рекурсивной структуре дерева (корень — поддерево — поддерево — ...). В нерекурсивной функции обхода по уровням вместо стека приходится ис-пользовать очередь типа FIFO — первым пришел — первым ушел.

Очевидно, что функция обработки данных в вершине Р(Т) зависит от конкретного применения дерева, в то время как обходы остаются одними и теми же. Бинарные деревья поиска могут быть использованы не только по своему прямому назначению — для поиска данных, но и для их сортировки. Совершая левый смешанный обход бинарного дерева поиска и располагая данные из узлов в том порядке, в котором они встречаются, получим упорядоченную по возрастанию ключей последовательность. Аналогично правый смешанный обход дерева дает последовательность, упорядоченную по убыванию ключей. Поэтому иногда о деревьях поиска говорят, как о деревьях сортировки.

Удаление элемента из дерева. Особенности операции удаления зависят от вида дерева. Удаление элемента из бинарного дерева поиска. Операция удаления элемента из дерева поиска сложнее, чем операция включения элемента. После удаления элемента дерево поиска должно сохранить свое свойство — обеспечение поиска элементов. Действия по удалению определяются тем, в каком месте дерева находится удаляемый элемент. В процедуре удаления различают следующие ситуации.
1.   Элемента с искомым ключом нет, дерево не изменяется, возврат с признаком отсутствия ключа.
2.     Удаляемый элемент — лист, в родительском узле соответствующий указатель на удаляемый элемент обнуляется, память из-под элемента освобождается.
3.    Удаляемый элемент только с одним поддеревом. Корректируются указатели, память освобождается.
4.    Удаляемый элемент имеет два поддерева. В этом случае необходимо спуститься вдоль самой правой ветви левого поддерева до конца и заменить удаляемый элемент конечным элементом с корректировкой указателей. Память освобождается. Вместо эго можно спуститься до конца вдоль самой левой ветви правого поддерева и заменить удаляемый элемент конечным элементом, скорректировать указатели и освободить память.

На примере мы рассмотрим результат удалении узла 13, имеющего два поддерева. Узел 13 заменен узлом 10. Если бы спускались по левой ветви правого поддерева, то узел 13 бы заменен узлом 14.

Рис. Удаление узла из бинарного дерева поиска

Удаление элемента из сбалансированного АВЛ - дерева поиска. Примечательно тем, что дополнительно выполняется балансировка дерева, если сбалансированность была нарушена в результате удаления элемента. При включении элемента нарушение сбалансированности происходило из-за роста высоты, а при удалении это случается из-за ее снижения.

Удаление элемента из рандомизированного дерева поиска. Рандомизированное дерево поиска обладает всеми свойствами бинарного дерева поиска. Поэтому удаление элемента можно осуществлять по тому же алгоритму, что и в обычном бинарном дереве поиска. Тогда удаляемый элемент замещается са-мым правым узлом левого дочернего узла (или самым левым узлом правого дочернего узла). Однако при этом может несколько ослабнуть «случайность» размещения элементов в узлах дерева. Поэтому замещающий узел также можно выбрать как «случайный». Естественно, это усложнит алгоритм удаления элемента. После удаления элемента потребуется корректировка счетчиков узлов.

Сохранение и восстановление бинарного дерева. Выполняя левый нисходящий обход дерева, сохраним ключ и данные каждого узла в файле. Указатели сохранять нет необходимости. Последовательно читая из файла сохраненные ключ и данные узлов, строим бинарное дерево. Дерево восстанавливается в прежнем виде, хотя данные в файле могут сохраниться в последовательности, несколько отличной от исходной. После сохранения в случае необходимости дерево уничтожается.

Уничтожение бинарного дерева. Для уничтожения бинарного дерева достаточно произвести обход дерева и при посещении каждого узла освободить память из-под него. При этом, однако, нельзя допускать того, что будет уничтожен узел, имеющий поддеревья, так как занятая ими память не будет освобождена и станет недоступной для повторного использования. Это требование удовлетворяется при левом или правом восходящем обходе. После освобождения всей занятой памяти указатель дерева необходимо обнулить.