|
Бинарные деревья часто используются для представления множества объектов, среди которых идет поиск по уникальному значению некоторого атрибута, называемого ключом. При этом на множестве объектов определенно особое отношение порядка - дихотомия, заключающееся в поэтапном разбиении множества информационных полей объектов на два непересекающихся подмножества. Дихотомическим деревом (деревом поиска) называется бинарное дерево, организованное так, что для каждого узла, имеющего ключ Т, справедливо утверждение о том, что в его левом поддереве содержатся узлы с ключами, меньшими T, а в его правом поддереве содержатся узлы с ключами, большими T.
Поиск в дихотомическом дереве узла с заданным значением ключа осуществляется на основе сравнения заданного ключа с ключом корня. Единственное сравнение позволяет перейти к левому или к правому поддереву корня. Если дихотомическое дерево является сбалансированным, то поиск узла с заданным значением ключа требует не более чем [log2 N]+1 сравнений, где N – количество узлов дихотомического дерева.
Включение в дихотомическое дерево узла с заданным значением ключа производится следующим образом: если поиск узла привел в тупик (т.е. к пустому поддереву, обозначенному ссылкой со значением NIL), то новый узел необходимо включить в дерево на место пустого поддерева. Таким образом, узел включается в дихотомическое дерево всегда в качестве листа.
Если корневой узел не содержит искомого ключа, процедура рекурсивно вызывает саму себя для продолжения поиска либо в правой, либо в левой половине дерева. В том случае, если достигнут конец ветви и не обнаружен искомый ключ, создается новый узел с этим значением ключа. Рекурсия заканчивается, когда искомый ключ найден (при этом выдается сообщение о невозможности повторного включения узла) или достигнут конец ветви (при этом новый узел включается в дерево).
Какой алгоритм обхода лежит в основе процедуры включения узла в дихотомическое дерево?
При построении дихотомического дерева из N узлов на каждом из N шагов цикла осуществляется вставка узла с заданным значением ключа (вызов процедуры Ins_Node). Поэтому сложность создания дихотомического дерева из N узлов оценивается как N * log2N операций.
При удалении узла, с заданным значением ключа из дихотомического дерева различают три случая:
1. узла с заданным значением ключа в дереве нет.
2. узел с заданным значением ключа имеет не более одного потомка. В этом случае исключаемый узел заменяется своим потомком.
3. Узел с заданным значением ключа имеет двух потомков. В этом случае исключаемый узел заменяется либо на самый правый узел его левого поддерева, имеющий не более одного потомка, либо на самый левый узел его правого поддерева, имеющий не более одного потомка.
Разрушение бинарного дерева любого вида заключается в последовательном освобождении участков памяти, в которых размещены элементы хранения узлов с возвратом их в кучу. В результате разрушения дерево становится пустым.
Какой алгоритм обхода необходимо использовать для разрушения бинарного дерева?
|
