ДЕРЕВО ПОИСКА. ОСНОВНЫЕ ОПЕРАЦИИ, ВЫЧИСЛЕНИЕ СРЕДНЕЙ ДЛИНЫ ПУТИ.

Дерево поиска – все вершины в правом поддереве > x (вершина), все вершины в левом поддереве < x.

В дереве поиска можно найти любой ключ, стартуя с корня и спускаясь в левое или правое поддерево в зависимости только от ключа в текущем узле. Если дерево идеально сбалансировано, то поиск среди n элементов можно выполнить за О(logn). Этим деревья поиска выгодно отличаются от линейных списков.

Операции:

Обход дерева

Обход дерева можно совершать тремя способами:

1. A,L,R(префиксный обход)

2. L,A,R (инфиксный обход)

3. L,R,A (постфиксный обход)

(подробно см. пункт 12)

Поиск вершины

Использование двоичного дерева поиска позволит найти искомую вершину за О(logn), причем высота дерева составляет log₂n.

Добавление

Данная операция соотносится с операцией поиска и они объединяются в одну – поиска-включения. При этом минимальной время – O(log₂n), максимальное - O(n). Аналогом по быстродействию является быстрая сортировка и поиск медианы в ней.

Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.

Иначе сравнить K с ключом корневого узла X.

§ Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.

§ Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

Удаление

Если дерево T пусто, остановиться;

В остальном различают 3 случая:

· Отсутствует компонента с ключом, равным х.

· У компоненты с ключом х не более 1 потомка.

· У компоненты с ключом х 2 потомка. В этой ситуации элемент должен быть заменен либо на самый правый элемент левого поддерева, либо на самый левый элемент правого поддерева.

Вычисление средней длины пути в дереве поиска:

Пусть вершины пронумерованы от 1 до n

– средняя длина пути

		n-i вершин

– левое поддерево, правое поддерево, корень