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

Сбалансированные деревья — это структуры данных, которые позволяют эффективно выполнять операции вставки, удаления и поиска элементов. Они поддерживают баланс, чтобы гарантировать, что операции выполняются за логарифмическое время, даже в худших случаях. Рассмотрим алгоритм для создания простого сбалансированного дерева — AVL-дерева, которое является одной из самых известных реализаций сбалансированных деревьев. ### Алгоритм для AVL-дерева 1. **Структура узла**: ```python class Node: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 # Высота узла ``` 2. **Функция получения высоты узла**: ```python def get_height(node): if not node: return 0 return node.height ``` 3. **Функция получения баланса узла**: ```python def get_balance(node): if not node: return 0 return get_height(node.left) - get_height(node.right) ``` 4. **Ротация**: - **Правый вращение**: ```python 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 ``` - **Левый вращение**: ```python 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. **Функция вставки**: ```python 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. **Функция обхода** (например, для вывода всех ключей): ```python def inorder(root): if root: inorder(root.left) print(root.key, end=' ') inorder(root.right) ``` ### Использование алгоритма Теперь, как мы можем использовать этот алгоритм для создания AVL-дерева и вставки ключей в него: ```python 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. **Обход**: Мы используем рекурсивный обход для вывода всех ключей в отсортированном порядке. Этот алгоритм обеспечивает не только эффективное хранение данных, но и быструю обработку запросов, что делает его полезным в различных приложениях.