Алгоритмы и структуры данных. Лекция 7. Деревья поиска

Бинарные деревья
Упорядоченное дерево – это дерево, в котором множество сыновей каждой вершины упорядочено слева направо.
Бинарное дерево – это упорядоченное дерево, в котором:
любой сын – либо левый либо правый,
любой узел имеет не более одного левого и не более одного правого сына.
1
2
3
4
5
7
6
8
9

Обходы деревьев в глубину
Пусть T – дерево, r- корень, v1, v2,…, vn – сыновья вершины r.
Прямой (префиксный ) обход:
посетить корень r;
посетить в прямом порядке поддеревья с корнями v1, v2,…, vn .
Обратный (постфиксный) обход:
посетить в обратном порядке поддеревья с корнями v1, v2,…, vn;
посетить корень r.
Внутренний ( инфиксный) обход для бинарных деревьев:
посетить во внутреннем порядке левое поддерево корня r (если существует);
посетить корень r;
посетить во внутреннем порядке правое поддерево корня r (если существует).

Обходы деревьев в глубину. Пример 1.
Прямой Обратный Внутренний
1
2
6
3
7
8
4
5
9
10
10
4
9
3
5
8
1
1
5
6
7
2
2
10
6
3
7
9
8
4

Обходы деревьев в глубину. Пример 2
+ * a – d e / + f g c - префиксный обход
a d e – * f g + c / + - постфиксный обход
a * (d – e)+ (f + g) / c - инфиксный обход
+
*
/
−
+
c
d
e
f
a
g

Реализация обхода
typedef struct node {
char * word;
struct node * left;
struct node * right;
} tree;
void print_tree ( tree * t )
{
if ( !t )
return;
print_tree( t->left );
printf ( “%s\n”, t->word );
print_tree( t->right );
}

Обход дерева в ширину
- это обход вершин дерева по уровням, начиная от корня, слева направо (или справа налево).
Алгоритм обхода дерева в ширину
Шаг 0:
Поместить в очередь корень дерева.
Шаг 1:
Взять из очереди очередную вершину. Поместить в очередь всех ее сыновей по порядку слева направо (справа налево).
Шаг 2:
Если очередь пуста, то конец обхода, иначе перейти на Шаг 1.

Обход дерева в ширину. Пример
b
h
i
j
k
l
d
e
f
a
g
b
i
h
a
j
k
l
d
e
f
g

Представления деревьев
Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) можно получить, применяя к нему следующие рекурсивные правила:
Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, расположенными в этом порядке (их корни — прямые потомки вершины а), то
Lrep(Т) = а (Lrep (T1), Lrep (Т2) , . . ., Lrep (Тn))
(2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Lrep (Т) = а.
Определение. Правое скобочное представление Rrep(Т) дерева Т:
Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, то
Rrep(Т) = (Rrep(Т1), Rrep(T2), . . ., Rrep (Тn))а.
(2) Если корнем дерева Т служит вершина а, не имеющая
прямых потомков, то Rrep(T) = а.

Скобочные представления деревьев
Lrep(T) = b ( h ( a, j ( d ) ), i ( k ( e, f, g ), l ) )
Rrep(T) = ( ( a, ( d ) j ) h, ( ( e, f, g ) k, l ) i ) b
b
h
i
j
k
l
d
e
f
a
g

Представление дерева списком прямых предков
Составляется список прямых предков для вершин дерева c номерами 1, 2, ..., n (именно в этом порядке). Чтобы опознать корень, будем считать, что его предок—это 0.

Дерево двоичного поиска
Определение. Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v)∈S так, что
l(u) < l(v) для каждого узла u из левого поддерева узла v,
l(w) > l(v) для каждого узла w из правого поддерева узла v,
для любого элемента a ∈S существует единственный узел v , такой что l(v) = a.

Дерево двоичного поиска. Пример
Пусть S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
5
1
7
3
6
10
2
4
8
9

Алгоритм просмотра дерева двоичного поиска
Вход: Дерево T двоичного поиска для множества S, элемент a.
Выход: true если a∈S, false - в противном случае.
Метод: Если T = ∅, то выдать false, иначе выдать ПОИСК (a, r), где r – корень дерева T.
функция ПОИСК (a, v) : boolean
{
если a = l(v) то выдать true
иначе
если a < l(v) то
если v имеет левого сына w
то выдать ПОИСК (a, w)
иначе выдать false;
иначе
если v имеет правого сына w
то выдать ПОИСК (a, w)
иначе выдать false;
}

