2014-02-24
2884
Рис. 72. Исключение узлов из дихотомического дерева
Рис. 71. Вырожденное дихотомическое дерево
Рис. 70. Дихомические деревья
Поиск в дихотомическом дереве узла с заданным значением ключа осуществляется на основе сравнения заданного ключа с ключом корня. Единственное сравнение позволяет перейти к левому или к правому поддереву корня. Если дихотомическое дерево является сбалансированным, то поиск узла с заданным значением ключа требует не более чем [log2 N]+1 сравнений, где N – количество узлов дихотомического дерева. В частном случае, когда множество ключей является линейно упорядоченным, дихотомическое дерево фактически вырождается в линейный список (рис. 71). В этом случае поиск среди N узлов выполняется максимум за N сравнений, а в среднем – за N / 2 сравнений.
 |
Структура дихотомического дерева определяется последовательностью задания ключей. Последовательности задания ключей для
¨ дерева рис. а) - 150, 70, 300, 100, 30, 200, 50;
¨ дерева рис. б) - 100, 50, 30, 70, 200, 150, 300;
¨ дерева рис. - 300, 200, 150, 100, 70, 50, 30.
Включение в дихотомическое дерево узла с заданным значением ключа производится следующим образом: если поиск узла привел в тупик (т.е. к пустому поддереву, обозначенному ссылкой со значением NIL), то новый узел необходимо включить в дерево на место пустого поддерева. Таким образом, узел включается в дихотомическое дерево всегда в качестве листа.
| Procedure Ins_Node(var root: PDtree; | { root – указатель на корень дерева } | |||||
| k: word); | { k – ключ вставляемого узла } | |||||
| begin | ||||||
| if root = nil then begin | { дерево пусто – вставка узла в качестве листа } | |||||
| new(root); | { создать элемент хранения узла } | |||||
| readln(root^. Info); | { заполнить информационное поле узла } | |||||
| root^.key:=k; | { заполнить поле ключа } | |||||
| root^.left:=nil; root^.right:=nil; | { заполнить ссылки на поддеревья } | |||||
| end | ||||||
| else | { дерево не пусто – продолжить поиск: } | |||||
| if k < root then Ins_Node(root^.left,) | { поиск в левом поддереве } | |||||
| else if k > root then Ins_node(root^.right) | { поиск в правом поддереве} | |||||
| else writeln(‘узел с ключом’, k, ‘уже есть в дереве’) | { ключ должен быть } | |||||
| end; | { уникальным } | |||||
Если корневой узел не содержит искомого ключа, процедура рекурсивно вызывает саму себя для продолжения поиска либо в правой, либо в левой половине дерева. В том случае, если достигнут конец ветви и не обнаружен искомый ключ, создается новый узел с этим значением ключа. Рекурсия заканчивается, когда искомый ключ найден (при этом выдается сообщение о невозможности повторного включения узла) или достигнут конец ветви (при этом новый узел включается в дерево).
Какой алгоритм обхода лежит в основе процедуры включения узла в дихотомическое дерево?
При построениидихотомического дерева из N узлов на каждом из N шагов цикла осуществляется вставка узла с заданным значением ключа (вызов процедуры Ins_Node). Поэтому сложность создания дихотомического дерева из N узлов оценивается как N * log2N операций.
При удаленииузла, с заданным значением ключа из дихотомического дерева различают три случая:
1. узла с заданным значением ключа в дереве нет.
2. узел с заданным значением ключа имеет не более одного потомка. В этом случае исключаемый узел заменяется своим потомком.
3. Узел с заданным значением ключа имеет двух потомков. В этом случае исключаемый узел заменяется либо на самый правый узел его левого поддерева, имеющий не более одного потомка, либо на самый левый узел его правого поддерева, имеющий не более одного потомка.
Пример исключения узлов из дихотомического дерева приведен на рис. 72.
 |
Разрушение бинарного дерева любого вида заключается в последовательном освобождении участков памяти, в которых размещены элементы хранения узлов с возвратом их в кучу. В результате разрушения дерево становится пустым.
Какой алгоритм обхода необходимо использовать для разрушения бинарного дерева?
Дерево выражений – бинарное дерево, в корневых узлах которого хранятся признаки операций, а в терминальных узлах – операнды выражения (переменные или константы). Дерево выражений представлено на рис. 73.
 |
