AVL Tree Introduction

An AVL tree is a self-balancing binary search tree named after its inventors, Adelson-Velsky and Landis. It maintains the balance of the tree by keeping track of a Balance Factor at each node, thereby providing efficient search, insertion, and deletion operations.

The Balance Factor of an AVL tree is defined as the height difference between the left subtree and the right subtree of a node (Height(Left Subtree) - Height(Right Subtree)). The balance factor can be -1, 0, or 1. If the absolute value of the balance factor exceeds 1, it indicates that the tree is unbalanced and requires rebalancing operations. AVL trees achieve this through rotation operations, which include left rotations, right rotations, double-left (left-right) rotations, and double-right (right-left) rotations.

The characteristics of an AVL tree are as follows:

1. Self-balancing: An AVL tree ensures that the height difference between its left and right subtrees does not exceed 1, thus maintaining balance. After inserting or deleting a node, if this balance is disrupted, the AVL tree restores it through rotation operations.
2. Binary Search Tree Property: An AVL tree adheres to binary search tree properties. For every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are greater than the node's key. This ensures that the time complexity for searching, inserting, and deleting operations within an AVL tree is O(log n), where n represents the number of nodes in the tree.
3. Height-balanced: The height of an AVL tree remains relatively small due to its balanced nature. In the worst-case scenario, the height of an AVL tree is O(log n), which keeps search operation efficiency at a high level.

AVL trees are suitable for scenarios requiring efficient search, insertion, and deletion operations with strict requirements on maintaining tree balance. However, because each node in an AVL tree must maintain its Balance Factor, frequent rebalancing operations are required during insertions and deletions. This can result in slightly lower efficiency compared to other self-balancing binary search trees, such as Red-Black Trees.

class TreeNode:
    def __init__(self, key):
        # Initialize node with its value and pointers to children
        self.key = key  # The data/key stored at this node
        self.left = None  # Pointer to the left child
        self.right = None  # Pointer to the right child
        
        # Calculate initial balance factor (Height(Left) - Height(Right))
        # Initially, both children are None with height 0, so BF is 0.
        self.balance_factor = calculate_balance(self.left, self.right)

def get_height(node):
    """Returns the height of a node or its subtree."""
    if node:
        return max(get_height(node.left), get_height(node.right)) + 1
    else:
        return -1 # Conventionally, empty tree has height -1 to make math work out

def calculate_balance(left_node, right_node):
    """Calculates the balance factor for a specific node."""
    left_h = get_height(left_node) if left_node else -1
    right_h = get_height(right_node) if right_node else -1
    return left_h - right_h # BF can be 0 or +/-1

# Note: In a full implementation, rotation functions (rotate_left, rotate_right) 
# would update the balance factors and heights of affected nodes after restructuring.