Пример построения дерева двоичного поиска
Пусть на вход подаются числа в следующем порядке:
5, 1, 7, 6, 3, 2, 10, 8, 4, 9
5
1
7
3
6
10
2
4
8
9

Операции нахождения минимума и максимума
min ( v )
v ← root( T );
while left(v) ≠ NIL
v ← left(v)
return v
max ( v )
v ← root(T);
while right(v) ≠ NIL
v ← right(v)
return v
5
1
7
3
6
10
2
4
8
9

Операция поиска следующего
successor (x)
if right[x] ≠ NIL then
return min (right [x])
y ← p[x]
while y ≠ NIL and x = right [y]
do
x ← y
y ← p[y]
return y
5
1
7
3
6
10
2
4
8
9

Операция удаления элемента из дерева поиска
Delete(T, z)
if left[z] = NIL or right[z] = NIL
then y ← z
else y ← successor (z)
if left[y] ≠ NIL
then x ← left[y]
else x ← right[y]
if x ≠ NIL
p[x] ← p[y]
if p[y] = NIL
then root[T] ← x
else if y = left[p[y]]
then left[p[y]] ← x
else right[p[y]] ← x
if y ≠ z
then key[z] ← key[y]
Копирование сопутствующих данных в z
return y

Пример удаления элемента из дерева поиска

Пример удаления элемента из дерева поиска (окончание)

Теорема (Т. Кормен и др.)
Математическое ожидание высоты случайного бинарного дерева поиска с n ключами равно O(log2 n)

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

Вставка элемента в сбалансированное дерево
Пусть r – корень, L – левое поддерево, R – правое поддерево. Предположим, что включение в L приведет к увеличению высоты на 1.
Возможны три случая:
hL = hR
hL < hR
hL > hR →нарушен принцип сбалансированности, дерево нужно перестраивать
r
L
R
hL
1
hR

Вставка в левое поддерево
A
B
3
2
1
A
B
3
2
1

Вставка в правое поддерево
A
B
3
2
1
С
4
A
3
2
1
С
4
B

Пример построения АВЛ-дерева

Красно-чёрное дерево (Red-Black-Tree, RB-Tree)
Красно-чёрное дерево обладает следующими свойствами.
Каждый узел либо красный либо чёрный
Все листья черны.
Корень дерева – чёрный
Все сыновья красных узлов черны.
Для каждого узла все пути от него до листьев, являющихся его потомками, содержат одно и то же количество черных узлов.
Для корня число чёрных узлов до листьев называется чёрной высотой дерева.
Для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных (NIL).

Пример

Свойства красно-чёрного дерева
1. Если h - чёрная высота дерева, то количество листьев не менее 2h − 1.
2. Если h - высота дерева, то количество листьев не менее 2(h−1)/2.
3. Если количество листьев N, высота дерева не больше 2log2(N + 1)

Повороты
Left_Rotate(T, x)
y ← right[x]
right[x] ← left[y]
if left[y] ≠ nil [T]
then p[left[y]] ← x
p[y] ← p[x]
if p[x] = nil [T]
then root[T] ← y
else if x = left[p[x]]
then left[p[x]] ← y
else right[p[x]] ← y
left[y] ← x
p[x] ← y

Операция вставки
Чтобы вставить узел, мы сначала
ищем в дереве место, куда его следует добавить.
Новый узел всегда добавляется как лист, поэтому оба его потомка являются NULL-узлами и предполагаются черными.
После вставки красим узел в красный цвет.
После этого применяем процедуру Fixup:
Fixup (T, z)
while color[p[x]] = RED
do if p[z] = left[p[p[z]]]
then y ←right[p[p[z]]]
if color [y] = RED //Случай 1
then [p[z]] ← BLACK
color [p[p[z]]] ← RED
z ←p[p[z]]
else if z = right[p[z]] // Случай 2
then z ←p[z]
Left_Rotate (T, z)
color[p[z]] ← BLACK // Случай 3
color [p[p[z]]] ← RED
Right_Rotate(T, p[p[z]])
else (симметрично с then)
color[root[T]] ← RLACK

Красный предок, красный «дядя» – случай 1
Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел C), поскольку он может оказаться красным.

Красный предок, черный «дядя» - случаи 2 и 3

Пример
Случай 1
Случай 2

