Продвинутые древовидные структуры

Освоив базовые древовидные структуры, такие как бинарные деревья и бинарные деревья поиска, мы собираемся вступить в более широкую и эффективную область — продвинутые древовидные структуры.

Если базовые деревья — это обычные дороги в мире структур данных, то продвинутые древовидные структуры — это тщательно спроектированные автомагистрали и развязки. Благодаря продуманным правилам балансировки и стратегиям хранения они обеспечивают превосходную производительность даже при огромных объёмах данных или частых операциях.

В этом разделе будут представленыAVL-дерево、красно-чёрное дерево、B-деревоиB+ деревоЭти четыре классические продвинутые древовидные структуры.

Зачем нам нужны продвинутые древовидные структуры?

Прежде чем углубляться, давайте сначала зададим вопрос: имея под рукой эффективное двоичное дерево поиска (BST), зачем нам всё ещё нужны более сложные деревья?

Представьте, что у вас есть библиотека и вы используете BST для хранения книг, отсортированных по названию. Если вы вставляете книги одну за другой в алфавитном порядке (например:A..., B..., C...), дерево вырождается в цепочку (похожую на связный список). В этот момент время поиска книги меняется с идеальногоO(log n)Деградация в наихудшем случаеO(n), крайне низкая эффективность.

Рисунок: схема двоичного дерева поиска, вырождающегося в связный список при вставке упорядоченных данных, из-за чего производительность поиска снижается.

Продвинутые древовидные структуры (самобалансирующиеся деревья) были созданы именно для решения этой проблемы.. Они автоматически корректируют форму дерева при вставке или удалении узлов, поддерживают дерево сбалансированным, тем самым гарантируя, что временная сложность таких операций, как поиск, вставка и удаление, всегда остаётся наO(log n)уровне.

АВЛ-дерево: страж баланса по высоте

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

Основная идея AVL-дерева очень проста:Для любого узла дерева разность высот его левого и правого поддеревьев не может превышать 1.。

Ключевое понятие: коэффициент баланса

У каждого узла естькоэффициент баланса, и формула его вычисления такова:Balance factor = height of left subtree - height of right subtreeВ AVL-дереве коэффициент баланса каждого узла может быть только -1, 0 или 1.

Дисбаланс и корректировка поворотами

После вставки или удаления узла, если коэффициент баланса узла становится 2 или -2, дерево становится несбалансированным. Чтобы восстановить баланс, AVL-дерево использует четыре операцииповоротадля корректировки:

  • Левый поворот: обрабатывает случай дисбаланса «правый-правый».
  • Правый поворот: обрабатывает случай дисбаланса «левый-левый».
  • Левый-правый поворот: сначала левый поворот, затем правый поворот, обрабатывает случай дисбаланса «левый-правый».
  • Правый-левый поворот: сначала правый поворот, затем левый поворот, обрабатывает случай дисбаланса «правый-левый».

Пример

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1  # Высота узла, изначально 1
        self.left = None
        self.right = None

def get_height(node):
    """Получить высоту узла (обработать пустые узлы)"""
    return node.height if node else 0

def get_balance_factor(node):
    """Вычислить коэффициент баланса узла"""
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def right_rotate(y):
    """
Выполните правый поворот поддерева с корнем в y
         y                              x
        / \                          /   \
x T4 правый поворот (y) z y
      / \      - - - - - - - ->    / \  / \
     z   T3                       T1  T2 T3 T4
    / \
  T1   T2
    """
    x = y.left
    T3 = x.right

    # Выполните поворот
    x.right = y
    y.left = T3

    # Обновите высоты (сначала нужно обновить высоту y, затем высоту x)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))

    # Вернуть новый корневой узел
    return x

# Функция левого поворота симметрична правому повороту; подробная реализация здесь опущена
def left_rotate(x):
    """Выполните левый поворот поддерева с корнем в x (логика симметрична правому повороту)"""
    pass

Сводка характеристик AVL-дерева

