Деревья бинарного поиска

1.

Деревья бинарного поиска
(Balanced Search Trees)

2.

Таблицы имен
Требование. Гарантии производительности
2-3 деревья, LLRB BSTs, B-деревья

3.

2-3 деревья поиска
(2-3 Search Trees)

4.

2-3 дерево
В каждом узле 1 или 2 ключа
2-узел: один ключ, 2 потомка
3-узел: 2 ключа, 3 потомка
Симметрия. Симметричный обход дает ключи в
порядке возрастания

5.

2-3 дерево
В каждом узле 1 или 2 ключа
2-узел: один ключ, 2 потомка
3-узел: 2 ключа, 3 потомка
Симметрия. Симметричный обход дает ключи в
порядке возрастания
Идеальный баланс. Длина каждого пути от корня
до null-ссылки имеет одинаковую длину

6.

2-3 дерево
Поиск и вставка
Видео 1

7.

Преобразования 2-3 дерева
Разделение 4 -узла (локальное изменение):
константное количество операций

8.

Свойства 2-3 деревьев
Инвариантность. Сохранение симметрии и
идеального баланса

9.

2-3 дерево: производительность

10.

Таблицы имен

11.

2-3 дерево: реализация
Прямая реализация сложна, потому что:
Сложно поддерживать узлы разных типов
Нужны разные интерфейсы сравнений для
узлов
Нужно возвращаться назад для разделения 4узла
Много случаев для разделения разных типов
узлов
Есть путь лучше

12.

Красно-черные деревья бинарного поиска
(red-black BSTs)

13.

Левые красно-черные ДБП
Представить 2-3 деревья как ДБП
Использовать левую ссылку для представления 3узла

14.

Обозначения
Нет узлов с двумя красными ссылками
Каждый путь от корня до null-ссылки имеет
одинаковое количество черных связей (идеальный
черный баланс)
Левые красные ссылки

15.

16.

Реализация поиска в RB BST
Поиск и большинство операций (min, max, floor и
тд.) ничем не отличается от обычного BST (цвет
игнорируется), но работают быстрее из-за лучшего
баланса дерева

17.

RB BST
Цвет связи хранится в потомке

18.

RB BST: левый поворот
Сохраняется симметрия и идеальный баланс

19.

RB BST: левый поворот
Сохраняется симметрия и идеальный баланс

20.

RB BST: правый поворот
Сохраняется симметрия и идеальный баланс

21.

RB BST: правый поворот
Сохраняется симметрия и идеальный баланс

22.

RB BST: изменение цвета
Сохраняется симметрия и идеальный баланс
Разделение 4-узла

23.

RB BST: изменение цвета
Сохраняется симметрия и идеальный баланс
Разделение 4-узла

24.

25.

26.

27.

28.

29.

30.

RB BST
Видео 2

31.

32.

RB BST
Видео 3

33.

Баланс в LLRB дереве
Утверждение. Высота дерева <= 2log2N в худшем
случае
В среднем высота ~ 1,00 log2N

34.

Таблицы имен