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

Пример: Необходимо расположить все слова некоторого текста в алфавитном порядке

Для решения данной

Допустим задан текст

«Сэр Исаак Ньютон по секрету признавался друзьям, что он

Текст в алфавитном порядке:

ведет
гравитация
друзьям
знает
Исаак
как
не
но
Ньютон

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

Построение дерева

сэр

Дерево оптимальной структуры:

Ньютон

Высота бинарного дерева

Пусть бинарное дерево содержит элементы:10, 20, 30, 40,

Дерево максимальной высоты

Дерево минимальной высоты

Порядок вставки элементов:
40, 20, 60, 10, 30, 50, 70

Высота бинарного дерева

Высота бинарного дерева зависит от порядка выполнения операций

Цель:

Создание деревьев, не теряющих баланса при выполнении операций вставки и удаления
Эффективность

2-3 дерево

Каждый узел 2-3 дерева содержит одно или два значения
Узлы дерева

2-3 дерево

Принцип упорядоченности для 2-3 дерева:
Для 2-узла – все значения, лежащие

Принцип упорядоченности для 2-3 дерева:

Для 3-узла – упорядоченность означает следующее: Пусть А1

Пример 2-3 дерева

15

21 | 22

28 | 30

5 | 8

4

Пример нарушения структуры 2-3 дерева

15

21 | 22

28 | 30

5 |

2-3 дерево

2-3 дерево не является бинарным
Все листья 2-3 дерева находятся на

Физическое представление 2-3 дерева

15

21

28

5

4

11

16

2

24

10

8

13

Вставка элементов

Вставка элементов осуществляется только в листья
В случае, если после вставки

Вставка элементов

23

Вставка элементов

Вставка элементов

12

Вставка элементов

15

21 | 22

28 | 30

5 | 8

4 |

Вставка элементов

15

21 | 22

28 | 30

5 | 8

4 |

Вставка элементов

15

21 | 22

28 | 30

5 | 8

4 |

Вставка элементов

15

21 | 22

28 | 30

5 | 8

16 | 19

23

Удаление элементов

Находим ближайшее наибольшее значение и заменяем удаляемый узел

Удаление элементов

Склеиваем значения 12 и 13

Удаление элементов

Используем метод переливания

Удаление элементов

2

6

11

12|13

4

7 | 8

0 | 1

Ссылка

Преимущества 2-3 дерева

2-3 дерево всегда сбалансировано
Эффективность алгоритма поиска в таком дереве

2-3-4 деревья

2-3-4 дерево может содержать четырехместные узлы
По сравнению с 2-3 деревом

2-3-4 деревья

2-3-4 деревом высотой h называется дерево, которое пусто
или имеет

2-3-4 деревья

Правила размещения данных

1) K(TL)2) K(TL)

Вставка элементов

Четырехместный узел разделяется сразу после обнаружения, при этом один из

Вставка элементов

Вставка элементов

Вставка элементов

Добавим значение 70

Вставка элементов

Добавим значения 80 и 15

Вставка элементов

Вставка элементов

Разделение четырехместных узлов при вставке

Возможны случаи:
Узел является корнем
Узел имеет двухместого родителя
Узел

Удаление элементов

Находим узел, содержащий данный элемент
Заменяем элемент его симметричным преемником (самый

Удаление элементов

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

Заключение

Достоинства 2-3 и 2-3-4 деревьев заключается в том, что они хорошо