Особенности Описание
Строго сбалансированное Условие баланса строгое (разница высот ≤ 1), высота дерева наиболее близка к log n, а производительность поиска отличная.
Частые корректировки После вставки/удаления для восстановления баланса может потребоваться несколько поворотов снизу вверх.
Применимые сценарии Подходитдля сценариев с большим количеством запросов и меньшим числом вставок/удалений, например для среднего слоя индексов баз данных или таблиц поиска в памяти.

Красно-чёрное дерево: король инженерной практики

Красно-чёрное дерево — это ещё одно самобалансирующееся двоичное дерево поиска. Оно идёт на некоторые «компромиссы» по сравнению с AVL-деревом. Вместо стремления к абсолютному балансу, как в AVL-дереве, оно использует набор более мягких правил для обеспечения приблизительного баланса, тем самым уменьшая количество поворотов при вставке/удалении и достигая лучших инженерных результатов в общей производительности. В JavaTreeMap、TreeSetи C++ STLmap、setВсе их низкоуровневые реализации используют красно-чёрные деревья.

Пять основных правил красно-чёрных деревьев

Красно-чёрные деревья поддерживают баланс, добавляя к узлам атрибут цвета (красный или чёрный) и соблюдая следующие правила:

  • Каждый узел является либо красным, либо чёрным.
  • Корневой узел является чёрным.。
  • Все листовые узлы (пустые узлы NIL) чёрные.
  • Оба потомка красного узла должны быть чёрными.(то есть не может быть подряд идущих красных узлов).
  • Все пути от любого узла к каждому из его листовых узлов содержатодинаковое количествочёрных узлов.

Правила 4 и 5 — ключ к балансировке красно-чёрного дерева. Правило 5 гарантирует, что никакой путь не более чем вдвое длиннее любого другого пути, что обеспечивает приблизительный баланс.

Стратегия корректировки при вставке

При вставке нового узла мы всегда сначала окрашиваем егокрасным(чтобы не нарушить правило 5). Если это вызывает конфликт (главным образом нарушение правила 2 или правила 4), его нужно скорректировать с помощьюизменения цветаиповоротадля корректировки. Основная идея корректировки — непрерывно "поднимать" конфликт (красный) к корню, пока его не удастся разрешить с помощью перекрашивания или поворота.

Пример

class RBNode:
    RED = "RED"
    BLACK = "BLACK"

    def __init__(self, key):
        self.key = key
        self.color = self.RED  # Новый узел изначально красный
        self.left = None
        self.right = None
        self.parent = None  # Красно-чёрному дереву нужен указатель на родителя

def insert_fixup(tree, node):
    """Восстановление свойств красно-чёрного дерева после вставки (упрощённое описание логики)"""
    while node.parent and node.parent.color == RBNode.RED:
        # Случай 1: узел-дядя красный -> перекрасить
        # Случаи 2 & 3: узел-дядя чёрный -> решается поворотом и перекрашиванием
        # ... (фактическая реализация включает большое количество операций с указателями; здесь приведено логическое описание)
        pass
    tree.root.color = RBNode.BLACK  # Убедиться, что корневой узел чёрный

Красно-чёрное дерево vs. AVL-дерево

Особенности AVL-дерево красно-чёрное дерево
Критерий балансировки Строгий (разница высот ≤ 1) Нестрогий (приблизительный баланс гарантируется правилами цвета)
Производительность поиска Лучше(дерево более сбалансировано) Немного уступает, но всё ещё O(log n)
Вставка/удаление Может потребоватьБольше поворотов Меньше поворотов,Более эффективно
Применимые сценарии Сценарии, требующие частого поиска Высокие комплексные требования к производительности:сценарии, такие как стандартные библиотеки языков и файловые системы.

B-дерево и B+ дерево: движок дискового хранения

