Balanced-tree motivation

What is a binary search tree?

A binary search tree, or BST, is a binary tree with an ordering rule. In the unique-key version here, every value in a node’s left subtree is smaller than that node, and every value in its right subtree is larger. This rule tells a search which direction to follow.

Example: At a node containing 8, search for 4 by moving left. Search for 12 by moving right. Search speed depends on height: an unbalanced tree can become a long chain.

Helpful before this chapter

If these ideas are new, begin with:

Binary trees

Understand the idea

Insertion order can make an ordinary BST a chain. Balanced trees use rotations and structural rules to keep height O(log n). Rotations preserve inorder ordering while changing local ancestry.

Work through an example

Inserting 1,2,3,4 creates four rightward nodes. An AVL or red-black tree restores balance through rotations and metadata/color rules.

Time and space complexity

Unbalanced operations O(n) worst; balanced search/insert/delete O(log n), storage O(n).

Why it works

Rotations preserve all keys and their sorted inorder relationship.

Common mistakes

Do not claim logarithmic operations for an arbitrary BST.
Rebalancing metadata must be updated after structural changes.

Chapter lab · Python implementation

A strict BST stores smaller keys left and larger keys right. This chapter assumes unique keys; duplicate-key policies need explicit changes. Operations follow one root-to-leaf path, so their cost is proportional to height. Balancing is what turns that into a logarithmic worst-case guarantee.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def insert(root,key):
    if root is None: return Node(key)
    if key<root.key: root.left=insert(root.left,key)
    elif key>root.key: root.right=insert(root.right,key)
    return root

def search(root,key):
    while root is not None:
        if key==root.key: return root
        root=root.left if key<root.key else root.right
    return None

def valid(root,low=float('-inf'),high=float('inf')):
    if root is None: return True
    return (low<root.key<high and
            valid(root.left,low,root.key) and
            valid(root.right,root.key,high))

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=None
for x in [4,2,6,1,3]: root=insert(root,x)
assert valid(root) and search(root,3).key==3
assert search(root,9) is None
root.left.right.key=5; assert not valid(root)

CHECK YOUR UNDERSTANDING