AVL Tree

An AVL Tree is a self-balancing binary search tree where the height of the left and right subtrees of any node differ by no more than one. If they differ, the tree is rebalanced using rotations.
Space Complexity: O(n)
Time Complexity: O(log n) for search, insert, and delete operations
Best Case: Ω(log n)
Average Case: Θ(log n)
Worst Case: O(log n)

class Node:
    def __init__(self, data):
        self.data = data
        self.height = 1
        self.left = None
        self.right = None

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if not node:
            return Node(data)
        elif data < node.data:
            node.left = self._insert(node.left, data)
        else:
            node.right = self._insert(node.right, data)

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))

        balance = self._get_balance(node)

        # Left Left
        if balance > 1 and data < node.left.data:
            return self._right_rotate(node)

        # Right Right
        if balance < -1 and data > node.right.data:
            return self._left_rotate(node)

        # Left Right
        if balance > 1 and data > node.left.data:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)

        # Right Left
        if balance < -1 and data < node.right.data:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)

        return node

    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 _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 _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 inorder(self, node):
        result = []
        if node:
            result = self.inorder(node.left)
            result.append(node.data)
            result = result + self.inorder(node.right)
        return result

    def preorder(self, node):
        result = []
        if node:
            result.append(node.data)
            result = result + self.preorder(node.left)
            result = result + self.preorder(node.right)
        return result

    def postorder(self, node):
        result = []
        if node:
            result = self.postorder(node.left)
            result = result + self.postorder(node.right)
            result.append(node.data)
        return result

    def displayTraversal(self, traversal_type):
        if traversal_type == 'inorder':
            return ' -> '.join(map(str, self.inorder(self.root)))
        elif traversal_type == 'preorder':
            return ' -> '.join(map(str, self.preorder(self.root)))
        elif traversal_type == 'postorder':
            return ' -> '.join(map(str, self.postorder(self.root)))

# Example Usage
avl = AVLTree()
for i in range(20):
    avl.insert(random.randint(0, 100))

print("Inorder:", avl.displayTraversal('inorder'))
print("Preorder:", avl.displayTraversal('preorder'))
print("Postorder:", avl.displayTraversal('postorder'))