implement avl tree in python

main.py
# Define a class for individual AVL Tree nodes
class AVLTreeNode:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        self.height = 1

# Define the AVL Tree class
class AVLTree:
    def __init__(self):
        self.root = None

    # Helper method to calculate the height of the tree
    def _height(self, node):
        if not node:
            return 0
        return node.height

    # Helper method to calculate the balance factor of a node
    def _balance_factor(self, node):
        if not node:
            return 0
        return self._height(node.left_child) - self._height(node.right_child)

    # Helper method to rotate a node to the right
    def _rotate_right(self, node):
        new_root = node.left_child
        node.left_child = new_root.right_child
        new_root.right_child = node

        # Update heights
        node.height = 1 + max(self._height(node.left_child), self._height(node.right_child))
        new_root.height = 1 + max(self._height(new_root.left_child), self._height(new_root.right_child))

        return new_root

    # Helper method to rotate a node to the left
    def _rotate_left(self, node):
        new_root = node.right_child
        node.right_child = new_root.left_child
        new_root.left_child = node

        # Update heights
        node.height = 1 + max(self._height(node.left_child), self._height(node.right_child))
        new_root.height = 1 + max(self._height(new_root.left_child), self._height(new_root.right_child))

        return new_root

    # Method to insert a value into the tree
    def insert(self, data):
        # Recursively insert the data
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        # If the node is None, return a new node with the data
        if not node:
            return AVLTreeNode(data)

        # Insert the node into the proper location
        if data < node.data:
            node.left_child = self._insert(node.left_child, data)
        else:
            node.right_child = self._insert(node.right_child, data)

        # Update the height of the node
        node.height = 1 + max(self._height(node.left_child), self._height(node.right_child))

        # Update the balance factor and balance the tree if necessary
        balance_factor = self._balance_factor(node)
        if balance_factor > 1 and data < node.left_child.data:
            # Left-Left case
            return self._rotate_right(node)
        elif balance_factor > 1 and data > node.left_child.data:
            # Left-Right case
            node.left_child = self._rotate_left(node.left_child)
            return self._rotate_right(node)
        elif balance_factor < -1 and data > node.right_child.data:
            # Right-Right case
            return self._rotate_left(node)
        elif balance_factor < -1 and data < node.right_child.data:
            # Right-Left case
            node.right_child = self._rotate_right(node.right_child)
            return self._rotate_left(node)

        return node
3095 chars
87 lines