Способы построения и представления деревьев

     1.7.Сбалансированные деревья поиска

     Длина поиска в двоичном дереве поиска определяется высотой самого дерева. Она для заданного числа элементов п зависит от порядка поступления элементов при построении дерева и может колебаться от log₂n в случае идеальной сбалансированности дерева до (n-1) в случае вырождения дерева в линейный список. Таким образом, затраты на поиск и включение элемента будут порядка от O(log₂n) до O(п).

     При случайном порядке включения элементов в дерево средние затраты на поиск элемента будут l,386* O(log₂n) Увеличение затрат на 39% вполне оправдано более простыми средствами поддержания обычного дерева поиска по сравнению с идеально сбалансированным деревом поиска. Однако при работе с большими деревьями свойство случайности распределения поступающих данных редко. Обычно входные последовательности являются частично упорядоченными (по фамилиям, номенклатурным номерам, квалификационным признакам и т.п.). Для таких ситуаций наиболее подходящими являются так называемые сбалансированные деревья поиска. Рассмотрим два вида таких деревьев: АВЛ-деревья, предложенные в 1962 г. Адельсоном-Вельским и Ландисом, и рандомизированные деревья поиска

     1.7.1.Сбалансированные АВЛ-деревья поиска

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

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

• 0 — высоты правого и левого поддеревьев равны;
• + 1 — высота правого поддерева больше;
• - 1 — высота правого поддерева меньше.

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

     1.7.2.Рандомизированные деревья поиска 

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

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

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

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

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

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

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

     Алгоритм включения в дерево отдельных элементов состоит из трех действий:

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

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

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

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

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

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

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

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

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

     Структура элемента имеет вид

     define struct RECORD

     { int DATA;             /* ключ+данные, здесь только ключ */

     RECORD *LPTR, *RPTR;    /* указатели на дочерние узлы */

     int N; /* счетчик узлов */

     int bal;         /* признак сбалансированности в АВЛ-деревьях */

     };

     Счетчик в заданном узле равен сумме чисел узлов в левом и правом поддеревьях + 1 (сам узел). Тогда счетчик для данного узла Т определится по рекурсивной функции:

     int count(RECORT *Т) {if (T==NULL) return 0 ; else

     return (count(T->LPTR) + count(T->RPTR) +1);

     }

     Для установки счетчиков во всех узлах дерева достаточно выполнить обход всех узлов и при посещении каждого узла выполнить функцию count для этого узла

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

     В ротации узла участвуют три связи (указателя):

• в ротации вправо — указатель на корень, на левый дочерний узел и на правый дочерний узел дочернего узла (на правую внучку);
• в ротации влево — указатель на корень, на правый дочерний узел и на левый дочерний узел дочернего узла.

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

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

     Обработка данных в вершинах дерева.

     Различают два вида обработки:

1. выборочную обработку отдельной вершины;
2. последовательную обработку всех вершин.

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

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

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

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

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

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

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

     Удаление элемента из дерева. Особенности операции удаления зависят от вида дерева.

     Удаление элемента из бинарного дерева поиска.

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

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

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

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