Python: AVL Tree Implementation

1. Introduction

AVL trees are a type of binary search tree where the height difference (balance factor) between the left and right subtrees of any node is not more than one. This ensures that the tree remains approximately balanced, leading to O(log n) time for operations like insertion, deletion, and search.

2. Program Overview

Our Python program will:

1. Define an AVL tree node with properties for value, height, left child, and right child.

2. Implement rotations to keep the tree balanced: right rotation, left rotation, right-left rotation, and left-right rotation.

3. Implement functions to insert and delete nodes while maintaining the AVL balance property.

4. Provide a utility to print in-order traversal of the tree.

3. Code Program

class AVLNode:
    def __init__(self, key, height=1):
        self.key = key
        self.height = height
        self.left = None
        self.right = None

def height(node):
    if not node:
        return 0
    return node.height

def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))

def balance(node):
    return height(node.left) - height(node.right)

def left_rotate(x):
    y = x.right
    x.right = y.left
    y.left = x
    update_height(x)
    update_height(y)
    return y

def right_rotate(y):
    x = y.left
    y.left = x.right
    x.right = y
    update_height(y)
    update_height(x)
    return x

def insert(root, key):
    if not root:
        return AVLNode(key)

    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

    update_height(root)
    balance_factor = balance(root)

    # Left heavy
    if balance_factor > 1:
        if key < root.left.key:
            return right_rotate(root)
        else:
            root.left = left_rotate(root.left)
            return right_rotate(root)

    # Right heavy
    if balance_factor < -1:
        if key > root.right.key:
            return left_rotate(root)
        else:
            root.right = right_rotate(root.right)
            return left_rotate(root)

    return root

def in_order_traversal(root):
    return in_order_traversal(root.left) + [root.key] + in_order_traversal(root.right) if root else []

# Sample Usage
root = None
keys = [10, 20, 30, 40, 50]
for key in keys:
    root = insert(root, key)
print("In-Order Traversal:", in_order_traversal(root))

Output:

In-Order Traversal: [10, 20, 30, 40, 50]

4. Step By Step Explanation

1. We start by defining an AVLNode class to represent nodes in the AVL tree.

2. Utility functions height, update_height, and balance provide information about a node's height and balance factor.

3. The left_rotate and right_rotate functions implement rotations for AVL balancing.

4. The insert function adds a node to the AVL tree while ensuring the tree remains balanced.

5. Finally, the in_order_traversal function helps in verifying the structure of our AVL tree.

The sample usage creates an AVL tree with keys ranging from 10 to 50. The resulting tree remains balanced and the in-order traversal confirms that keys are in the correct order.