AVL Insertion 🎯

Welcome to our deep dive into AVL (Adelson-Velsky and Landis) Tree, a self-balancing binary search tree! This lesson is perfect for beginners and intermediates looking to master data structures and algorithms. Let's get started!

Understanding AVL Trees 📝

AVL trees are a type of binary search tree that maintains a balance between the heights of the left and right subtrees. They are named after their creators, Adelson-Velsky and Landis. The primary benefit of AVL trees is that they provide fast search, insert, and delete operations with a guaranteed time complexity of O(log n).

Basic AVL Tree Structure 📝

An AVL tree consists of nodes, where each node contains a data element and two child pointers (left and right). In addition, each node stores a balance factor, which helps maintain the balance.

python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.bf = 0  # balance factor
        self.key = key

Balance Factor and Height 📝

The balance factor (bf) of a node is calculated as the difference between the heights of the left and right subtrees:

If the height of the left subtree is greater, the balance factor is -1.
If the height of the right subtree is greater, the balance factor is 1.
A balance factor of 0 means both subtrees have the same height.

AVL Insertion 💡

Let's dive into the heart of this lesson: AVL Insertion! We'll discuss the process step-by-step, with practical examples that will help you grasp the concept.

Step 1: Insert a new node as a leaf 📝

Start by inserting a new node as a leaf in the AVL tree, just like you would in a normal binary search tree.

python

def insert(root, key):
    if root is None:
        root = Node(key)
    else:
        current = root
        while True:
            if key < current.key:
                if current.left is None:
                    current.left = Node(key)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(key)
                    break
                current = current.right

Step 2: Update heights 📝

After inserting a new node, we need to update the heights of the affected nodes.

python

def updateHeight(node):
    if node is None:
        return 0
    else:
        leftHeight = self.getHeight(node.left)
        rightHeight = self.getHeight(node.right)
        node.bf = leftHeight - rightHeight
        return max(leftHeight, rightHeight) + 1

Step 3: Check balance 📝

After updating the heights, we need to check the balance of the tree. If the balance factor of a node exceeds 1 or goes below -1, we know the tree is unbalanced, and we need to rebalance it.

python

def isBalanced(node):
    if node is None:
        return True
    return abs(node.bf) <= 1 and isBalanced(node.left) and isBalanced(node.right)

Step 4: Rebalance the tree 💡

If the tree is unbalanced, we have several cases to consider, but we'll focus on the most common ones: left-left, right-right, and left-right cases.

python

def rotateRight(node):
    if node.left is not None:
        newRoot = node.left
        node.left = newRoot.right
        newRoot.right = node
        newHeight = updateHeight(newRoot)
        node.height = newHeight
    return newRoot

def rotateLeft(node):
    if node.right is not None:
        newRoot = node.right
        node.right = newRoot.left
        newRoot.left = node
        newHeight = updateHeight(newRoot)
        node.height = newHeight
    return newRoot

def rebalance(node):
    if node.bf > 1 and node.left.bf >= 0:
        node.left = rotateLeft(node.left)
        node = rotateRight(node)
    elif node.bf > 1 and node.left.bf < 0:
        node.left = rotateRight(node.left)
        node = rotateLeft(node)
    elif node.bf < -1 and node.right.bf <= 0:
        node.right = rotateRight(node.right)
        node = rotateLeft(node)
    elif node.bf < -1 and node.right.bf > 0:
        node.right = rotateLeft(node.right)
        node = rotateRight(node)

Step 5: Check the final balance 💡

After rebalancing the tree, we need to check if the root is balanced. If it's not, we'll continue to rebalance the tree until we reach a balanced state.

python

def insert(root, key):
    if root is None:
        root = Node(key)
    else:
        current = root
        while True:
            # ... insert, update height, check balance, rebalance (as described above)
            if not isBalanced(current):
                current = rebalance(current)

    return root

Quiz Time 🎯

With this lesson, you now have a solid understanding of AVL insertion and the process of maintaining a balanced AVL tree. Keep practicing, and you'll be an AVL master in no time! 🚀