Алгоритм на псевдокоде

Добавление в СДП (D, *Root)

Описание переменных: Root – указатель на корень дерева.

D – данные, которые необходимо добавить.

P – указатель на указатель на вершину дерева.

p := @Root

DO (*p ≠ NIL)

IF (D < (*p)→Data) p := @((*p)→Left)

ELSEIF (D > (*p)→Data) p := @((*p)→Right)

ELSE OD {данные с ключом D уже есть в дереве}

OD

IF (*p = NIL)

new(*p), (*p)→Data := D,

(*p)→Right := NIL, (*p)→Left := NIL

FI

Пример. Построение дерева для последовательности В 9

1). D = B 2). D = 9

Рисунок 34 Добавление вершины В

Рисунок 35 Добавление вершины 9

Нетрудно видеть, что трудоемкость добавления вершины в случайное дерево поиска сравнима по порядку величины с трудоемкостью поиска в двоичном дереве, т.е. С _ср = О(log n), n→∞.

11.3 Удаление вершины из дерева

Алгоритм удаления вершины с ключом равным X из случайного дерева поиска состоит в следующем. Сначала нужно найти вершину с ключом равными X. Если найденная вершина имеет не более одного поддерева, то её просто удаляем. На рисунке 36 показаны различные варианты расположения вершин. Удаляемая вершина выделена черным цветом.

Рисунок 36 Варианты удаления вершин

Если найденная вершина имеет два поддерева (Рисунок 37), то тогда порядок действий следующий. На место удаляемой вершины ставится наибольшая вершина из левого поддерева (наименьшая из правого поддерева), т.е. самая правая вершина левого поддерева (самая левая из правого поддерева), которая не имеет правого поддерева (левого поддерева) (Рисунок 38).

Рисунок 37 Удаляемая вершина с двумя поддеревьями

Рисунок 38 Порядок изменения указателей при удалении вершины