Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python AVL insertion: rotate while preserving ordered keys and heights

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

An AVL tree keeps each node’s two subtree heights within one level so search paths remain logarithmic in the retained key count.

Download Python source kit

Operation contract

The receipt index stores bounded unique integer keys. Duplicate insertion leaves its logical key set unchanged. Each recursive insertion updates height before testing balance, and single or paired rotations restore the local invariant. The wrapper retains the returned root because a rotation can replace the tree’s entrypoint.

Failure and ownership boundary

This fixture implements insertion only. Deletion needs its own rebalance path, and arbitrary externally edited nodes are outside the owned-tree contract. The index rejects a new key after its 128-key budget before changing nodes; a duplicate remains allowed. Python BST deletion: replace a two-child node with its successor and Python iterative tree traversal: shared nodes are not a tree explain related but distinct operations.

Working program

python
from dataclasses import dataclass

@dataclass
class IndexNode:
    key: int
    left: "IndexNode | None" = None
    right: "IndexNode | None" = None
    height: int = 1

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

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

def rotate_right(node):
    replacement = node.left
    node.left = replacement.right
    replacement.right = node
    refresh(node); refresh(replacement)
    return replacement

def rotate_left(node):
    replacement = node.right
    node.right = replacement.left
    replacement.left = node
    refresh(node); refresh(replacement)
    return replacement

def insert_key(node, key):
    if node is None:
        return IndexNode(key)
    if key < node.key:
        node.left = insert_key(node.left, key)
    elif key > node.key:
        node.right = insert_key(node.right, key)
    else:
        return node
    refresh(node)
    balance = height(node.left) - height(node.right)
    if balance > 1:
        if key > node.left.key:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1:
        if key < node.right.key:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

class ReceiptIndex:
    def __init__(self):
        self.root = None
        self.keys = set()
    def add(self, key):
        if type(key) is not int or (key not in self.keys and len(self.keys) >= 128):
            raise ValueError("index key budget rejected")
        self.root = insert_key(self.root, key)
        self.keys.add(key)

index = ReceiptIndex()
for key in (10, 20, 30, 40, 50):
    index.add(key)
print("root:", index.root.key)
print("height:", index.root.height)
index.add(30)
print("unique keys:", len(index.keys))

Output

Output
root: 20
height: 3
unique keys: 5

Costs and limits

Accepted insertion takes O(log n) tree traversal and stack depth while AVL invariants hold. Rotations change a bounded number of links, and height refresh uses retained child heights. The wrapper’s key set and nodes retain O(n) state; integer comparison/hash costs depend on digit size.

Common Mistakes

  • Refresh heights in child-before-parent order after a rotation.
  • A logarithmic-height claim requires checking the balance invariant after updates.

Connected lessons

Python BST deletion: replace a two-child node with its successor, Python iterative tree traversal: shared nodes are not a tree, Python bisect: binary position search does not make list insertion logarithmic.

Check the next state boundary

Python AVL deletion: rebalance after removing a key and replacing its successor.

python
avl-insertion
Storage details