Основные операции с бинарными деревьями

Основные операции с бинарными деревьями.

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

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

Так же как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Обращаясь к бинарному дереву на рис. 8, где R обозначает корень, а А и В левое и правое поддеревья, мы можем определить такие три упорядочения 1. Сверху вниз R, А, В посетить корень до поддеревьев 2. Слева направо A, R, В 3. Снизу вверх А, В, R посетить корень после поддеревьев Обходя дерево на рис. 4 и выписывая символы, находящиеся в узлах, в том порядке, в котором они встречаются, мы получаем следующие последовательности 1. Сверху вниз ab c d ef 2. Слева на право a bc d e f 3. Снизу вверх abc def Мы узнаем три формы записи выражений обход сверху вниз дает префиксную запись, обход снизу вверх постфиксную запись, Рис. 8. Бинарное дерево. а обход слева направо дает привычную инфиксную запись, хотя и без скобок, необходимых для определения порядка выполнения операций. Теперь выразим эти три метода обхода как три конкретные программы с явным параметром t, означающим дерево, с которым они имеют дело, и неявным параметром Р, означающим операцию, которую нужно выполнить с каждым узлом.

Введем следующие определения type ref node node record 2.1 left, right ref end Эти три метода легко сформулировать в виде рекурсивных процедур они вновь служат примером того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. procedure preordert ref begin if t nil then begin Pt preordert .left 2.2 preordert .right end end procedure postordert ref begin if t nil then begin posordert . left postordert .right 2.3 Pt end end procedure inordert ref begin if t nil then begin wordcrt .left Pt 2.4 Inordert .right end end. Отметим, что ссылка t передается как параметр-значение. Это отражает тот факт, что здесь существенна сама ссылка указание на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изменить значение, если бы t передавался как параметр-переменная.

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

Если дерево организовано таким образом, что для каждого узла ti все ключи в левом поддереве, меньше ключа ti, а ключи в правом поддереве больше ключа ti, то это дерево называется деревом поиска.

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

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

S Рис. 9. Дерево поиска с барьером. Так как этот поиск проходит по единственному пути от корня к искомому узлу, его можно запрограммировать с помощью итерации 2.6 function locx integer t ref ref var found boolean begin found false while t . nil Л - found do begin 2.6 if t .key x then found true else if t .key x then t t .left else t .right end loc t end. Функция locx, t имеет значение nil, если в дереве с корнем t не найдено ключа со значением х. Так же как в случае поиска по списку, сложность условия окончания цикла заставляет искать лучшее решение.

При поиске по списку .конце его помещается барьер. Этот прием можно применить в случае поиска по дереву. Использование ссылок позволяет связать все терминальные узлы дерева с одним и тем же барьером. Полученная структура это уже не просто дерево, а скорее, дерево, все листья, которого прицеплены внизу к одному якорю см. рис. 9. Барьер можно также считать общим представлением всех внешних специальных узлов, которыми дополняется исходное дерево см. рис. 3. Полученная в результате упрощенная процедура поиска описана ниже function locx integer t ref ref begin s .key x барьер 2.7 while t .key x do if x t .key then t t .left else t t .right loc t end. Отметим, что если в дереве с корнем t не найдено ключа со значением х, то в этом случае locx, t принимает значение s, т. е. ссылки на барьер.

Ссылка на s просто принимает на себя роль ссылки nil. 2.2.