AVL Tree Data Structure

 AVL Tree Data Structure

An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees of any node is at most 1. It provides efficient search, insertion, and deletion operations, and is commonly used in databases and compilers.

python

# AVL Node class

class AVLNode:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

        self.height = 1

# AVL Tree class

class AVLTree:

    def insert(self, root, key):

        if not root:

            return AVLNode(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_factor = self.get_balance_factor(root)

        if balance_factor > 1 and key < root.left.key:

            return self.right_rotate(root)

        if balance_factor < -1 and key > root.right.key:

            return self.left_rotate(root)

        if balance_factor > 1 and key > root.left.key:

            root.left