Lecture XI · Data Structures & Algorithms
Trees, BSTs, and balance
Last lecture we bought constant-time lookup and paid for it with order. A hash
table scatters keys across buckets on purpose, and the scattering is exactly
what makes it fast; ask it for the smallest key, or for everything between
"Kosovo" and "Latvia", or simply to hand back its contents in sorted order,
and it has nothing to offer but a full scan. That is a real loss. Most of the
questions we actually ask of data are ordered questions.
So this lecture buys the order back. The structure that does it is the binary search tree, and the whole lecture is one long argument: the search tree property gives you sorted structure for free, every operation costs the height of the tree, and the height is entirely at the mercy of the order the keys arrived in. The last third is about taking that mercy away.
A tree is a list that branched
Start with the shape, before any searching. In Lecture V a node held one link,
next, and the nodes formed a chain. Give a node two links, or a list of links,
and the chain becomes a tree. That is the entire structural change, and
everything else follows from it.
The vocabulary is worth ten seconds because I will use it constantly. The node at the top is the root (computer science grows its trees downward, and I have stopped apologising for it). A node’s links point to its children; the node above is its parent; a node with no children is a leaf. An edge is one parent-to-child link. The depth of a node is the number of edges from the root down to it, so the root has depth 0. The height of a tree is the largest depth in it, that is, the number of edges on the longest root-to-leaf path. I will use that convention all lecture: a single node has height 0, and by convention the empty tree has height . Different books differ by one here; what matters is that you pick one and stay honest.
Now the definition that does the real work, which is recursive:
A tree is a node holding some data, together with a list of trees, its children.
Read that again and notice there is no base case in sight. There does not need to be: a leaf is a node whose list of children happens to be empty, and the recursion stops there by itself. This is not a cute reformulation. It is the reason nearly every tree algorithm you will ever write is four lines long. If a tree is made of trees, then a function on trees is written by calling itself on the children and combining the answers, which is precisely the induction we set up in Lecture VI.
class Tree:
def __init__(self, data, children=()):
self.data = data
self.children = list(children)
Two lines of state, and we can already say what the ADT is. A Tree supports:
give me the data at this node; give me my children; tell me my height and my
size; walk me in some order. Notice what is missing. There is no find yet, no
ordering, no promise about where anything lives. A bare tree is a shape, not a
search structure. The searching comes later, when we impose an invariant on top
of this shape.
Watch how short the recursive functions are. Size: one for me, plus the size of each child. Height: zero if I am a leaf, otherwise one more than the tallest child. Each is a direct transcription of the recursive definition, and neither needs a loop over anything but my immediate children.
Four ways to walk
There is only one sensible way to walk a linked list: start at the head, follow
next, stop at None. A tree branches, so at every node there is a choice, and
the choices give us genuinely different orders. Four of them have names, and the
names are worth knowing because each one is the right answer to a different
question.
For a binary tree, where every node has a left and a right child slot, three of the four differ only in where you put yourself relative to the two recursive calls:
- Preorder: me, then the left subtree, then the right. Parent before children.
- Inorder: the left subtree, then me, then the right. Me in the middle.
- Postorder: the left subtree, the right subtree, then me. Children before parent.
The fourth, level order, is not a rearrangement of the same recursion at all. It visits every node at depth 0, then every node at depth 1, and so on, which no recursive descent will give you. It needs a queue: put the root in, and then repeatedly take a node out and put its children in. Depth by depth falls out of the first-in-first-out discipline automatically, which is a rather lovely payoff for the ADT we built in Lecture IV.
When is each one right? Preorder writes a node down before its subtree, so it is the order for copying a tree, serialising it, or printing an outline: you need the heading before its contents. Postorder finishes the children before it touches the parent, so it is the order for anything where the parent’s answer depends on the children’s: computing sizes and heights, evaluating an expression tree, freeing memory, deleting a directory. You cannot delete a folder until its contents are gone, and postorder is the walk that respects that. Inorder is the one that will matter most in twenty minutes, because on a search tree it emits the keys in sorted order. Level order is what you want when depth is the thing you care about: the shallowest answer first, printing a tree by rows, or searching outward from a start point. That last one is breadth-first search, and we will meet it again on graphs in Lecture XIII, where it is the same code with a bigger set of neighbours.
The search tree property
Now the invariant, which is the whole idea. A binary tree is a binary search tree when, for every node in it:
Read the quantifier carefully, because this is the single most common bug in the topic. It says every key in the subtree, not the child. A node whose left child is smaller and whose right child is larger can still sit in a tree that is not a search tree, if some grandchild off to one side has drifted onto the wrong half of the line. The property is global, and checking it locally, one parent against its two children, will happily certify a broken tree.
The honest way to check it is to carry the bounds down as you descend. When you
step into a node’s left subtree you have learned something: every key down there
must be less than this node’s key. So is_bst takes a lower bound and an upper
bound, tightens one of them at each step, and any key that escapes its window
fails immediately. That interval is the same idea as the loop invariant from
Lecture VIII: a shrinking window that the answer is guaranteed to live inside.
The checks · run against your code
# an ordinary legal tree passes good = Node(50, Node(30, Node(20), Node(40)), Node(70)) assert is_bst(good) # the empty tree is a legal search tree assert is_bst(None) # so is a lone node assert is_bst(Node(1)) # the local-only trap: every parent-child pair is fine, the tree is not trap = Node(50, Node(30, Node(20), Node(60)), Node(70)) assert not is_bst(trap) # a violation buried on the right spine is caught too deep = Node(50, None, Node(70, Node(10), None)) assert not is_bst(deep)
Why is this invariant worth the trouble? Because it turns a search into a sequence of decisions with no backtracking. To find a key, compare it with the root. If it is smaller, the entire right subtree is eliminated, not searched and discarded but never looked at, because the property guarantees nothing smaller lives over there. Recurse into the left. This is binary search from Lecture VIII, and it is exactly as good as its ability to keep throwing away half the remaining data. The cost of a lookup is the number of nodes on the path you walk, which is at most the height of the tree, so lookup is .
That is the number to hold onto. Everything for the rest of the lecture is about what turns out to be.
Insert, and the leaf where the search failed
Insertion is lookup that does not give up. Search for the key you are inserting.
If you find it, there is nothing to do (a set does not hold duplicates; a map
would overwrite the value here). If you do not find it, the search runs off the
bottom of the tree and reaches a None, and that empty spot is precisely where
the new key belongs. Hang a fresh node there and you are done, and the property
still holds, because you have put the key on the one path all those comparisons
already agreed on.
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
return node
This is the pattern to internalise for the rest of the lecture: a recursive
tree function returns the new root of the subtree it was handed, and the
caller reassigns. That convention costs one extra assignment per level and saves
you from ever writing parent-pointer bookkeeping. Insert returns the same node
in almost every case, and a brand-new node in one, and the line
node.left = insert(node.left, key) quietly handles both. When we get to
rotations, the same convention will let the tree restructure itself under a
recursive call with no special cases.
Insert costs too, for the same reason as lookup: one comparison per level on the way down, one assignment per level on the way back up.
The checks · run against your code
# inserting in sorted order builds a right spine
t = None
for k in [1, 2, 3]:
t = insert(t, k)
assert t.key == 1 and t.right.key == 2 and t.right.right.key == 3
# whatever the order in, the in-order walk comes out sorted
u = None
for k in [50, 30, 70, 20, 40]:
u = insert(u, k)
assert inorder(u, []) == [20, 30, 40, 50, 70]
# a new key lands exactly where the failed search fell off
assert u.left.left.key == 20
# a duplicate is ignored: the tree does not grow
u = insert(u, 30)
assert inorder(u, []) == [20, 30, 40, 50, 70]
Delete, and the one hard case
Deletion is where students slow down, and rightly, because removing a node from the middle of a tree threatens to disconnect it. There are three shapes, and two of them are easy.
No children. The node is a leaf. Drop it: replace it with None. Nothing
was hanging off it, so nothing is lost.
One child. Splice. Whatever was below the doomed node moves up into its place. The property still holds, because that whole subtree was already on the correct side of everything above it, and deleting a node between them does not change which side that is. This is the same splice as the linked-list deletion from Lecture V, with the same feel.
Two children. Here you cannot simply promote one child, because the other child has nowhere to go. The trick is to stop thinking about removing the node and start thinking about removing the key. Find the key that could legally sit in this node’s place: either the largest key in the left subtree (the predecessor) or the smallest key in the right subtree (the successor). Take the successor, say. Copy its key into the doomed node, and then delete the successor from the right subtree. That second deletion is guaranteed to be easy, because the smallest node in a subtree is the one you reach by walking left until you cannot, so it has no left child, so it falls under case one or case two.
That reduction is the entire idea, and it is worth saying out loud: the hard case is not solved directly, it is turned into an easy case by moving a key instead of a node. Delete is as well: one walk down to find the node, and at worst one more walk down the right subtree to find the successor.
Height is everything, and the insertion order decides it
Every operation we have written costs . So what is ?
It depends, and the range is not a small one. With nodes, the best possible height is , achieved when every level is full: level holds up to nodes, so nodes need at least about levels to hold them. The worst possible height is , achieved when every node has exactly one child and the tree is a single long path. That tree is a linked list wearing a costume, and has silently become .
Now the sting. Which of those two you get is decided entirely by the order the keys arrived in, and the worst order is not some adversarial monstrosity. It is sorted. Insert into a plain search tree: each key is bigger than everything already in, so each one walks the whole right spine and lands at the bottom of it. You get a right-leaning path of height . Reversed input gives you the mirror image. Any nearly-sorted input, which is to say a great deal of real data, gives you something nearly as bad. The most natural way for data to arrive is the way that ruins this structure.
Random order, by contrast, is fine: the expected height of a search tree built from a random permutation is , growing asymptotically like , so a shuffle gets you within a small constant factor of optimal with high probability. That is a genuine result and not a consolation prize, and it is the same reason randomised pivots rescued quicksort in Lecture IX. But you rarely control the order, and “please shuffle your data before inserting it” is not an interface anyone wants to ship.
Rotation: the one legal move
To fix a lopsided tree we need an operation that changes the shape without changing the contents. That operation is the rotation, and there is really only one of them, in two mirror-image flavours.
Take a node with a left child . A right rotation at lifts into ‘s place and pushes down to become ‘s right child. The subtree that was ‘s right child, the one holding all the keys between and , changes parents: it becomes ‘s new left child. Three references move, and the whole thing is regardless of how large the subtrees are, because the subtrees themselves are never touched, only re-pointed.
def rotate_right(y):
x = y.left
y.left = x.right # the middle subtree changes parents
x.right = y # y sinks
return x # x is the new root of this subtree
def rotate_left(x):
y = x.right
x.right = y.left
y.left = x
return y
Here is why it is legal. Before the rotation, the in-order reading of the subtree is: everything under ‘s left, then , then everything under ‘s right, then , then everything under ‘s right. After the rotation, read it again: same five pieces, same order. A rotation preserves the in-order sequence. It moves one node up and one node down and reassigns exactly one subtree, and the sorted reading of the whole tree is untouched, which means the search tree property survives. That is the entire licence for everything that follows: we may reshape the tree however we like, as long as we only ever do it with rotations.
A right rotation shortens the left side and lengthens the right. So the recipe for a tree that has grown too tall on the left is: rotate right at the top of the offending part. The next two sections are entirely about when to do that and where.
Weight-balanced: count the nodes
The first balancing rule is the most obvious one. If the trouble is that one side holds much more than the other, then measure exactly that, and rebalance when the imbalance gets too big.
Store the size of each subtree in the node, maintained on the way back up from every insert and delete (this is the same wrapper-pattern idea from Lecture V: a stored field is trustworthy only because one class owns every update to it). Call a node weight-balanced when neither child’s subtree holds more than some fixed fraction of the node’s total, say more than three quarters. On the way back up from an insertion, check that condition at every node on the path. Where it fails, rotate to fix it, using a single rotation when the offending grandchild is on the outside and a double rotation when it is on the inside.
Because the ratio can never drift far, the height of a weight-balanced tree stays , and since insert already walks a root-to-leaf path, the extra checking is free in the asymptotic sense. The stored sizes are a bonus, not just overhead: with subtree sizes in hand you can answer “what is the -th smallest key” in by descending and comparing against the left subtree’s size, which is a genuinely useful operation a plain tree cannot do at all.
The cost is that sizes are the wrong thing to measure if all you care about is height. Two trees can have identical subtree sizes and different heights. Which brings us to the rule that measures the thing it actually wants.
AVL: measure the height, fix it locally
An AVL tree stores, at every node, the height of its subtree, and maintains one invariant:
That is it. Every node’s two sides must be within one of each other. The quantity is called the balance factor, and it is the number drawn beside each node in the playground below.
This local condition buys a global guarantee. Let be the smallest number of nodes an AVL tree of height can have. The scrawniest legal tree of height has a root, a subtree of height , and a subtree of height (it cannot be , that would break the invariant), so . Those are the Fibonacci numbers from Lecture VI, shifted, and they grow exponentially, roughly as . Turn that around: if nodes force then . An AVL tree is never more than about 44 percent taller than a perfect tree. The lopsided disaster is impossible, not merely unlikely.
Maintaining it takes one insert and, at most, one rebalance. After inserting at a leaf you walk back up the path you came down, recomputing heights. The first node whose balance factor reaches is the one to repair, and there are exactly four cases, named for where the new key went:
- Left-left: the tree grew in the left child’s left subtree. One right rotation at the unbalanced node.
- Right-right: mirror image. One left rotation.
- Left-right: the tree grew in the left child’s right subtree. A single right rotation does not help here (try it: it just moves the problem to the other side). Rotate left at the child first, converting the shape into left-left, then rotate right at the top. Two rotations.
- Right-left: mirror image of left-right. Rotate right at the child, then left at the top.
The inside cases are the ones worth doing on paper once. The single rotation works when the offending subtree hangs on the outside of the zig, because the rotation swings it up a level; when it hangs on the inside, the rotation moves it across but not up, and a first rotation is needed to push it to the outside. That is the whole content of “double rotation”: it is not a new move, it is two of the same move.
One more pleasant fact: for insertion, a single rebalance is always enough. The repair restores the subtree’s height to what it was before the insertion, so nothing above it changed, so nothing above it needs fixing. Deletion is less kind, and can require rebalancing all the way up, which is still rotations and still cheap.
The plate is the place to stop reading and start pressing. Build the sorted order and watch the spine grow, one insertion every second and a half; then try to flatten it by hand, choosing a node and rotating; then hand the same seven keys to AVL and see how many rotations it spends and what height it lands on. The balance factor over each node turns rose the moment it leaves , so you can see the violation before the rotation that repairs it.
| insertion order | keys | height, plain | height, AVL | rotations |
|---|---|---|---|---|
| Sorted | 1 2 3 4 5 6 7 | 6 | 2 | 4 |
| Reversed | 7 6 5 4 3 2 1 | 6 | 2 | 4 |
| Zig-zag | 1 7 2 6 3 5 4 | 6 | 3 | 5 |
| Bisected | 4 2 6 1 3 5 7 | 2 | 2 | 0 |
Same seven keys, same search tree property, four different shapes. The best possible height for seven nodes is 2; only AVL reaches it from every order. Enable JavaScript to build these trees a key at a time and rotate them by hand.
Splay trees: no invariant at all
AVL keeps a promise at every moment, and pays for it with a stored field at every node and a rebalance check on every path. A splay tree takes the opposite bet: store nothing, promise nothing about any individual moment, and still come out fine on average.
The rule is a single sentence. Whenever you touch a node, whether you looked it up, inserted it, or deleted around it, rotate it all the way to the root. That is the splay operation. There is no balance factor, no subtree size, no extra byte per node, and no invariant that a checker could ever fail.
The one subtlety is how you rotate it up, and it matters more than it looks. Splaying moves the node up two levels at a time, looking at it together with its parent and grandparent:
- Zig: the node’s parent is the root. One rotation, and you are done.
- Zig-zig: node, parent, and grandparent lie in a straight line (all left children, or all right). Rotate at the grandparent first, then at the parent. Note the order: grandparent first.
- Zig-zag: the node is a left child of a right child, or the reverse. Rotate at the parent, then at the (new) grandparent. This is the AVL double rotation under another name.
Why insist on the zig-zig order instead of just rotating the node up twice? Because rotating a node up one level at a time on a long path leaves the path essentially as long as it was: you pull one node out and everything else stays strung out behind you. The zig-zig, done grandparent-first, folds the path in half. This is the difference between an amortised guarantee and no guarantee at all, and it is the reason splaying is a specific procedure and not just “rotate until you get there”.
Now the honest version of the analysis. The claim is that any sequence of operations on a splay tree with keys costs total, so the amortised cost per operation is . The argument is a potential function argument, the same accounting trick that made the doubling array’s amortised append constant in Lecture III. Here is the sketch.
Give every node a rank , and define the potential of the whole tree as . Potential is prepaid work: a tall stringy tree has high potential, a balanced one has low potential, and the amortised cost of an operation is defined as its real cost plus the change in potential. The technical heart is the access lemma: the amortised cost of splaying a node to the root of a tree with root is at most . Since and , that is per operation. Sum over operations, add the at most of potential the starting tree could have held, and the total falls out.
What that argument does not say deserves equal time. It does not say any single operation is fast: splaying a key at the bottom of a long spine really does cost , and it can happen, and no amount of amortisation makes that one call return sooner. If you are writing something with a latency budget, a real-time system or an interactive frame loop, an amortised bound is not the bound you need. What the argument buys is that such an expensive operation must have been paid for by cheap ones before it and leaves the tree flatter for the ones after it. Splay trees are also self-adjusting in a way the others are not: a key you access often keeps getting dragged back near the root, so a skewed access pattern gets faster than , which no fixed-shape balanced tree can do. And they achieve all of it with less code and less memory than AVL.
Three different bargains, then, over the same one legal move.
What it costs
| Plain BST | Weight-balanced | AVL | Splay | |
|---|---|---|---|---|
| Height | worst, if the order is random | worst | ||
| Lookup / insert / delete | amortised | |||
| Per-operation guarantee | none | yes | yes | no |
| Extra field per node | none | subtree size | height or balance factor | none |
| Rotations per insert | 0 | amortised | at most 2 | amortised |
| Bonus | simplest thing that works | -th smallest in | tightest height bound | adapts to the access pattern |
And, running underneath all four columns, the two facts this lecture is really about: everything costs the height, and the height is decided by the shape, which is decided by the order the data arrived in unless you take steps. Every balancing scheme in the table is one such step, and all of them are built from the same rotation that leaves the in-order reading alone. That is the sort of thing you keep for good. The particular constants of AVL you can look up; the idea that an invariant plus a cheap local repair buys a global guarantee is the transferable part.
Problems
Work these in order. The last four grade themselves; make every row green.
Warm-up, on paper. Insert the keys
7, 3, 9, 1, 5, 8, 10, 4into an empty binary search tree in that order and draw the result. What is its height, counting edges? What is the best possible height for eight nodes? Then write out the preorder, inorder, postorder, and level-order walks of your tree, and confirm that exactly one of the four came out sorted.The local check is not enough. Draw a binary tree of five nodes in which every node’s left child is smaller than it and every node’s right child is larger than it, and which is nevertheless not a binary search tree. Then say in one sentence what a lookup would do wrong on your tree, that is, which key it would fail to find and why.
Which walk, and why. For each task, name the traversal you would use and say in one clause why the others are wrong: (a) print a nested table of contents; (b) compute the height of every node; (c) list the keys of a search tree in sorted order; (d) find the shallowest node satisfying some property; (e) evaluate an arithmetic expression tree. One of these is the only one of the five that needs a queue.
Depth by depth. Implement
level_order, which returns the keys of a binary tree top to bottom, left to right. Use a queue, not recursion, and keep an index walking the list rather than callingpop(0), for the reason Lecture IV made painful. Run to grade against the checks.The checks · run against your code
# depth by depth, left to right t = build([50, 30, 70, 20, 40, 60, 80]) assert level_order(t) == [50, 30, 70, 20, 40, 60, 80] # which is NOT the preorder of the same tree assert level_order(t) != [50, 30, 20, 40, 70, 60, 80] # the empty tree gives an empty list, no crash assert level_order(None) == [] # a left spine comes out top to bottom assert level_order(build([5, 4, 3, 2, 1])) == [5, 4, 3, 2, 1] # a lopsided tree still comes out by depth assert level_order(build([50, 30, 70, 80])) == [50, 30, 70, 80]
python runs in your browser · first run downloads ~240 kbPlate VII Breadth first. level_order is stubbed; drive it with a queue so the keys come out by depth. The checks include the empty tree, a left spine, and one tree whose level order must NOT equal its preorder. Press Run to grade, or Trace to watch the queue fill and drain. Hint one
Start with the root in the queue. Then repeat: take the front node out, append its key to the output, and put its two children on the back. Children go on the back precisely so that everything at the current depth is dealt with before anything one level deeper.
Hint two
Handle
Nonein two places. The whole tree may be empty, and a node may have only one child, so check before you append a key. It is cleanest to letNonechildren go into the queue and skip them when they come out, or to test before enqueuing; either works, but pick one and be consistent.The solution
An index walks the list, so no element is ever shifted:
def level_order(root): out, q, i = [], [root], 0 while i < len(q): n = q[i] i += 1 if n is None: continue out.append(n.key) q.append(n.left) q.append(n.right) return outEvery node enters and leaves the queue exactly once, so this is time and, at worst, space: the queue holds a whole level at a time, and the widest level of a full tree is about half the nodes. Swap the queue for a stack and you get a depth-first walk instead, which is a good five-minute experiment: the code barely changes and the order changes completely.
The invariant, both directions. Implement
rotate_rightso it lifts the left child and returns the new subtree root. Exactly three references should move; the last check is the one that matters, because it asserts that the in-order reading came out identical. Run to grade.The checks · run against your code
# the lifted child becomes the new subtree root y = Node(50, Node(30, Node(20), Node(40)), Node(70)) r = rotate_right(y) assert r.key == 30 # the old root sinks to the right assert r.right.key == 50 # the middle subtree changes parents: 40 now hangs off 50's left assert r.right.left.key == 40 # the outer subtrees are untouched assert r.left.key == 20 assert r.right.right.key == 70 # and the whole point: the sorted order is unchanged assert inorder(r, []) == [20, 30, 40, 50, 70]
python runs in your browser · first run downloads ~240 kbPlate VIII One legal move. rotate_right is stubbed; lift y's left child, sink y to the right, and re-parent the middle subtree. The checks pin down all four displaced references, and then assert that the sorted reading of the subtree is unchanged, which is the licence rotations run on. Press Run to grade. Hint one
Name the child first:
x = y.left. Now there are three assignments to make and one value to return, and the order matters, because one of the three overwrites something you still need.Hint two
The subtree that changes parents is
x.right: it holds exactly the keys betweenxandy, so it must end up ony’s left. Save it, or use it, before you overwritex.rightwithy.The solution
Three lines, and the return is the point:
def rotate_right(y): x = y.left y.left = x.right x.right = y return xNothing inside the three subtrees is touched, so the cost is no matter how large they are. Returning the new root is what lets the caller write
node.left = rotate_right(node.left)and never think about parent pointers, which is the same conventioninsertuses. The mirror image,rotate_left, is this function with everyleftandrightswapped.The hard case. Implement
deletefor all three shapes: a leaf, a node with one child, and a node with two children. For the last one, usemin_nodeto find the successor in the right subtree, copy its key up, and then delete the successor from that subtree. Run to grade.The checks · run against your code
# deleting a leaf just drops it t = build([50, 30, 70, 20, 40, 60, 80]) t = delete(t, 20) assert inorder(t, []) == [30, 40, 50, 60, 70, 80] # deleting a node with one child splices that child up t = delete(t, 30) assert inorder(t, []) == [40, 50, 60, 70, 80] # deleting a node with two children keeps the order intact t = build([50, 30, 70, 20, 40, 60, 80]) t = delete(t, 30) assert inorder(t, []) == [20, 40, 50, 60, 70, 80] # the root with two children survives, replaced by its successor t = build([50, 30, 70, 20, 40, 60, 80]) t = delete(t, 50) assert t.key == 60 assert inorder(t, []) == [20, 30, 40, 60, 70, 80] # deleting a key that was never there changes nothing t = delete(t, 999) assert inorder(t, []) == [20, 30, 40, 60, 70, 80]
python runs in your browser · first run downloads ~240 kbPlate IX Removing a key without disconnecting a tree. delete is stubbed; min_node is given. The checks walk all three shapes, including deleting the root and deleting a key that was never there. The two-child case is not solved directly: it is turned into an easier one by moving a key instead of a node. Press Run to grade. Hint one
The recursive shape is the same as
insert: descend on the comparison, reassignnode.leftornode.rightto the result of the recursive call, and returnnodeat the end. Only the branch where the key matches is new.Hint two
In the matching branch, take the easy exits first. If
node.left is None, returnnode.right; that one line covers both the leaf case and the one-child case on that side. Then the mirror. Whatever is left has two children.Hint three
For two children:
s = min_node(node.right)is the successor and it has no left child by construction. Copys.keyintonode.key, then calldeleteonnode.rightfor that same key, and assign the result back. The recursive call is guaranteed to hit an easy case.The solution
Three exits in the matching branch, and only the third is interesting:
def delete(node, key): if node is None: return None if key < node.key: node.left = delete(node.left, key) elif key > node.key: node.right = delete(node.right, key) else: if node.left is None: return node.right if node.right is None: return node.left s = min_node(node.right) node.key = s.key node.right = delete(node.right, s.key) return nodeThe whole cost is one walk down to the node plus, at worst, one more walk down the right subtree to the successor, so delete is like everything else. Using the predecessor (the largest key on the left) instead works exactly as well, and some implementations alternate between the two so that repeated deletions do not gradually strip one side of the tree.
The unbalanced invariant, by hand. Using Plate VI: choose the Zig-zag order and step all seven keys in with Plain BST selected. Write down the height you end with. Now switch to AVL, which rebuilds the same order with rotations, and write down the height and the rotation count. Finally, back in Plain BST, reach AVL’s height using the Rotate buttons and count how many you needed. In two or three sentences: why does the balance factor turn rose one insertion before anything looks obviously wrong to you, and why is fixing an imbalance as it appears cheaper than fixing the finished tree?
Amortised is not worst-case. A splay tree holds the keys through and happens to be a single right spine. You look up key . In one sentence, what does that one operation cost, in notation? In one more, what does the tree look like afterwards, and what does the next lookup of cost? Then say, in two or three sentences, why ” amortised” is a perfectly good guarantee for a compiler’s symbol table and a poor one for the audio thread of a synthesiser.
An aside: B-trees, and balance without rotation
Every scheme in this lecture kept the same two assumptions: the tree is binary, one key to a node, and the only legal move is the rotation. B-trees drop both, and the reason they do is not aesthetic. It is that the tree does not fit in memory.
Start with the shape. A B-tree node holds not one key but a whole sorted run of them, with one more child than it has keys, so that the children fan out into the gaps between consecutive keys exactly the way a binary node fans left and right around its single key. The playground below uses a deliberately small one: minimum degree , meaning every node holds between and keys (that is ) and every internal node has between and children. A production B-tree sets in the hundreds, so a single node is hundreds of keys wide.
Now the balancing rule, which never rotates anything. Insertion always walks down to a leaf and drops the new key into its sorted place. Then it walks back up, and the one thing it watches for is overflow: a node that has been pushed to a fourth key here (to keys in general) is too full, so it splits. The median key rises into the parent, and the node becomes two, one key to the left and the remaining two to the right, each keeping its share of the children. If the overflow travels all the way to the root, the root itself splits and a brand new root of a single key is minted above it, and the whole tree grows one level taller. That is the only way a B-tree ever gains height. Because height is only ever added at the very top, every leaf stays at exactly the same depth: the tree is kept perfectly balanced by construction, not repaired into balance after the fact.
Why go to this trouble when AVL already guarantees ? Because on disk the unit of work is not the comparison, it is the block read, and a read hauls up a whole block whether you wanted one key or four hundred. The cost that matters is the number of nodes on the path, that is, the height, and a B-tree of minimum degree has height : a B-tree of order is tall. Push the base of that logarithm up into the hundreds and a tree of millions of keys is three or four levels deep, which is three or four disk reads to find anything. That is the whole reason databases and filesystems index on B-trees rather than on the binary trees in the table above.
The plate opens on a small B-tree with eight keys already inserted, the sequence . Press Reset to empty it, then Insert next repeatedly to replay that build from nothing and watch a node reach its fourth key, split, and send its median upward; the node that just split is outlined in ochre for a moment so you can see where the pressure went. Type a key of your own and Insert, or let Random pick one; a key already present is ignored, since the keys are a set.
Showing the tree after inserting 10, 20, 5, 6, 12, 30, 7, 17. Press Reset, then Insert next repeatedly to watch it build and split from empty.