AVL_Tree - patch - ariadna/AlgoritmStructure_Ari

AVL_Tree
149 строк4 KB
ariadna
update AVL_Tree
18 апр 2025, 22:24
18 апр 2025, 22:240eff968
#AVL
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class 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.get_height(root.left), self.get_height(root.right))

        
        balance = self.get_balance(root)

        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root
    def get_min_value_node(self, node): 
        if node is None or node.left is None:
            return node
        return self.get_min_value_node(node.left)

    def delete(self, root, key):
        if not root:
            return root

        elif key < root.key:
            root.left = self.delete(root.left, key)

        elif key > root.key:
            root.right = self.delete(root.right, key)

        else:

            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left

            
            min_larger_node = self.get_min_value_node(root.right)
            root.key = min_larger_node.key
            root.right = self.delete(root.right, min_larger_node.key)


        if root is None:
            return root

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)


        if balance > 1 and self.get_balance(root.left) >= 0:
            return self.right_rotate(root)

        if balance > 1 and self.get_balance(root.left) < 0:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and self.get_balance(root.right) <= 0:
            return self.left_rotate(root)

        if balance < -1 and self.get_balance(root.right) > 0:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

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

    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)
    
    def inOrder(self, root):
        if root:
            self.inOrder(root.left)
            print(root.key, end=" ")
            self.inOrder(root.right)


myTree = AVLTree()
root = None
nums = [30, 20, 10, 25, 40, 50]

for num in nums:
    root = myTree.insert(root, num)

print("AVLTree:")
myTree.inOrder(root)  # ВЫВЕЛ 10 20 25 30 40 50

root = myTree.delete(root, 20)
print("\nДерево после удаления числа 20- ")
myTree.inOrder(root) # ВЫВЕЛО 10 25 30 40 50

root = myTree.insert(root, 15)
print("\nДерево после вставки числа 15- ")
myTree.inOrder(root) # ВЫВЕЛ 10 15 25 30 40 50