Пример, окончание
Случай 2
Случай 3

Удаление узла
Если удаляемый узел красный все правила сохраняются и все прекрасно.
Если же удаляемый узел черный, требуется значительное количество кода, для поддержания дерева частично сбалансированным.
Как и в случае вставки в красно-черное дерево, здесь также существует несколько различных случаев.

Сравнение с АВЛ-деревом
Пусть высота дерева h, минимальное количество листьев N.
Тогда:
для АВЛ-дерева N(h) = N(h − 1) + N(h − 2).
Поскольку N(0) = 1, N(1) = 1, N(h) растёт как последовательность Фибоначчи, следовательно, N(h) = Θ(λh), где
для красно-чёрного дерева
Следовательно, при том же количестве листьев красно-чёрное
дерево может быть выше АВЛ-дерева, но не более чем
раз.

Поиск, вставка, удаление
Поиск. Поскольку красно-чёрное дерево, в худшем случае, выше, поиск в нём медленнее, но проигрыш по времени не превышает 40%.
Вставка. Вставка требует до 2 поворотов в обоих видах деревьев. Однако из-за большей высоты красно-чёрного дерева вставка может занимать больше времени.
Удаление. Удаление из красно-черного дерева требует до 3 поворотов, в АВЛ-дереве оно может потребовать числа поворотов до корня. Поэтому удаление из красно-чёрного дерева быстрее, чем из АВЛ-дерева.
Память. АВЛ-дерево в каждом узле хранит высоту (целое число). Красно-чёрное дерево в каждом узле хранит цвет (1 бит). Таким образом, красно-чёрное дерево может быть экономичнее.

Splay деревья
Сплей-дерево (Splay-tree) — это двоичное дерево поиска.
Оно позволяет находить быстрее те данные, которые использовались недавно.
Относится к разряду сливаемых и самобалансирующихся деревьев.
Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Основная операция Splay(Tree, x):
x становится корнем
Treal = Θ(depth(x))
Tamort = O(log(n))

Splay(Tree, x)
Zig
Если p — корень дерева с сыном x, то совершаем один поворот вокруг ребра (x, p), делая x корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина x была нечетной.

Splay(Tree, x)
Zig-Zig
Если p — не корень дерева, а x и p — оба левые или оба правые дети, то делаем поворот ребра (p, g), где g отец p, а затем поворот ребра (x, p).

Splay(Tree, x)
Zig-Zag
Если p — не корень дерева и x — левый ребенок, а p — правый, или наоборот, то делаем поворот вокруг ребра (x, p), а затем поворот нового ребра (x, g), где g – бывший родитель p.

Операции
Find (Tree, x)
Эта операция выполняется как для обычного бинарного дерева, только после нее запускается операция Splay.
Merge (Tree1, Tree2)
У нас есть два дерева Tree1 и Tree2, причём подразумевается, что все элементы первого дерева меньше элементов второго.
Запускаем Splay от самого большого элемента в дереве Tree1 (пусть это элемент i). После этого корень Tree1 содержит элемент i, при этом у него нет правого ребёнка. Делаем Tree2 правым поддеревом i и возвращаем полученное дерево.
Split (Tree, x)
Запускаем Splay от элемента x и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем x.
Add (Tree, x)
Запускаем Split(Tree, x), который нам возвращает деревья Tree1 и Tree2, их подвешиваем к x как левое и правое поддеревья соответственно.
Remove(Tree, x)
Запускаем Splay от x элемента и возвращаем Merge от его детей.

Анализ Splay
Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов.
Потенциалом рассматриваемого дерева назовём сумму рангов его вершин.
Ранг вершины — r(x) = log2w(x),
w(x) — количество вершин в поддереве с корнем x.
Лемма
Амортизированное время операции Splay вершины x в дереве с корнем t не превосходит
3r(t) – 3r(x) +1

Доказательство леммы
Пусть r’ и r — ранги вершин после шага и до него соответственно, p — предок вершины x, а g — предок p, если есть.
Zig. Выполнен один поворот ⇒
Tamort = 1 + r’(x) + r’(p) – r(x) – r(p)
Ранг p уменьшился ⇒Tamort ≤ 1 + r’(x) – r(x) .
Ранг x увеличился ⇒ r’(x) – r(x) ≥ 0 ⇒
Tamort ≤ 1 + 3r’(x) – 3r(x) .

Доказательство леммы - Zig-zig.