Когда данные слишком велики, чтобы полностью поместиться в памяти, их приходится хранить на диске. Скорость дискового ввода-вывода (чтение/запись) намного ниже, чем скорость доступа к памяти. B-деревья и B+ деревья созданы, чтобыСократить количество операций дискового ввода-выводаРазработаны дляМногостороннее сбалансированное дерево поиска, и они широко используются в индексах баз данных и файловых систем.

B-дерево: сбалансированное многостороннее дерево поиска

B-дерево больше не требует, чтобы каждый узел хранил только один элемент данных и два указателя.B-дерево порядка mУзел имеет следующие характеристики:

  • Каждый узел имеет не болееm дочерних узлов。
  • Каждый узел, не являющийся корневым или листовым, имеет по крайней мере⌈m/2⌉ дочерних узлов。
  • Корневой узел имеет как минимум 2 дочерних узла (если только он сам не является листовым узлом).
  • Все листовые узлы находятся на одном уровне.
  • Если нелистовой узел имеет k дочерних узлов, он содержитk-1 ключей, и эти ключи разделяют диапазоны значений поддеревьев.

Рисунок: структурная схема узла B-дерева порядка 3. Он содержит два ключа и три указателя, разделяя диапазон данных на три интервала.

Преимущество B-деревазаключается в его низкой и широкой форме дерева. Поскольку узел может хранить несколько ключей и иметь несколько дочерних узлов, высота дерева значительно уменьшается. При поиске элемента данных требуется загрузить меньше страниц диска (узлов), что повышает эффективность.

B+ дерево: улучшенная версия B-дерева

B+ деревья вносят ключевые улучшения по сравнению с B-деревьями и являютсяде-факто стандартом。

Основные различия между B+ деревьями и B-деревьями:

  1. Место хранения данных: В B+ дереве,все записи данных (или указатели на записи) хранятся только в листовых узлах.. Внутренние узлы (нелистовые узлы) хранят только ключи для маршрутизации.
  2. Связный список листовых узлов: все листовые узлы связаны через указатели вупорядоченный двусвязный список。

Рисунок: диаграмма B+ дерева. Обратите внимание, что данные находятся только в листовых узлах, а листовые узлы образуют упорядоченный связанный список.

Огромное преимущество B+ деревьев

Преимущества Объяснение
Более стабильная эффективность запросов Любой поиск должен доходить до листового узла; длины путей одинаковы, поэтому производительность стабильна.
Более высокое использование пространства Внутренние узлы не хранят данные, поэтому могут вмещать больше ключей, что делает дерево короче и снижает I/O.
Мощный диапазонный запрос Через связанный список листовых узлов, эффективныеWHERE age BETWEEN 20 AND 30диапазонные запросы могут быть выполнены, тогда как B-деревья требуют сложного симметричного обхода.
Лучше подходит для предварительной выборки с диска Дисковые чтения/записи выполняются страницами (блоками). Узлы B+ дерева обычно проектируются ровно размером в одну страницу, поэтому одна операция ввода-вывода может загрузить больше ключей, что ещё больше сокращает количество операций ввода-вывода.

Итог

Давайте воспользуемся таблицей, чтобы рассмотреть эти четыре продвинутые древовидные структуры:

Структура дерева Основная цель Ключевые особенности Типичные области применения
AVL-дерево Предельная скорость запросов Очень строго сбалансировано, с частыми корректировками вращениями Сценарии, требующие быстрого поиска в памяти
красно-чёрное дерево Сбалансированная всесторонняя производительность Приближённо сбалансировано с помощью цветовых правил, эффективные вставка и удаление Стандартные библиотеки языков (Map/Set), планирование процессов
B-дерево Сокращение дискового ввода-вывода Многопутевое сбалансированное, данные могут храниться во внутренних узлах Ранние файловые системы, некоторые индексы баз данных
B+-дерево Оптимизация индекса базы данных Данные хранятся только в листьях, листья образуют связанный список, эффективные запросы диапазонов Индексы современных реляционных баз данных (MySQL, PostgreSQL)
Другие расширения