Составь алгоритм для структуры данных на основе сбалансированного дерева

Сбалансированные деревья — это структуры данных, которые позволяют эффективно выполнять операции вставки, удаления и поиска элементов. Они поддерживают баланс, чтобы гарантировать, что операции выполняются за логарифмическое время, даже в худших случаях. Рассмотрим алгоритм для создания простого сбалансированного дерева — AVL-дерева, которое является одной из самых известных реализаций сбалансированных деревьев.

Алгоритм для AVL-дерева

1. Структура узла:

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

2. Функция получения высоты узла:

   def get_height(node):
       if not node:
           return 0
       return node.height
   

3. Функция получения баланса узла:

   def get_balance(node):
       if not node:
           return 0
       return get_height(node.left) - get_height(node.right)
   

4. Ротация:

   • Правый вращение:

     def right_rotate(y):
         x = y.left
         T2 = x.right
         x.right = y
         y.left = T2
         # Обновление высоты
         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):
         y = x.right
         T2 = y.left
         y.left = x
         x.right = T2
         # Обновление высоты
         x.height = 1 + max(get_height(x.left), get_height(x.right)))
         y.height = 1 + max(get_height(y.left), get_height(y.right)))
         return y
     

5. Функция вставки:

   def insert(node, key):
       # 1. Выполнение стандартной вставки в бинарное дерево
       if not node:
           return Node(key)
       elif key < node.key:
           node.left = insert(node.left, key)
       else:
           node.right = insert(node.right, key)
       
       # 2. Обновление высоты узла
       node.height = 1 + max(get_height(node.left), get_height(node.right)))
       
       # 3. Получение баланса узла
       balance = get_balance(node)
   
       # 4. Если он стал несбалансированным, тогда есть 4 случая
   
       # Левый левый случай
       if balance > 1 and key < node.left.key:
           return right_rotate(node)
   
       # Правый правый случай
       if balance < -1 and key > node.right.key:
           return left_rotate(node)
   
       # Левый правый случай
       if balance > 1 and key > node.left.key:
           node.left = left_rotate(node.left)
           return right_rotate(node)
   
       # Правый левый случай
       if balance < -1 and key < node.right.key:
           node.right = right_rotate(node.right)
           return left_rotate(node)
   
       # возвращение (неизмененный узел)
       return node
   

6. Функция обхода (например, для вывода всех ключей):

   def inorder(root):
       if root:
           inorder(root.left)
           print(root.key, end=' ')
           inorder(root.right)
   

Использование алгоритма

Теперь, как мы можем использовать этот алгоритм для создания AVL-дерева и вставки ключей в него:

root = None
keys = [10, 20, 30, 40, 50, 25]  # Пример ключей для вставки

for key in keys:
    root = insert(root, key)

print("Обход дерева в порядке возрастания:")
inorder(root)

Объяснение

1. Структура узла: Каждый узел содержит ключ, указатели на левого и правого детей, а также высоту.
2. Балансировка: После каждой вставки высоты узлов обновляются, и дерево может быть переработано (повороты), если баланс узла выходит за пределы -1, 0, +1.
3. Обход: Мы используем рекурсивный обход для вывода всех ключей в отсортированном порядке.

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