Балансировка деревьев: AVL-деревья

4.1 Проблемы несбалансированных деревьев

У обычных (несбалансированных) деревьев при добавлении элементов могут наблюдаться неприятные эффекты.

1. Увеличение высоты дерева:

В несбалансированных деревьях высота может достигать n (где n — количество узлов), что приводит к деградации производительности.

Время выполнения основных операций (поиск, вставка, удаление) в худшем случае становится O(n).

2. Неравномерное распределение узлов:

В несбалансированных деревьях некоторые поддеревья могут содержать значительно больше узлов, чем другие, что приводит к неэффективному использованию памяти и увеличению времени обработки.

3. Ухудшение времени выполнения операций:

В несбалансированных деревьях операции поиска, вставки и удаления требуют большего времени из-за увеличенной высоты дерева.

Пример несбалансированного дерева:

В этом примере дерево фактически превращается в связный список, и время выполнения операций становится линейным.

4.2 Определение AVL-дерева и его свойства

AVL-дерево (названное в честь своих изобретателей, Адельсона-Вельского и Ландиса) — это тип сбалансированного бинарного дерева поиска, в котором для любого узла разница высот его левого и правого поддеревьев не превышает 1.

Свойства AVL-дерева:

1. Сбалансированность:

Разница высот левого и правого поддеревьев любого узла не превышает 1.

Это обеспечивает высоту дерева O(log n), где n — количество узлов, что гарантирует эффективное выполнение операций поиска, вставки и удаления.

2. Бинарное дерево поиска:

AVL-дерево обладает всеми свойствами бинарного дерева поиска: для любого узла все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве больше ключа узла.

3. Автоматическая балансировка:

После каждой операции вставки или удаления выполняется балансировка дерева, чтобы сохранить его свойства.

4.3 Примеры балансировки деревьев

Вращения — это операции, которые выполняются для восстановления баланса в AVL-дереве после вставки или удаления узлов. Существуют четыре типа вращений: левое, правое, левое-правое и правое-левое.

1. Левое вращение (Left Rotation):

В левом вращении узел x поднимается вверх, а его правый дочерний узел y становится его родителем. Левое поддерево y становится правым поддеревом x.

2. Правое вращение (Right Rotation):

В правом вращении узел x поднимается вверх, а его левый дочерний узел y становится его родителем. Правое поддерево y становится левым поддеревом x.

3. Левое-правое вращение (Left-Right Rotation):

Сначала выполняется левое вращение на левом дочернем узле, а затем правое вращение на самом узле.

4. Правое-левое вращение (Right-Left Rotation):

Сначала выполняется правое вращение на правом дочернем узле, а затем левое вращение на самом узле.

4.4 Основные операции в AVL-деревьях

Основные операции в AVL-деревьях включают вставку, удаление и поиск.

1. Вставка (Insertion)

Нужно вставить новый узел в AVL-дерево и сбалансировать его, если требуется.

Шаги:

1. Вставка узла:
   • Начинаем с корня дерева и рекурсивно находим правильное место для нового узла, сравнивая его значение с текущими узлами.
   • Вставляем новый узел в найденное место, как в обычном бинарном дереве поиска.
2. Обновление высот:
   • После вставки обновляем высоты всех узлов по пути от нового узла до корня.
3. Балансировка дерева:
   • Проверяем баланс каждого узла по пути от нового узла до корня.
   • Если баланс какого-либо узла нарушен (разница высот левого и правого поддеревьев больше 1), выполняем соответствующее вращение для восстановления баланса.

Пример:

2. Удаление (Deletion)

Нужно удалить узел из AVL-дерева и сбалансировать его, если требуется.

Шаги:

1. Поиск и удаление узла:
   • Начинаем с корня дерева и рекурсивно находим узел для удаления.
   • Удаляем узел как в обычном бинарном дереве поиска:
     • Если узел является листом, просто удаляем его.
     • Если у узла один потомок, заменяем узел его потомком.
     • Если у узла два потомка, находим наименьший узел в правом поддереве (или наибольший в левом), копируем его значение в удаляемый узел и рекурсивно удаляем наименьший узел в правом поддереве.
2. Обновление высот:
   • После удаления обновляем высоты всех узлов по пути от удалённого узла до корня.
3. Балансировка дерева:
   • Проверяем баланс каждого узла по пути от удалённого узла до корня.
   • Если баланс какого-либо узла нарушен, выполняем соответствующее вращение для восстановления баланса.

Пример:

3. Поиск (Search)

Нужно найти узел с заданным значением в AVL-дереве.

Шаги:

1. Рекурсивный поиск:
   • Начинаем с корня дерева и рекурсивно сравниваем искомое значение с текущими узлами.
   • Если значение меньше текущего узла, переходим к левому поддереву.
   • Если значение больше текущего узла, переходим к правому поддереву.
   • Если значение совпадает с текущим узлом, возвращаем этот узел.

Пример:

2

Задача

Модуль 1: Python Core, 17 уровень, 3 лекция

Недоступна

AVL-дерево

AVL-дерево

Открыть

2

Задача

Модуль 1: Python Core, 17 уровень, 3 лекция

Недоступна

Вставка в AVL-дерево

Вставка в AVL-дерево

Открыть