🌲 AVL-дерево в C#

AVL-дерево — это самобалансирующееся бинарное дерево поиска, в котором:

• Баланс-фактор (разница высот левого и правого поддерева) каждого узла равен -1, 0 или 1.

• При нарушении баланса выполняется ротация (левая, правая или двойные) для восстановления баланса.

Баланс-фактор (BF) узла вычисляется так:

BF = Height(Left) - Height(Right)

• BF = 0, 1 или -1 — дерево сбалансировано.
• BF > 1 — перегрузка слева.
• BF < -1 — перегрузка справа.

🤔 Что такое ротация в деревьях?

Ротация — это операция, которая переставляет узлы в бинарном дереве, изменяя их структуру без нарушения свойств дерева.

Когда высота левого и правого поддерева отличается более чем на 1, дерево становится разбалансированным. Это снижает эффективность операций поиска, вставки и удаления.

Виды ротаций в AVL-дереве:

1️⃣ Правое вращение

Применяется, когда перегрузка слева (BF > 1) и новый узел добавлен в левое поддерево левого потомка.

Простой пример:

    C
   /
  B
 /
A

После правого вращения:

    B
   / \
  A   C

2️⃣Левое вращение

Применяется, когда перегрузка справа (BF < -1) и новый узел добавлен в правое поддерево правого потомка.

Пример:

A
 \
  B
   \
    C

После левого вращения:

  B
 / \
A   C

3️⃣ Лево-правое вращение

Используется при перегрузке слева, если новый узел добавлен в правое поддерево левого потомка.

Сначала выполняется левое вращение для левого потомка.
Затем правое вращение для корня.

4️⃣ Право-левое вращение

Используется при перегрузке справа, если новый узел добавлен в левое поддерево правого потомка.

Сначала выполняется правое вращение для правого потомка.
Затем левое вращение для корня.

6 полезных шаблонов проектирования

🚩 Шаблон проектирования Singleton

🚩 Шаблон проектирования Итератор

🚩 Шаблон проектирования Декоратор

🚩 Шаблон проектирования Фасад

🚩 Шаблон проектирования Адаптер

🚩 Шаблон проектирования Абстрактная фабрика

#полезное