41. 43. Упорядоченные двоичные деревья. Операции поиска.

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

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

Данные - поле, предназначенное для хранения полезной информации, которая используется для хранения дерева.

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

Над бинарным деревом определены все те же операции, что и над обычными:

1. поиск по заданному значению ключа,

2. вставка в дерево нового данного,

3. удаление из дерева значения.

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

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

Для реализации операции поиска можно использовать как рекурсивный, так и не рекурсивный алгоритм.

42. 44. Включения и удаления элементов из двоичного упорядоченного дерева.

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

Процесс вставки:

1) создается новый узел дерева, куда записывается ключ, данные, а ссылки на левые и правые поддеревья заполняются значением Нил.

2) осуществляется поиск узла дерева, к которому можно подвесить новый узел, так, чтобы упорядоченность дерева не было нарушено. Таковым узлом может быть только терминальный узел.

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

Операции включения выполняется в следующей последовательности:

1. Осуществляется поиск исключающего звена.

2. Если звено найдено, то выполняется операция его удаления из дерева.

На этапе удаления нужной вершины дерева возможны три варианта:

а. Из исключающей вершины не выходит ни одна ветвь. Тогда исключении производиться удалением найденной вершины и записью вместо ссылки на нее предшествующие вершины значению Нил.

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

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

Составил к.ф. - м.н., доцент каф. И и ВМ /В. Сиников/