AVL Trees

Understand the idea

This example demonstrates one left rotation, not a complete AVL implementation. A full insertion algorithm also updates heights along the path and handles left-left, right-right, left-right, and right-left cases. The rotation preserves inorder key order while changing shape. Test both ordering and stored heights rather than only checking a successful lookup.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def rotate_left(root):
    pivot = root.right
    root.right = pivot.left
    pivot.left = root
    return pivot

root = Node(1, right=Node(2, right=Node(3)))
root = rotate_left(root)
print(root.key, root.left.key, root.right.key)

Read the result

The new root is 2, with children 1 and 3. The right-heavy chain becomes balanced for this small case.

Try one change

Draw the before and after shapes, then explain why inorder traversal remains 1, 2, 3.