Организация поиска. Сбалансированные поисковые деревья. АВЛ-дерево

Словарные операции
поиск элемента с заданным ключом х
добавление нового элемента с заданным ключом х
удаление элемента с заданным ключом х
Структуры данных
массив
поисковые деревья
ФПМИ БГУ

поиск элемента с заданным ключом х
произвольный массив
O(n)
ФПМИ БГУ
упорядоченный массив
O(log n)
поисковое дерево
O(h), где h – высота дерева
если дерево не сбалансировано, то h=O(n)

добавление элемента с заданным ключом х
ФПМИ БГУ
произвольный массив
O(1)
упорядоченный массив
O(n)
поисковое дерево
O(h), где h – высота дерева
если дерево не сбалансировано, то h=O(n)

удаление элемента с заданным ключом х
ФПМИ БГУ
произвольный массив
O(n)
упорядоченный массив
O(n)
поисковое дерево
O(h)
если дерево не сбалансировано, то h=O(n)

Сбалансированные деревья

v
w
z
u
x
hu
hw
ФПМИ БГУ

Пример
h=3
h=0
h=0
h=0
h=1
h=2
h=0
k=2
дерево 2-сбалансировано по высоте
ФПМИ БГУ
v
x
z
y
t
w
u

h=0
k=1
дерево сбалансировано
ФПМИ БГУ
h=2
h=0
h=0
h=1
h=0
Пример

Высота полного бинарного дерева h=O(log n), где n – количество вершин.
ФПМИ БГУ
Полное бинарное дерево —
это такое корневое дерево, в котором каждая вершина имеет не более двух сыновей, а заполнение вершин осуществляется в порядке от верхних уровней к нижним, причём на одном уровне заполнение вершинами производится слева направо. Пока уровень полностью не заполнен, к следующему уровню не переходят. Последний уровень в полном бинарном дереве может быть заполнен не полностью.
k=1
полное бинарное дерево всегда сбалансировано

Идеально сбалансированные деревья
ФПМИ БГУ

v
w
z
u
w
cu
cw
ФПМИ БГУ

Пример
k=3
3-идеально сбалансировано по количеству вершин
ФПМИ БГУ
c=7
c=1
c=1
c=1
c=2
c=4
c=1
v
x
y
z
t
w
u

ФПМИ БГУ
Каждое идеально-сбалансированное дерево является сбалансированным. Обратное верно не всегда.
Дерево –сбалансировано,
но не является идеально-сбалансированным

Оценки для бинарных поисковых деревьев
10
18
19
6
2
построение дерева для последовательности из n элементов
поиск элемента с заданным ключом x
добавление элемента с заданным ключом х
в худшем случае высота дерева
h = n-1
обход дерева из n вершин
удаление элемента с заданным ключом x
ФПМИ БГУ
h (=n)
h (=n)
n·h (=n2)
n
h (=n)

ФПМИ БГУ
В 1962 году советские учёные
Г.М.Адельсон-Вельский
и
Е.М.Ландис
предложили структуру данных сбалансированного поискового дерева.

Георгий
Максимович
Адельсон-Вельский
Евгений
Михайлович
Ландис

АВЛ-дерево – это бинарное поисковое дерево, которое является сблансированным по высоте.
2
4
1
3
5
ФПМИ БГУ
АВЛ — аббревиатура, образованная первыми буквами фамилий создателей.

АВЛ-дерево ?
Нет, так как оно не поисковое.
8
4
1
3
5
ФПМИ БГУ
НЕТ

АВЛ-дерево ?
1
4
3
5
ФПМИ БГУ
НЕТ

АВЛ-дерево ?
1
4
5
ФПМИ БГУ
НЕТ

АВЛ-дерево ?
2
4
3
5
0
1
ФПМИ БГУ
НЕТ

АВЛ-дерево ?
2
4
3
5
0
ФПМИ БГУ
ДА

ТЕОРЕМА
Пусть n – число внутренних вершин АВЛ-дерева, h – его высота.
Тогда справедливы следующие неравенства:
ФПМИ БГУ

Для доказательства утверждения оценивают максимальное и минимальное число внутренних вершин.
Максимальное число внутренних вершин
оценивается достаточно просто, так как АВЛ-дерево является бинарным деревом, то подсчитаем максимальное число внутренних вершин у полного бинарного дерева высоты h:
ФПМИ БГУ
20
21
…
…
…
…

Для оценки минимального числа внутренних вершин используются свойства чисел Фибоначчи.
Пусть Nh − число внутренних вершин АВЛ дерева высоты h с минимальным числом внутренних вершин.
ФПМИ БГУ
T0
T1
T2
T3
Nh+1 = Nh + Nh-1 +1
(Nh+1 +1)= ( Nh +1)+ ( Nh-1 +1)
выполним замену переменной:
F'i =Ni +1
F'h+1 =F'h+F'h-1
T1
T2
Какая связь F'i ??? Fi − число Фибоначчи
Поскольку принцип построения деревьев напоминает построение чисел Фибоначчи, то такие деревья обычно называют деревьями Фибоначчи.

