Двоичные деревья поиска. Основные определения и операции

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

Start – указатель на корень дерева. Work – рабочий указатель. INF – указатель на информационное поле. PLP – указатель на левое поддерево.PRP – указатель на правое поддерево. Work→INF – значение информационного поля Work→PLP – значение указателя на левое поддерево. Work→PRP – значение указателя на правое поддерево. ВП(Work) – процедура выделения памяти. ОП(Work) – освобождение памяти.

Алгоритм поиска.

Процедура Poisk(X,Work)

Пока (Work<>0) и (X<>Work→INF)

Если X< Work→INF, то Work= Work→PLP

Иначе Work= Work→PRP

Конец_Пока

Если X=Work→INF, то «Нашли»

Иначе «Не нашли»

Правильнее две последние строчки заменить на: Если Work=0, то «Не нашли», иначе «Нашли».

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

Алгоритм формирования бинарного дерева поиска, не содержащего дублирования элементов.

Процедура WP(X;Var Work)

Если Work=0, то

ВП(Work)

Work→INF= Х

Work→PLP=0

Work→PRP=0

Конец_Если

Иначе, если Х< Work→INF, то WP(X; Work→PLP)

Иначе, если Х> Work→INF, то WP(X; Work→PRP)

Иначе «Дублирование» Выход

Конец_WP

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

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

В алгоритме удаления элемента из двоичного дерева поиска реализуется три случая:

1. Элемента с ключом Х нет в дереве

2. Элемент с ключом Х имеет не более одного потомка

3. Элемент с ключом Х имеет несколько потомков.

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

Процедура delete(X, Var Work)

Если Work=0, то «Нет элемента. Выход»

Иначе, если Х<Work→INF, то delete(X, Work→PLP)

Иначе, если Х>Work→INF, то delete(X, Work→PRP)

Иначе Начало_Иначе

q= Work

Если q→PRP=0, то Work=q→PLP

Иначе, если q→PLP=0, то Work=q→PRP

Иначе del(q→PLP)

ОП(q)

Конец_иначе

Процедура Del(Var r); если 2 потомка.

Если r→PRP<>0,то del(r→PRP)

Иначе Начало_Иначе

q→INF = r→INF

q = r

r = r→PLP

Конец_Иначе