АВЛ ДЕРЕВО PYTHON

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

class Node:    def __init__(self, key):        self.left = None        self.right = None        self.key = key        self.height = 1class AVLTree:    def insert(self, root, key):          if not root:            return Node(key)        elif key < root.key:            root.left = self.insert(root.left, key)        else:            root.right = self.insert(root.right, key)          root.height = 1 + max(self.getHeight(root.left),                          self.getHeight(root.right))          balance = self.getBalance(root)          if balance > 1 and key < root.left.key:            return self.rightRotate(root)          if balance < -1 and key > root.right.key:            return self.leftRotate(root)          if balance > 1 and key > root.left.key:            root.left = self.leftRotate(root.left)            return self.rightRotate(root)          if balance < -1 and key < root.right.key:            root.right = self.rightRotate(root.right)            return self.leftRotate(root)          return root    def leftRotate(self, z):          y = z.right        T2 = y.left          y.left = z        z.right = T2          z.height = 1 + max(self.getHeight(z.left),                         self.getHeight(z.right))        y.height = 1 + max(self.getHeight(y.left),                         self.getHeight(y.right))          return y    def rightRotate(self, z):          y = z.left        T3 = y.right          y.right = z        z.left = T3          z.height = 1 + max(self.getHeight(z.left),                          self.getHeight(z.right))        y.height = 1 + max(self.getHeight(y.left),                          self.getHeight(y.right))          return y    def getHeight(self, root):        if not root:            return 0          return root.height    def getBalance(self, root):        if not root:            return 0          return self.getHeight(root.left) - self.getHeight(root.right)

В этом примере кода представлен класс AVLTree, который содержит три метода: вставка, левый поворот и правый поворот. Мы также используем класс Node для представления узлов дерева. Методы вставки, левого и правого поворота будут вызываться в зависимости от текущего баланса высот поддеревьев. Если баланс больше заданного лимита, мы выполняем повороты. Этот пример демонстрирует основную концепцию AVL-дерева и может быть изменен и дополнен в соответствии с требованиями конкретных задач.