Лекция 8

программирования
Часть 2

которые можно сравнивать друг с другом.
-5
7
3
23
28
31
45
25
6
24
26
Каждое левое поддерево хранит элементы,

которые (в некотором смысле) меньше, чем элемент в корне, каждое правое – больше.
Совпадающие значения, как правило, не допускаются.

Стандартные операции:
-поиск элемента по значению
-добавление элемента
-поиск максимального/минимального элемента
-поиск предыдущего/следующего по величине элемента
-удаление элемента
-различные варианты обхода дерева – для его вывода, записи в файл или удаления

int x)
{
TreeNode*cur=root;
while(cur)
{
if (x==cur->data) return 1;

else
if (x > cur->data) cur=cur->right;
else cur=cur->left;
}
return 0;
}
Если число в узле меньше x – ищем в правом поддереве, иначе – в левом.

Если искали число 25

createNode(x);
while(cur)
{
if (x==cur->data)break;
else if (x>cur->data)

{
if(cur->right) cur=cur->right;
else cur->right=createNode(x);
}else
{
if(cur->left) cur=cur->left;
else cur->left=createNode(x);
}
}
return root;
}

5

Если добавили число 5

добавлять элементы в таком порядке:
23, 28, 25, 3, 7, 31,

45, -5, 6, 24, 26
(один из возможных вариантов)

дереву влево, пока это возможно – то есть, существует левый

потомок узла. Последний рассмотренный узел и содержит минимум.

Для максимума тем же способом идём вправо.

Можно искать минимум или максимум не всего дерева, а одного из его поддеревьев.
Жёлтым отмечен максимум левого поддерева.

найдём минимум в правом поддереве элемента (где этот потомок является

корнем)

Так, у элемента с числом 3 на схеме есть правый потомок. Минимум в соответствующем поддереве – число 6.

Если правого потомка нет…

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

На схеме этой ситуации соответствуют элементы 7 и 23.

Поиск предыдущего производится аналогично.

то есть, не имеет потомков.
Решение: В переменную left или right

элемента-отца, где был указатель на удаляемый, записать NULL.

Случай 2. У удаляемого элемента один потомок.
Решение: В переменную left или right элемента-отца, где был указатель на удаляемый, записать адрес потомка удаляемого.

Случай 3. У удаляемого элемента два потомка.
Решение: Найти и «отцепить» любой из элементов: содержащий предыдущее или следующее значение. Поставить его на место удаляемого.

Сам найденный элемент стирается из памяти.

имеет потомков.
23
3
28
-5
7
25
31
45
6
24
26
Удаление элемента 26.
23
3
28
-5
7
25
31
45
6
24

(6) ставится на место удаляемого
23
3
28
-5
6
25
31
45
24
26

элемент (6), или предыдущий (-5) ставится на место удаляемого
23
-5
28
7
25
31
45
24
26
23
6
28
-5
7
25
31
45
24
26
6

добавлять элементы в таком порядке:
23, 28, 25, 3, 7, 31,

45, -5, 6, 24, 26
(один из возможных вариантов)

А если добавлять по возрастанию – получим вырожденное дерево

-5

3

6

7

23

24

25

26

31

45

данными, хранящимися в дереве: иногда дерево оказывается вырожденным.

У сбалансированного (по

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

23

3

28

-5

7

25

31

45

6

24

26

Дерево из предыдущих примеров является сбалансированным.

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

корень и два сбалансированных поддерева; одно с N-1 уровнями, второе

– как минимум с N-2.

Минимальное количество элементов такого дерева составит
k(N)=1+k(N-1)+k(N-2)

Поскольку k(1)=1, k(2)=2, получаем следующие минимальные количества:
N 3 4 5 6 7 8 9 10
k(N) 4 7 12 20 33 54 88 143

Для сравнения, минимальное число элементов полного дерева равно 2N

авторов

1962, «Один алгоритм организации информации»

В оригинальной статье были описаны

алгоритмы добавления, но не алгоритмы удаления.

Г. М.Адельсон-Вельский

Е. М. Ландис

Схемы балансировки при добавлении

левого поддерева, hR – правого.

Пусть, элемент был добавлен в левое

поддерево и увеличил его высоту.




Возможны три случая:

1. hL < hR – после вставки поддеревья выровняются
2. hL = hR – дерево всё ещё сбалансированное
3. hL > hR – (На схеме) после вставки левое поддерево на 2 выше. Требуется балансировка.

левого поддерева. Корень левого поддерева (A) становится корнем дерева
r
2
3
A
1

левого поддерева. Корень правого поддерева левого поддерева (B) становится корнем

дерева

B

3

r

2

4

A

1

B

3

симметрично.


Если расход памяти важен, для хранения состояния узла хватит 2

бит: поддеревья равны, левое выше, правое выше. Функция добавления в этом случае возвращает 1, если высота увеличилась и 0 иначе.
Можно хранить высоты явно. В любом случае нет смысла использовать тип данных больше чем char для их хранения – высота всего дерева невелика даже при большом объёме данных.


Для удаления не придумано ничего лучше, чем попробовать «обратить» балансировку при добавлении. Потенциально это может привести к перестроению дерева на каждом уровне.

Algorithms»
Красно-чёрными деревьями эти сбалансированные деревья назвал Роберт Седжвик (Robert Sedgewick)

в 1978 году, стараясь более наглядно представить алгоритмы.

В работе приведён полный набор алгоритмов – как для добавления, так и для удаления. Их много!

Первая ссылка в статье Байера – на работу Адельсона-Вельского и Ландиса

чёрный.
3. Нулевые указатели считаются листьями, причём листья – чёрные.
4. Потомки

красного узла – чёрные. (Потомки чёрного узла – не обязательно красные).
5. Любой путь от корня поддерева до листа содержит одинаковое число чёрных узлов. (Глубина по чёрным узлам).

Грубая оценка на основании правил 4 и 5 показывает, что длины двух соседних поддеревьев отличаются не более, чем в 2 раза.

Каждый новый узел изначально считается красным. Если это нарушает одно из правил, обычно 4 или 5, производится балансировка…

может создать проблемы.
1. Если это корень всего дерева – меняем

его цвет на чёрный.
2. Если предок – чёрный, всё сбалансировано.
3. Если «отец» и «дядя» - красные

N

P

U

G

N

P

U

G

После проверить, не нарушает ли «дедушка» G одно из правил

4. Добавление в левое поддерево «отца» P. «Отец»-красный, «дядя» U - чёрный

N

P

U

G

U

N

G

P

5. Добавление в правое поддерево «отца» P. «Отец»-красный, «дядя» U - чёрный

N

P

U

G

N

P

U

G

P

U

G

N