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

Удаление из СДП (Х, *Root)

Обозначения

p := @Root

DO (*p ≠ NIL)

IF ((*p)→Data < X) p := @((*p)→Right)

ELSEIF ((*p)→Data > X) p := @((*p)→Left)

ELSE OD

FI

OD

IF (*p ≠ NIL)

q := *p

IF (q→Left = NIL) *p := q→Right

ELSEIF (q→Right = NIL) *p :=q→Left

ELSE r := q→Left, s := q

DO (r→Right ≠ NIL)

s := r, r := r→Right

OD

s→Right := r→Left 1)

r→Left := q→Left 2)

r→Right := q→Right 3)

*p := r 4)

FI

dispose(q)

FI

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

11.4 Варианты заданий

1. Написать процедуру включения нового элемента в случайное дерево поиска.

2. Определить необходимое количество операций для включения элемента в дерево. Сравнить эту величину с высотой дерева.

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

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

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

6. Проверить, является ли построенное случайно дерево деревом поиска с помощью логической функции.

7. Сделать обход слева направо для построенного случайного дерева. Подтвердить, что оно является деревом поиска.

8. Написать процедуру графического изображения СДП.

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

10. Построить случайное дерево поиска и ИСДП для одних и тех же данных. Определить высоты построенных деревьев и найти отношение высот. Сравнить полученную величину с теоретической оценкой.

12. сбалансированные по высоте деревья (АВЛ-ДЕРЕВЬЯ)

12.1 Определение и свойства АВЛ-дерева

Как было показано выше, ИСДП обеспечивает минимальное среднее время поиска. Однако перестройка дерева после случайного включения вершины – довольно сложная операция. СДП дает среднее время поиска на 40 % больше, но процедура построения достаточно проста. Возможное промежуточное решение – введение менее строгого определения сбалансированности. Одно из таких определений было предложено Г. М. Адельсон – Вельским и Е. М. Ландисом (1962).

Дерево поиска называется сбалансированным по высоте, или АВЛ – деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.

На рисунке 39 приведены примеры деревьев, одно из которых является АВЛ-деревом, а другое – нет. В выделенной вершине нарушается баланс высот левого и правого поддеревьев.

Рисунок 39 Пример АВЛ-дерева и не АВЛ-дерева

Заметим, что ИСДП является также и АВЛ – деревом. Обратное утверждение не верно.

Адельсон – Вельский и Ландис доказали теорему, гарантирующую, что АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин:

log(n+1) ≤ h_АВЛ(n) < 1,44 log(n+2) – 0,328 при n®¥.

Таким образом, лучший случай сбалансированного по высоте дерева – ИСДП, худший случай – плохое АВЛ – дерево. Плохое АВЛ – деревоэто АВЛ-дерево, которое имеет наименьшее число вершин при фиксированной высоте. Рассмотрим процесс построения плохого АВЛ-дерева. Возьмём фиксированную высоту h и построим АВЛ – дерево с минимальным количеством вершин. Обозначим такое дерево через T_h. Ясно, что Т₀ – пустое дерево, Т₁ – дерево с одной вершиной. Для построения Т_h при h > 1 будем брать корень и два поддерева с минимальным количеством вершин.

Рисунок 40 Деревья Фибоначчи

Одно поддерево должно быть высотой h–1, а другое высотой h–2. Поскольку принцип их построения очень напоминает построение чисел Фибоначчи, то такие деревья называют деревьями Фибоначчи: T_h = < T_h-1, x, T_h-2 >. Число вершин в T_h определяется следующим образом:

n₀ = 0, n₁ = 1, n_h = n_h-1 + 1 + n_h-2

12.2 Повороты при балансировке

Рассмотрим, что может произойти при включении новой вершины в сбалансированное по высоте дерево. Пусть r – корень АВЛ-дерева, у которого имеется левое поддерево (Т_L) и правое поддерево (T_R). Если добавление новой вершины в левое поддерево приведет к увеличению его высоты на 1, то возможны три случая:

1) если h_L = h_R, то Т_L и T_R станут разной высоты, но баланс не будет нарушен;

2) если h_L < h_R, то Т_L и T_R станут равной высоты, т. е. баланс даже улучшится;

3) если h_L > h_R, то баланс нарушиться и дерево необходимо перестраивать.

Введём в каждую вершину дополнительный параметр Balance (показатель баланса), принимающий следующие значения:

-1, если левое поддерево на единицу выше правого;

0, если высоты обоих поддеревьев одинаковы;

1, если правое поддерево на единицу выше левого.

Если в какой-либо вершине баланс высот нарушается, то необходимо так перестроить имеющееся дерево, чтобы восстановить баланс в каждой вершине. Для восстановления баланса будем использовать процедуры поворотов АВЛ-дерева.

Рисунок 41 LL - поворот