ФПМИ БГУ
T0
T1
T2
T3
Fh+2= F'h =Nh +1
Теорема доказана.
Nh = Fh+2 −1

ФПМИ БГУ
Операции поиска, добавления и удаления элементов для АВЛ-деревьев осуществляются точно также, как и для бинарных поисковых деревьев.
Однако, после добавления/удаления элемента может нарушится свойство сбалансированности по высотам и его нужно восстановить.
Восстановление выполняют каждый раз, как только происходит нарушение сбалансированности.

Разбалансировка после добавления элемента
2
4
1
5
6
разбалансировка после добавления 6
ФПМИ БГУ

Разбалансировка после удаления элемента
2
4
1
5
6
разбалансировка после удаления 3
3
0
ФПМИ БГУ

Балансировки
LL поворот (малое правое вращение, одинарный правый поворот)
RR поворот (малое левое вращение, одинарный левый поворот)
LR поворот (большое правое вращение, двойной правый поворот)
RL поворот (большое левое вращение, двойной левый поворот)
ФПМИ БГУ

h-1
h-3
h-1
h
z
C
A
B
z
B
A
C
h-2
h-3
h-3
h-3
h-2
h-2
LL
z
C
B
h-3
A
h-3
h-2
h-3
h-1
+
>
> (≥)
ФПМИ БГУ
LL –поворот
(малое правое вращение)
пусть k1 – вершина на максимальной глубине, для которой произошла разбалансировка и высота ее левого поддерева больше высоты правого поддерева на 2;
пусть k2 – левый сын вершины k1 и высота его левого поддерева (A) больше (или равна) высоты его правого поддерева (В);

LL-поворот
5
3
6
2
4
3
2
5
1
4
6
ФПМИ БГУ
1
LL

RR
h-3
h-1
h-2
h-2
z
C
A
B
z
B
A
C
h-3
h-3
h-2
h-3
>
> (≥)
ФПМИ БГУ
RR –поворот
(малое левое вращение)
пусть k1 – вершина на максимальной глубине, для которой произошла разбалансировка и высота ее правого поддерева больше высоты левого поддерева на 2;
пусть k2 – правый сын вершины k1 и высота его правого поддерева (С) больше (или равна) высоты его левого поддерева (В);

z
C
A
B
z
B
A
D
C
D
h-2
h-3
h-4
h-3
h-1
h-3
h
h-4
h-3
h-3
h-3
h-2
h-2
h-1
>
>
ФПМИ БГУ
RL –поворот
(большое левое вращение)
пусть k1 – вершина на максимальной глубине, для которой произошла разбалансировка и высота ее правого поддерева больше высоты левого поддерева на 2;
пусть k2 – правый сын вершины k1 и высота его левого поддерева (с корнем в вершине k3) больше высоты его правого поддерева (D);
RL

z
C
A
B
z
B
D
A
D
C
>
>
ФПМИ БГУ
LR –поворот
(большое правое вращение)
пусть k1 – вершина на максимальной глубине, для которой произошла разбалансировка и высота ее левого поддерева больше высоты правого поддерева на 2;
пусть k2 – левый сын вершины k1 и высота его правого поддерева (с корнем в вершине k3) больше высоты его левого поддерева (A);
LR

ОЦЕНКИ
Каждый из поворотов (LL, RR, LR, RL) выполняется за O(1), если известна ссылка на разбалансированную вершину.
ФПМИ БГУ

ФПМИ БГУ
После выполнения операции добавления элемента разбалансировка может произойти сразу у нескольких вершин (эти вершины лежат на пути от корня дерева к отцу добавляемой вершины):
сначала необходимо найти ту из разбалансированных вершин, которая наиболее удалена от корня дерева и выполнить для неё один из поворотов;
в результате одной балансировки для всех вершин дерева будет выполняться свойство сбалансированности по высотам.
Таким образом, на весь процесс восстановления свойства сбалансированности будет потрачено время O(log n).

ФПМИ БГУ
Процедура добавления элемента:
поиск отца для вершины x ;
добавление вершины x;
поиск разбалансированнной вершины;
один из поворотов для восстановления свойства сбалансированности по высотам;
будет выполнена за время O(log n).

