ЛЕКЦИЯ 16. ДВОИЧНЫЕ ДЕРЕВЬЯ ПОИСКА

Цели и задачи лекции: ознакомиться с двоичными деревьями поиска

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

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

Рис.. Путь поиска ключа по значению “23”

Рис. Идеально сбалансированное двоичное дерево

Применение деревьев как объектов с динамической структурой особенно полезно, если допускать выполнение не только операции поиска по значению ключа, но и операций включения новых и исключения существующих ключей. Если не принимать во внимание потенциальное желание поддерживать идеальную балансировку дерева, то процедуры включения и исключения ключей очень просты. Для включения в дерево вершины с новым ключом x по общим правилам поиска ищется листовая вершина, в которой находился бы этот ключ, если бы он входил в дерево. Возможны две ситуации: (a) такая вершина не существует; (b) вершина существует и уже занята, т.е. содержит некоторый ключ y. В первой ситуации создается недостающая вершина, и в нее заносится значение ключа x. Во второй ситуации после включения ключа x эта вершина в любом случае становится внутренней, причем если x > y, то ключ x заносится в новую листовую вершину - правого сына y, а если x < y - то в левую. Четыре потенциально возможных случая проиллюстрированы на рисунке 4.9.

(a)

(b)

(c)

(d)

(e)

При выполнении исключения ключа из дерева также прежде всего выполняется поиск ключа. Если ключ обнаруживается, то возможны следующие случаи: (a) ключ содержится в листовой вершине, у вершины-отца которой имеются два сына; (b) ключ содержится в листовой вершине, являющей единственным сыном своего отца; (c) ключ содержится во внутренней вершине, имеющей только левого или только правого сына; (d) ключ содержится во внутренней вершине, имеющей и левого, и правого сыновей. В случае (a) соответствующая листовая вершина ликвидируется, а у ее отца остается только один сын. В случае (b) листовая вершина ликвидируется, а ее отец становится новой листовой вершиной. В случае (c) внутренняя вершина ликвидируется, и ее место занимает единственный сын (он может быть внутренней или листовой вершиной. В случае (d) внутренняя вершина ликвидируется, и заменяется на листовую или внутреннюю вершину, достигаемую по самому правому пути от левого сына внутренней вершины. Эта вершина наследует левого и правого сыновей ликвидируемой вершины.

(a)

(b)

(c)

(d)

(e)

(f)
Рис. Исключение ключа из двоичного дерева

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