Дерево AVL
-
Определение и свойства дерева AVL
- Дерево AVL — самобалансирующееся бинарное дерево поиска.
- Высоты дочерних поддеревьев отличаются не более чем на единицу.
- Поиск, вставка и удаление занимают O(log n) времени.
- Для вставок и удалений может потребоваться перебалансировка.
-
История и сравнение с красно-черными деревьями
- Изобретено Георгием Адельсоном-Вельским и Евгением Лэндисом в 1962 году.
- Часто сравнивается с красно-черными деревьями, но работает быстрее для интенсивного поиска.
- Оба дерева поддерживают O(log n) время для основных операций.
-
Коэффициент сбалансированности
- Коэффициент баланса узла определяется как разница высот дочерних поддеревьев.
- Узел с коэффициентом баланса < 0 называется левосторонним, с > 0 — правосторонним, с 0 — сбалансированным.
-
Операции с деревом AVL
- Поиск: O(log n) времени, требует функции сравнения.
- Обход: O(n) времени, амортизированная стоимость 2×(n−1)/n.
- Вставка: O(log n) времени, требует отслеживания баланса.
- Удаление: O(log n) времени, требует восстановления баланса.
-
Операции набора и массовые операции
- Определены операции набора: объединение, пересечение и разность.
-
Операции с деревьями AVL
- Вставки и удаления данных требуют вспомогательных операций разделения и объединения.
- Функция Join объединяет два дерева AVL и ключ, создавая новое дерево с элементами из обоих.
- Разделение дерева AVL на два меньших дерева требует вставки ключа и разделения поддеревьев.
-
Реализация на основе соединения
- Объединение, пересечение и разность выполняются рекурсивно и могут выполняться параллельно.
- Сложность операций O(m log(n/m + 1)) для деревьев AVL различных размеров.
-
Восстановление равновесия
- Временная разница в высоте между дочерними поддеревьями может быть исправлена с помощью древовидных поворотов.
- Простое вращение выполняется, когда внутренний дочерний элемент не выше родного элемента.
- Двойное вращение выполняется, когда внутренний дочерний элемент выше родного элемента.
-
Сравнение с другими структурами
- AVL-деревья и красно-черные деревья являются самобалансирующимися бинарными деревьями поиска.
- AVL-деревья более жестко сбалансированы, чем RB-деревья.
- AVL-деревья требуют больше памяти, но более эффективны для вставок и удалений.
-
Стили и форматирование
- Использование различных шрифтов и переносов слов
- Применение различных стилей для цитат и идентификаторов
- Настройка цвета и фона для различных элементов
-
Идентификаторы и блокировки
- Идентификаторы для различных типов блокировок
- Ссылки на изображения для идентификации
- Настройка цвета и размера для идентификаторов
-
Библиографическое описание и ссылки
- Использование различных стилей для библиографического описания
- Настройка шрифта и цвета для ссылок
-
Деревья AVL и их свойства
- Определение μ-сбалансированных деревьев
- Описание свойств деревьев AVL
- Хранение информации о балансе в дочерних узлах
-
Дополнительные материалы
- Ссылки на книги и статьи по теме
- Упоминание о красно-черном дереве и его доказательстве наличия границ
-
Внешние ссылки
- Упоминание о материалах, являющихся общественным достоянием