Skip to content

Latest commit

 

History

History
101 lines (65 loc) · 5.51 KB

topic_12.md

File metadata and controls

101 lines (65 loc) · 5.51 KB

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

Алгоритм вставки ключа в АВЛ-дерево

  1. Поиск места вставки:

    • Выполняется как в обычном бинарном дереве поиска.
    • Ключ добавляется в подходящее место, сохраняя упорядоченность.

  2. Обновление высот:

    • После вставки обновляется высота каждого узла по пути от нового узла к корню.

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

    • АВЛ-дерево считается сбалансированным, если разница высот левого и правого поддерева каждого узла не превышает 1.

  4. Балансировка:

    • Если дерево стало несбалансированным, выполняется одна из следующих операций:
      • Правый поворот (LL): при дисбалансе в левом поддереве левого потомка.
      • Левый поворот (RR): при дисбалансе в правом поддереве правого потомка.
      • Левый-правый поворот (LR): при дисбалансе в правом поддереве левого потомка.
      • Правый-левый поворот (RL): при дисбалансе в левом поддереве правого потомка.

Назначение балансировки дерева

Балансировка в АВЛ-дереве необходима для поддержания минимальной высоты дерева, что обеспечивает эффективное выполнение операций поиска, вставки и удаления с временной сложностью ( O(\log n) ).

Критерий сбалансированности АВЛ-дерева

АВЛ-дерево сбалансировано, если для каждого узла выполняется условие: [ |h_{\text{left}} - h_{\text{right}}| \leq 1, ] где ( h_{\text{left}} ) и ( h_{\text{right}} ) — высоты левого и правого поддеревьев соответственно.

Критерий несбалансированности АВЛ-дерева

АВЛ-дерево несбалансировано, если для хотя бы одного узла: [ |h_{\text{left}} - h_{\text{right}}| > 1. ]

Определение высоты сбалансированного дерева при известном числе узлов

Для АВЛ-дерева минимальная высота ( h ) определяется рекурсивно: [ h(n) = h(n - 1) + h(n - 2) + 1, ] где ( n ) — число узлов.

Определение опорного узла в АВЛ-дереве

Опорный узел — это узел, в котором обнаруживается дисбаланс (разница высот левого и правого поддеревьев больше 1), требующий выполнения операции балансировки.

Дерево Фибоначчи

Дерево Фибоначчи — это особый случай АВЛ-дерева, где структура узлов соответствует последовательности Фибоначчи.

Свойства:

  • Минимальное количество узлов для высоты ( h ) определяется формулой: [ n_h = F_{h+2} - 1, ] где ( F_{h+2} ) — число Фибоначчи на позиции ( h+2 ).

Определение количества узлов при заданной высоте дерева

Количество узлов ( n_h ) для высоты ( h ) в дереве Фибоначчи: [ n_h = F_{h+2} - 1, ] где ( F_{h+2} ) — число Фибоначчи.

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

Высота ( h ) определяется как: [ h = \text{позиция } F_{h+2} \text{ в последовательности Фибоначчи, где } n + 1 = F_{h+2}. ]

Совершенное дерево и дерево Фибоначчи

Совершенное дерево:

  • Все уровни, кроме последнего, полностью заполнены.
  • Последний уровень заполнен слева направо.
  • Минимальная высота для заданного числа узлов.

Дерево Фибоначчи:

  • Минимально возможное число узлов для заданной высоты.
  • Характеризуется асимметричной структурой.

Сходства:

  • Оба дерева минимизируют высоту относительно числа узлов.

Различия:

  • Совершенное дерево полностью заполнено, а дерево Фибоначчи допускает «разреженность».
  • Дерево Фибоначчи использует последовательность Фибоначчи для определения структуры.