При удалении элемента x разбалансировка может произойти только у одной вершины:
найдём разбалансированную вершину и выполним для неё поворот;
однако, после поворота может появиться ещё одна разбалансированная вершина и т.д.;
выполнить повторные балансировки; число повторных балансировок ограничено высотой дерева, так как каждый раз балансируемая вершина имеет большую высоту .
Так как удаление элемента из бинарного поискового дерева выполняется за O(log n), а все балансировки будут выполнены за O(log n), то вся процедура удаления элемента − O(log n).
ФПМИ БГУ

ПРИМЕР

Построить АВЛ-дерево для последовательности чисел:
7, 8, 2, 3, 4, 6, 1, 9, 10, 11, 5
построение осуществляется последовательным добавлением элементов;
если на некотором шаге произошла разбалансировка, то для её восстановления выполнить поворот.

7 8 2 3 4 6 1 9 10 11 5
7: 3:
8:
2:
7
7
8
7
8
2
7
8
2
3
ФПМИ БГУ

7 8 2 3 4 6 1 9 10 11 5
4:
7
8
2
3
4
RR
7
3
8
2
4
ФПМИ БГУ

7 8 2 3 4 6 1 9 10 11 5
6:
LR
7
3
8
2
4
4
3
7
2
6
6
8
ФПМИ БГУ

7 8 2 3 4 6 1 9 10 11 5
1:
LL
2
7
1
6
8
7
6
8
3
4
2
1
3
ФПМИ БГУ
4

Построить АВЛ-дерево для последовательности чисел:
7 8 2 3 4 6 1 9 10 11 5
9,10:
RR
2
7
1
6
8
4
3
2
7
1
6
9
4
3
9
10
8
10
ФПМИ БГУ

7 8 2 3 4 6 1 9 10 11 5
11:
RR
2
9
1
7
10
4
3
8
11
2
7
1
6
9
4
3
8
10
11
6
ФПМИ БГУ

7 8 2 3 4 6 1 9 10 11 5
5:
задача решена
RL
2
9
1
7
10
4
3
8
11
6
4
9
2
8
10
7
6
1
11
5
5
3
ФПМИ БГУ

7, 8, 2, 3, 4, 6, 1, 9, 10, 11, 5
4
9
2
8
10
7
6
1
11
5
3
ФПМИ БГУ

Сортировка деревом
Предположим, что на вход поступаю числа, среди которых нет повторяющихся.
1. По последовательности чисел сначала построим АВЛ-дерево.
O(n*log n)
2. Выполним внутренний левый обход построенного дерева.
O(n)
Время работы алгоритма сортировки деревом:
O(n*log n)
ФПМИ БГУ

Абстрактный тип данных: множество (set)
Множество (англ. set) —хранит набор попарно различных объектов без определённого порядка.
Интерфейс множества включает три основные операции:
Insert(x) — добавить в множество ключ x;
Contains(x) — проверить, содержится ли в множестве ключ x;
Remove(x) — удалить ключ x из множества.
ФПМИ БГУ
Для реализации интерфейса множества обычно используются такие структуры данных, как:
сбалансированные поисковые деревья: например, AVL-деревья, 2-3-деревья, красно-чёрные деревья.
хеш-таблицы.
В стандартной библиотеке C++ есть контейнер std::set, который реализует множество на основе сбалансированного дерева (обычно красно-чёрного), и контейнер std::unordered_set, построенный на базе хеш-таблицы.
В языке Java определён интерфейс Set, у которого есть несколько реализаций, среди которых классы TreeSet (работает на основе красно-чёрного дерева) и HashSet (на основе хеш-таблицы).
В языке Python есть только встроенный тип set, использующий хеширование, но нет готового класса множества, построенного на сбалансированных деревьях.

Абстрактный тип данных ассоциативный массив (map)
Ассоциативный массив (англ. associative array), или отображение (англ. map), или словарь (англ. dictionary), —хранит пары вида (ключ, значение), при этом каждый ключ встречается не более одного раза.
Название «ассоциативный» происходит от того, что значения ассоциируются с ключами.
Интерфейс ассоциативного массива включает операции:
Insert(k,v) — добавить пару, состоящую из ключа k и значения v;
Find(k) — найти значение, ассоциированное с ключом k, или сообщить, что значения, связанного с заданным ключом, нет;
Remove(k) — удалить пару, ключ в которой равен k.
ФПМИ БГУ
Данный интерфейс реализуется на практике теми же способами, что и интерфейс множества. Реализация технически немного сложнее, чем множества, но использует те же идеи.
Для языка программирования C++ в стандартной библиотеке доступен контейнер std::map, работающий на основе сбалансированного дерева (обычно красно-чёрного), и контейнер std::unordered_map, работающий на основе хеш-таблицы.
В языке Java определён интерфейс Map, который реализуется несколькими классами, в частности классом TreeMap (базируется на красно-чёрном дереве) и HashMap (базируется на хеш-таблице).
В языке Python очень широко используется встроенный тип dict. Этот словарь использует внутри хеширование.