Balanced Trees: AVL, Red-Black and B-Trees
After this lesson, you will be able to:
- Show with a count why a plain binary search tree does about n^2 / 2 comparisons on sorted input, and what a balanced tree does instead
- Compute a node's height and balance factor, and state the AVL rule
- Trace a rotation by hand, and name which of LL, RR, LR or RL needs one rotation and which needs two
- Write an AVL insert in Python with a rotation counter, and check that the height stays logarithmic
- Prove in words that an AVL tree with n nodes has height at most about 1.44 log2 n, using a Fibonacci-style recurrence
- Explain the red-black rules, why they cap the height at 2 log2(n + 1), and why a B-tree with wide nodes needs fewer disk reads
Before You Start
#Why a Plain BST Is Not Enough
key. Everything in the left subtree is smaller, and everything in the right subtree is larger. Search, insert and delete each walk one path from the root down. So their cost is the length of that path, the height of the tree.Here, height counts the nodes on the longest path from the root to a leaf. A single node has height 1, and an empty tree has height 0.
The shape of the tree depends on the order of arrival, not just on the values. Take the numbers 1, 2, 3 and so on, arriving in increasing order, and think about where each new one lands.
You insert the numbers 1, 2, 3, ... 1023 into a plain BST, in increasing order. What is the height of the finished tree?
class Node:
"""A plain BST node: a key and two child pointers."""
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def build_plain(values):
"""Insert values into a plain BST. Returns (height, comparisons).
Height counts nodes on the longest root-to-leaf path. Equal keys are ignored.
Worst case O(n^2) total comparisons for n inserts, O(n) space.
"""
root, height, compares = None, 0, 0
for key in values:
if root is None:
root, height = Node(key), 1
continue
cur, depth = root, 1
while True:
compares += 1
if key == cur.key:
break
nxt = cur.left if key < cur.key else cur.right
depth += 1
if nxt is None:
if key < cur.key:
cur.left = Node(key)
else:
cur.right = Node(key)
height = max(height, depth)
break
cur = nxt
return height, compares
def middle_first(lo, hi):
"""Values lo..hi in an order that builds a perfectly balanced tree."""
if lo > hi:
return []
mid = (lo + hi) // 2
return [mid] + middle_first(lo, mid - 1) + middle_first(mid + 1, hi)
n = 1023
print("sorted :", build_plain(range(1, n + 1)))
print("reversed:", build_plain(range(n, 0, -1)))
print("balanced:", build_plain(middle_first(1, n)))
print("n(n-1)/2 =", n * (n - 1) // 2)
# Output:
# sorted : (1023, 522753)
# reversed: (1023, 522753)
# balanced: (10, 8194)
# n(n-1)/2 = 522753Each new value is bigger than everything before it, so it goes right at every node and lands at the very bottom. The tree is a chain of right children, a linked list wearing a tree costume. The sorted run needed 522,753 comparisons, which is exactly n(n - 1) / 2, the sum 1 + 2 + ... + (n - 1). The k-th insert walks past all k - 1 earlier nodes. The balanced order needed 8,194, about 8 per insert, which is the height. So the total time is O(n^2) in the worst case and about O(n log n) when the tree stays balanced.
Reverse order is no better. Sorted arrival is common: timestamps, auto-numbered ids, log lines. A tree that needs lucky input is a trap.
This viewer is a plain BST with no balancing, which is the problem we are fixing. Insert 1, 2, 3, 4, 5 in order and watch the tree become a line. Then try 3, 1, 5, 2, 4 and compare the heights.
#Height, Balance Factor and the AVL Rule
Each node stores its own height. A missing child has height 0, and a node's height is 1 plus the larger child height, so it is recomputed in O(1). That one small integer is all the extra data an AVL node needs.
30 (height 3, balance +1)
/ \
20 40 (20: height 2, balance +1)
/
10 (10: height 1, balance 0)
Node 20 has height 2 and node 40 has height 1, so node 30 has balance 2 - 1 = +1, which is allowed. Now insert 5 under 10. Node 10 gets height 2, and node 20 has a left height of 2 against a right height of 0. Its balance is +2, so the rule is broken at 20.
Only nodes on the path from the root to the new node can change height, and each changes by at most 1. Before the insert every balance was in range, so a broken node has a balance of exactly +2 or -2. We repair the lowest broken node first.
#Rotations: Moving Links, Keeping Order
y x
/ \ / \
x C -> A y
/ \ / \
A B B C
rotate_right(y)
Read the left-to-right order of the values on both sides: A, x, B, y, C. It is identical. That is why a rotation never breaks the BST rule. The subtree B was between x and y before, and it stays between them: it moves from x's right side to y's left side. Only three pointers change, so a rotation costs O(1).
rotate_left, which lifts the right child. Rotating right is the fix for a tree too heavy on the left. After the pointers move, recompute heights with the lower node first: y now sits below x, so update y, then x. A later mistake shows what happens otherwise.class AVLNode:
"""An AVL node stores its own height: 1 for a leaf, 0 for a missing child."""
__slots__ = ("key", "left", "right", "height")
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(node):
return node.height if node else 0
def update(node):
node.height = 1 + max(height(node.left), height(node.right))
def balance(node):
"""Balance factor: height of the left subtree minus height of the right subtree."""
return height(node.left) - height(node.right)
def rotate_right(y):
"""Lift y's left child x above y. The order of the keys is unchanged. O(1)."""
x = y.left
y.left = x.right # B sits between x and y, so it becomes y's left subtree
x.right = y
update(y) # y is now lower, so fix it first
update(x)
return x
def rotate_left(x):
"""Mirror image: lift x's right child y above x. O(1)."""
y = x.right
x.right = y.left
y.left = x
update(x)
update(y)
return y
def inorder(node):
return inorder(node.left) + [node.key] + inorder(node.right) if node else []
chain = AVLNode(3) # a left-leaning chain 3 -> 2 -> 1
chain.left = AVLNode(2)
chain.left.left = AVLNode(1)
update(chain.left)
update(chain)
print("before:", chain.key, "balance", balance(chain), "inorder", inorder(chain))
top = rotate_right(chain)
print("after: ", top.key, "balance", balance(top), "inorder", inorder(top), "height", top.height)
# Output:
# before: 3 balance 2 inorder [1, 2, 3]
# after: 2 balance 0 inorder [1, 2, 3] height 2A chain of three became a tree of height 2, and the sorted order did not change.
#The Four Cases: LL, RR, LR and RL
Say node z has balance +2 (too heavy on the left). Let c be its left child, the taller one. A new value went into c's left side or into c's right side. These are two different problems, and a single rotation fixes only the first. The name is the path from z to the new node: Left-Left, Left-Right, and the mirror pair Right-Right and Right-Left.
1 2
\ / \
2 -> 1 3
\
3
3 3 2
/ / / \
1 -> 2 -> 1 3
\ /
2 1
start rotate_left(1) rotate_right(3)
How does the code choose? It looks at the balance of the taller child. If it leans the same way as z (or is level), one rotation is enough. If it leans the opposite way, the zigzag needs two. Here is the table.
| Balance at z | Balance at taller child | Case | Fix |
|---|---|---|---|
| +2 | +1 or 0 | LL | rotate_right(z) |
| +2 | -1 | LR | rotate_left(child), then rotate_right(z) |
| -2 | -1 or 0 | RR | rotate_left(z) |
| -2 | +1 | RL | rotate_right(child), then rotate_left(z) |
A child balance of 0 cannot happen after an insert. It happens after a delete, and the one-rotation rule still covers it.
Inserting 8, 4, 6 into an AVL tree makes the root 8 too heavy on the left. Its left child 4 leans right, because 6 went under 4. Which fix is needed?
#AVL Insert in Python
The insert is the ordinary BST insert plus one step on the way back up. After the recursive call returns, recompute this node's height and check its balance. If it is out of range, apply the case above. Only nodes on the walked path can be out of range, so the extra work is O(1) per level.
You insert 1, 2, 3, 4, 5, 6, 7 into an AVL tree in that order. Counting each single rotation once (so a double rotation counts as two), how many rotations happen in total?
def rebalance(node, stats):
"""Restore the AVL rule at node after one insert below it. Returns the new subtree root."""
update(node)
b = balance(node)
if b > 1: # left side too tall
if balance(node.left) < 0: # LR case: first straighten the left child
node.left = rotate_left(node.left)
stats["rotations"] += 1
stats["rotations"] += 1 # LL case, or the second step of LR
return rotate_right(node)
if b < -1: # right side too tall
if balance(node.right) > 0: # RL case
node.right = rotate_right(node.right)
stats["rotations"] += 1
stats["rotations"] += 1 # RR case, or the second step of RL
return rotate_left(node)
return node
def insert(node, key, stats):
"""AVL insert. Time O(log n): one walk down and one O(1) rebalance per level on the way back.
Space O(log n) for the recursion stack, plus one new node. Equal keys are ignored.
"""
if node is None:
return AVLNode(key)
stats["compares"] += 1
if key < node.key:
node.left = insert(node.left, key, stats)
elif key > node.key:
node.right = insert(node.right, key, stats)
else:
return node
return rebalance(node, stats)
def is_avl(node):
"""True when every balance factor is -1, 0 or +1 and every stored height is right."""
if node is None:
return True
h = 1 + max(height(node.left), height(node.right))
return (h == node.height and abs(balance(node)) <= 1
and is_avl(node.left) and is_avl(node.right))
def build_avl(values):
root, stats = None, {"rotations": 0, "compares": 0}
for key in values:
root = insert(root, key, stats)
return root, stats
cases = {"LL": [3, 2, 1], "RR": [1, 2, 3], "LR": [3, 1, 2], "RL": [1, 3, 2]}
for name, order in cases.items():
root, stats = build_avl(order)
print(name, order, "-> root", root.key, "rotations", stats["rotations"], "inorder", inorder(root))
root, stats = build_avl(range(1, 8))
print("1..7: root", root.key, "height", root.height, "rotations", stats["rotations"], "is_avl", is_avl(root))
# Output:
# LL [3, 2, 1] -> root 2 rotations 1 inorder [1, 2, 3]
# RR [1, 2, 3] -> root 2 rotations 1 inorder [1, 2, 3]
# LR [3, 1, 2] -> root 2 rotations 2 inorder [1, 2, 3]
# RL [1, 3, 2] -> root 2 rotations 2 inorder [1, 2, 3]
# 1..7: root 4 height 3 rotations 4 is_avl TrueAll four cases end with 2 at the root, the only balanced shape for three values. LL and RR cost one rotation, LR and RL two. Here is the hand trace behind the last line.
| Insert | Break found at | Fix | Tree after (root first) |
|---|---|---|---|
| 1, 2 | none | none | 1 with right child 2 |
| 3 | node 1, balance -2 | rotate left at 1 | 2 with children 1 and 3 |
| 4 | none | none | 2, 1, 3 with 4 under 3 |
| 5 | node 3, balance -2 | rotate left at 3 | 2 with children 1 and 4 (3, 5) |
| 6 | node 2, balance -2 | rotate left at 2 | 4 with 2 (1, 3) and 5 (6) |
| 7 | node 5, balance -2 | rotate left at 5 | 4 with 2 (1, 3) and 6 (5, 7) |
Sorted input made the plain BST a line, and AVL turned it into a perfect tree with a few pointer moves. After a rotation, the repaired subtree has exactly the height it had before the insert, so nothing above it can break. One insert therefore needs at most one rebalance (a single or a double rotation). Delete is harder: shortening a subtree can break the node above, and then the next, so it may need a rotation at every level, O(log n) in all. We skip delete here.
#Why the Height Stays Logarithmic
The invariant says every balance is within 1. Does that really keep the height near log2 n? Ask the opposite question. What is the fewest nodes an AVL tree of height h can have? Call it N(h). A tree with so few nodes for its height is as lopsided as the rule allows.
The root has two subtrees. One has height h - 1. The other may be as short as the rule allows, h - 2. To use the fewest nodes, make both subtrees themselves as sparse as possible. So N(h) = 1 + N(h - 1) + N(h - 2), with N(0) = 0 and N(1) = 1.
This looks like the Fibonacci numbers, and it behaves like them: N(h) is the Fibonacci number F(h + 2) minus 1. Fibonacci numbers grow by a factor of about 1.618 (the golden ratio) at each step. So n grows at least like 1.618^h, and taking logs, h is at most about log2(n) / log2(1.618), which is about 1.44 log2 n.
def min_nodes(h):
"""Fewest nodes an AVL tree of height h can have. O(h) time, O(1) space."""
a, b = 0, 1 # min_nodes(0), min_nodes(1)
for _ in range(h - 1):
a, b = b, 1 + a + b
return b if h >= 1 else 0
def max_height(n):
"""Tallest an AVL tree with n nodes can be: grow h while the sparsest tree of that height fits.
The loop runs about 1.44 log2 n times, so O(log n) time and O(1) space.
"""
steps, h = 0, 0
a, b = 0, 1 # min_nodes(h), min_nodes(h + 1)
while b <= n:
a, b = b, 1 + a + b
h += 1
steps += 1
return h, steps
print([min_nodes(h) for h in range(0, 11)])
for n in (1, 7, 1000, 10**6, 10**18):
print(n, max_height(n))
# Output:
# [0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143]
# 1 (1, 1)
# 7 (4, 4)
# 1000 (14, 14)
# 1000000 (28, 28)
# 1000000000000000000 (85, 85)Read the output. With a million values, an AVL tree is at most 28 levels tall. The smallest height any binary tree can have is 20, because a tree of height h holds at most 2^h - 1 nodes. So the worst AVL tree is within a factor of about 1.4 of perfect. Even for 10^18 values, the height is at most 85.
Two facts follow. No comparison-based search can beat about log2 n comparisons on n values, so AVL is within a factor of 1.44 of the best possible. And n inserts followed by an inorder walk sort in O(n log n) time, matching the lower bound for comparison sorts, while keeping the data sorted as you add to it.
Now check the bound on real runs. The code builds an AVL tree from sorted input, then compares its height with the lowest possible height and with the highest the recurrence allows.
import math
for n in (7, 100, 1000, 10000):
root, stats = build_avl(range(1, n + 1))
lowest = math.floor(math.log2(n)) + 1 # no binary tree with n nodes is shorter
highest = max_height(n)[0] # no AVL tree with n nodes is taller
print(f"n={n:>5} height={root.height:>2} lowest={lowest:>2} highest={highest:>2} "
f"rotations={stats['rotations']:>5} valid={lowest <= root.height <= highest and is_avl(root)}")
# Output:
# n= 7 height= 3 lowest= 3 highest= 4 rotations= 4 valid=True
# n= 100 height= 7 lowest= 7 highest= 9 rotations= 93 valid=True
# n= 1000 height=10 lowest=10 highest=14 rotations= 990 valid=True
# n=10000 height=14 lowest=14 highest=18 rotations= 9986 valid=Trueis_avl confirms every balance is within 1.Space is O(n) for n nodes, plus O(log n) of recursion, so Python's recursion limit is never a risk.
#Red-Black Trees: The Idea
Why does this keep the tree short? Let b be the black height of the root. Rule 3 means the tree is full down to depth b, so it has at least 2^b - 1 nodes. So b is at most log2(n + 1). Rule 2 says that along any path, reds cannot touch, so there is at most one red node between two blacks. Any path therefore has at most 2b nodes. Together, the height is at most 2 log2(n + 1).
That bound is looser than AVL's 1.44 log2 n. In exchange, repairing the rules takes at most two rotations after an insert (plus color flips, which move no pointers) and at most three after a delete. The usual summary: AVL trees are shallower, so lookups are a little faster, and red-black trees change less on writes.
The checker below verifies the three rules for a tree written as nested tuples. It does one walk, so O(n) time, and O(h) space for the recursion.
RED, BLACK = "R", "B"
def check_red_black(node, is_root=True):
"""Return the black height of a tree of (color, value, left, right) tuples, or raise ValueError.
Checks the red-black rules in one walk: O(n) time, O(h) space for the recursion.
"""
if node is None:
return 0 # a missing child counts as black
color, value, left, right = node
if is_root and color != BLACK:
raise ValueError("rule 1: the root must be black")
for child in (left, right):
if color == RED and child is not None and child[0] == RED:
raise ValueError(f"rule 2: red {value} has a red child {child[1]}")
left_black = check_red_black(left, False)
right_black = check_red_black(right, False)
if left_black != right_black:
raise ValueError(f"rule 3: paths under {value} hold {left_black} and {right_black} black nodes")
return left_black + (1 if color == BLACK else 0)
good = (BLACK, 10, (RED, 5, (BLACK, 3, None, None), (BLACK, 7, None, None)), (BLACK, 15, None, None))
red_red = (BLACK, 10, (RED, 5, (RED, 3, None, None), None), (BLACK, 15, None, None))
uneven = (BLACK, 10, (BLACK, 5, None, None), None)
print("good black height:", check_red_black(good))
for name, tree in (("red_red", red_red), ("uneven", uneven)):
try:
check_red_black(tree)
except ValueError as problem:
print(name, "->", problem)
# Output:
# good black height: 2
# red_red -> rule 2: red 5 has a red child 3
# uneven -> rule 3: paths under 10 hold 1 and 0 black nodesgood, the paths 10, 5, 3 and 10, 15 have 3 and 2 nodes, yet both pass two black nodes. That is the slack red-black trees allow. We skip the insert and delete procedures, which are a case analysis on the color of the uncle node. The rules and the height proof are the part that carries over.#B-Trees: Wide Nodes for Disks
If each node has up to m children, a full tree of h levels holds m^h - 1 values, so the height needed is about log base m of n.
Each node may have up to 100 children. What is the smallest number of levels that can hold 1,000,000 values?
def levels_needed(n, children):
"""Fewest levels for n keys when every node has at most `children` child pointers.
A full tree with h levels holds children ** h - 1 keys, so grow h until that is enough.
O(h) time, O(1) space.
"""
h = 0
while children ** h - 1 < n:
h += 1
return h
for children in (2, 100, 1000):
print(children, levels_needed(1_000_000, children))
# Output:
# 2 20
# 100 4
# 1000 3With wide nodes, a million values need 4 page reads at most, where a balanced binary tree needs about 20. The top levels are tiny, so they can be kept in memory.
insert 10, 20, 30: [10 20 30]
insert 40: root is full, split it, 20 moves up:
[20]
/ \
[10] [30 40]
insert 50: [30 40 50] is now full
insert 60: walking down, split that full leaf, 40 moves up:
[20 40]
/ | \
[10] [30] [50] 60 joins it: [50 60]
insert 70: [50 60 70]
The code does exactly this walk. It splits full nodes on the way down, so it never has to go back up, and it counts the nodes it touches as page reads.
from bisect import bisect_left
class BNode:
"""One B-tree node. Think of it as one page on disk: many sorted keys, many children."""
def __init__(self, leaf):
self.keys = []
self.kids = []
self.leaf = leaf
class BTree:
"""B-tree with minimum degree t: every node but the root holds t - 1 to 2t - 1 keys."""
def __init__(self, t):
self.t = t
self.root = BNode(True)
def search(self, key):
"""Returns (found, nodes_read). A tree of height h reads at most h nodes."""
node, reads = self.root, 0
while True:
reads += 1
i = bisect_left(node.keys, key)
if i < len(node.keys) and node.keys[i] == key:
return True, reads
if node.leaf:
return False, reads
node = node.kids[i]
def _split_child(self, parent, i):
"""Cut the full child parent.kids[i] in two and lift its middle key into parent."""
t = self.t
full = parent.kids[i]
right = BNode(full.leaf)
middle = full.keys[t - 1]
right.keys = full.keys[t:]
full.keys = full.keys[:t - 1]
if not full.leaf:
right.kids = full.kids[t:]
full.kids = full.kids[:t]
parent.keys.insert(i, middle)
parent.kids.insert(i + 1, right)
def insert(self, key):
"""One walk down, splitting every full node on the way. Reads O(log_t n) nodes."""
if len(self.root.keys) == 2 * self.t - 1: # a full root grows the tree upward
new_root = BNode(False)
new_root.kids = [self.root]
self.root = new_root
self._split_child(new_root, 0)
node = self.root
while not node.leaf:
i = bisect_left(node.keys, key)
if i < len(node.keys) and node.keys[i] == key:
return
if len(node.kids[i].keys) == 2 * self.t - 1:
self._split_child(node, i)
if key == node.keys[i]:
return
if key > node.keys[i]:
i += 1
node = node.kids[i]
i = bisect_left(node.keys, key)
if i < len(node.keys) and node.keys[i] == key:
return
node.keys.insert(i, key)
def height(self):
node, h = self.root, 1
while not node.leaf:
node, h = node.kids[0], h + 1
return h
def shape(node):
"""Each node as its keys; an inner node as (keys, [children])."""
return node.keys if node.leaf else (node.keys, [shape(k) for k in node.kids])
small = BTree(2)
for key in (10, 20, 30):
small.insert(key)
print(shape(small.root))
small.insert(40)
print(shape(small.root))
for key in (50, 60, 70):
small.insert(key)
print(shape(small.root), "height", small.height())
big = BTree(50)
for key in range(1, 100001):
big.insert(key)
print("t=50, 100000 sorted keys: height", big.height())
print(big.search(77777), big.search(0), big.search(100001))
# Output:
# [10, 20, 30]
# ([20], [[10], [30, 40]])
# ([20, 40], [[10], [30], [50, 60, 70]]) height 2
# t=50, 100000 sorted keys: height 3
# (True, 3) (False, 3) (False, 3)For 100,000 sorted keys, an AVL tree needs at least 17 levels (the smallest height of any binary tree on that many values), and the B-tree has 3. Every search reads at most 3 nodes. Insert does one walk down, so O(log_t n) node reads, plus O(t) work inside a node to shift the values. Space is O(n).
Many databases use the B+ tree variant, which keeps all values in the leaves and links the leaves in order, so a range query reads along the bottom. The cost of a wide node is the work inside it, which is cheap in memory. For data that lives only in memory, a binary tree is usually simpler.
#Treaps and Skip Lists: A Pointer
Two more structures balance with random coins instead of repair rules. We only point at them.
#Which Tree for Which Job
| Job | Good choice | Search, insert (worst case) | Why |
|---|---|---|---|
| Sorted data, mostly reads, in memory | AVL | O(log n) | the shortest binary trees, about 1.44 log2 n at most |
| Sorted data, many writes, in memory | Red-black | O(log n) | at most 2 rotations per insert, 3 per delete |
| Index larger than memory, on disk | B-tree or B+ tree | O(log_t n) page reads | wide nodes mean few reads |
| Simple code, expected speed is enough | Treap or skip list | O(log n) expected | random priorities replace the repair rules |
| Data arrives all at once, searches only | Sorted list and bisect | O(log n) search | no tree needed, insert is O(n) |
| Everyday Python | sortedcontainers.SortedList | about O(log n) | a third-party library, written for speed |
bisect.insort on a list searches in O(log n) but shifts items in O(n) per insert, which is fine for small or read-heavy data. Reach for a tree when you need ordered inserts and deletes over many items.#Where This Shows Up
- Database indexes. Many relational databases store an index as a B-tree or B+ tree, which is why a lookup among millions of rows reads only a few pages.
- Ordered maps in standard libraries. Java's
TreeMapis documented as a red-black tree, and C++'sstd::mapis commonly built on one. - File systems. Several use B-tree variants to keep directory and block indexes ordered on disk.
- Machine learning code. Finding the nearest timestamp to a query, or keeping a sliding window sorted for a running median, needs an ordered structure with fast insert.
The common thread is the invariant: a small rule, a proof that each operation restores it, and a height bound that follows.
#Common Mistakes
#Try It: Five Problems
Work through the ladder in order. Each problem returns counts, so you can see the cost and not only the answer. Problem 1 is easy, problem 4 asks for a full AVL insert, and problem 5 uses a number so large that building a tree is impossible.
Tests · Expected output. Line 1: (200, 19900) (0, 0) (2, 3), since sorted input of 200 values costs 200 * 199 / 2 comparisons, empty input costs nothing, and duplicates are ignored. Line 2: 2 2 [1, 2, 3]. Line 3: ['LL', 'LR', 'RR', 'RL', 'none']. Line 4: (8, 247, 1785) for 1..255 and for 255..1, then (10, 400, 2067) for the zigzag order. Line 5: (0, 0, 0) (1, 0, 2) for empty and duplicate input. Line 6: (0, 0) (1, 1) (2, 2) (85, 85), so n = 10 ** 18 needs only 85 loop steps. The starter prints zeros and 'none' for each open problem.
#Recap
A plain BST takes its shape from arrival order, so sorted input gives a chain of height n and about n^2 / 2 comparisons. A self-balancing tree restores a rule after every change.
The AVL rule keeps every balance factor in -1, 0 or +1. A rotation moves three pointers in O(1) and keeps the sorted order. LL and RR need one rotation, LR and RL two, and an insert needs at most one rebalance. The sparsest AVL tree follows a Fibonacci recurrence, so the height is at most about 1.44 log2 n.
Red-black trees keep three color rules and cap the height at 2 log2(n + 1). B-trees use wide nodes and equal-depth leaves to cut page reads. Treaps and skip lists balance by chance, with expected O(log n) cost.
You insert 1, 2, 3, 4, 5, ... n into a plain BST and into an AVL tree. Which pair of heights is right for n = 1023?
Key Takeaways
- A plain BST on sorted input becomes a chain: height n and n(n - 1) / 2 comparisons in total
- AVL keeps every balance factor in -1, 0 or +1. A rotation moves three pointers in O(1) and keeps the sorted order
- LL and RR need one rotation, LR and RL two, and an insert needs at most one rebalance
- The sparsest AVL tree follows N(h) = 1 + N(h - 1) + N(h - 2), so the height is at most about 1.44 log2 n
- Red-black trees cap the height at 2 log2(n + 1) and rotate less on writes. B-trees use wide nodes to cut disk reads
- Treaps and skip lists balance by chance, so their O(log n) is expected, not guaranteed