57The binary search tree — order that stays searchable

In Chapter 56 we built the binary tree. Nodes on the heap, two children apiece, hierarchy for its own sake. Here we add one ruthless rule to that skeleton, and it turns into a search engine. Here is the tension it resolves. A sorted array can binary-search in O(log n). But insert one value in the middle and every element after it shifts, an O(n) tax on every change. A hash table gives O(1) lookup, and then throws order in the bin. It cannot tell you the smallest key, or every key between 100 and 200. The binary search tree is the deal that keeps both. It stays sorted and stays fast to change, by holding order not in memory positions but in pointers. The one question we keep asking is this: what does it cost to keep a collection sorted while it is still changing under your hands? By the end you will insert, search, and delete in a BST. You will see why one careless insertion order can rot it into a slow linked list. And you will know the fix that runs every database index on Earth.

01One rule, wired into every pointer

Let's start from what we already have. When we built the binary tree back in Chapter 56, each node lived on the heap. It held its data and up to two child pointers, left and right. That was hierarchy, and nothing more. A BST is that same skeleton plus a single, ruthless invariant. An invariant is a rule that must hold at every node, without exception: everything in my left subtree is less than me, and everything in my right subtree is greater than me. Watch how far that reaches. Not just my two children, but my entire left subtree, all the way down, and my entire right subtree. That one promise is what turns a plain tree into a search structure.

Why does that promise reach the whole subtree and not just the two children? Because the rule compounds down every level. My left child is less than me, and everything in that child's own right subtree is less than the child — so by simple transitivity it is less than me as well. Chain that reasoning down rung by rung and the ordering holds for the entire left subtree, all the way to the leaves. That is the quiet magic of the design: each node only ever checks its own two children, yet the order it enforces spans the whole tree beneath it. A cheap local rule buys a global guarantee.

Because the rule holds everywhere, a BST has a hidden talent you first met in the binary-tree chapter. Walk it in-order, which means left subtree, then the node, then right subtree. The keys come out sorted, for free, with no sorting step. We built one and walked it:

class Node:
    __slots__ = ("key", "left", "right")   # three references, nothing else
    def __init__(self, key):
        self.key  = key
        self.left = None                    # < me
        self.right = None                   # > me

root = None
for k in [4, 2, 6, 1, 3, 5, 7]:            # inserted in this order
    root = insert(root, k)

out = []
inorder(root, out)
print(out)          # [1, 2, 3, 4, 5, 6, 7]   ← sorted, though we never sorted

Line by line: each Node is three references and nothing more — the key, a left pointer, and a right pointer. We insert seven keys in a jumbled order, then run an in-order walk, and it prints them back as 1 2 3 4 5 6 7. That sorted output falls straight out of the invariant, because "smaller stuff is always on the left" is exactly what an in-order walk visits first. Order was never stored anywhere. It is implied by where the pointers go.

Now for the memory bill, run for real: a node with __slots__ is the leanest a Python BST node gets, and we measured what one actually costs:

import sys
sys.getsizeof(Node(30))          # 56   ← 16 GC + 16 header + 3×8 pointers
# a plain class (no __slots__):
sys.getsizeof(dict_node)         # 48   object…
sys.getsizeof(dict_node.__dict__)# 296  …plus its instance dict = 344 total
# the same 1000 ints in a Python list:
sys.getsizeof(list(range(1000))) # 8056 → ~8 bytes per reference

Read the tax. Every BST node costs 56 bytes at best, or 344 if you skip __slots__. Of that, only 24 bytes is the data-carrying part, which is three 8-byte references. The rest is Python's per-object overhead. That is Vol 1's ~32-byte object header, here split as a 16-byte GC header and a 16-byte object head. A plain list stores those same references at 8 bytes each in one contiguous block. So a BST is roughly 7× heavier per element than a list. You are paying that overhead to buy something a list can't give you: sorted order that survives insertion and deletion in O(log n). Whether that trade is worth it is the whole question of the chapter.

Put a real number on that 7× overhead so it stops being abstract. Store 1000 keys and the BST spends 1000 × 56 bytes, which is 56,000 bytes just for nodes. The same 1000 references packed into a list cost 1000 × 8, a mere 8,000 bytes. Divide and the ratio pops right back out: 56,000 ÷ 8,000 is exactly 7. You are handing the allocator 48,000 extra bytes to buy one thing the list cannot give you — sorted order that survives every insert and delete. On a laptop with gigabytes of RAM that is loose change; on an embedded board with 64 KB of memory it may be the whole design decision.

The invariant isn't decoration. It's a machine for cutting the problem in half at every step →

02Search: a binary search that walks pointers

Here is where the invariant pays off. To find a key you start at the root and compare, and there are three outcomes. Equal means you found it, so stop. Target is smaller means the invariant guarantees it can only be in the left subtree, so the entire right subtree is eliminated in one comparison. Target is larger sends you right, and the whole left subtree is gone in the same stroke. Each comparison throws away one of the two subtrees, and that is binary search, the halving technique from Volume 3. But instead of indexing into a sorted array, you are following pointers down a tree:

Try one search by hand on a tree whose root is 50. Say the left subtree holds smaller keys and the right holds larger all the way down, and we are hunting for 40. Compare 40 with 50. It is smaller, so in one step we discard the entire right half of the tree and step left. We land on, say, 30, and now we compare 40 with 30. This time it is larger, so we discard 30's left subtree and step right. Each comparison is cheap, and each one deletes a whole region of the tree from the hunt. We are not scanning keys one by one — we are halving the field at every hop.

def search(root, target):
    node = root
    while node is not None:          # until we fall off the tree
        if target == node.key:
            return node              # found — stop
        elif target < node.key:
            node = node.left         # smaller → whole right subtree gone
        else:
            node = node.right        # larger  → whole left subtree gone
    return None                      # ran out of tree → not present

Line by line: we hold a moving pointer node, starting at the root. Each loop is one comparison. If equal, done. If target < node.key we step left; otherwise right. When node becomes None we've walked off a branch tip without a match — the key isn't there. The number of loops is exactly the number of levels we descend: the path length from root to where the key is (or would be).

So search costs O(h), where h is the tree's height, the longest root-to-leaf path. And here is the crux. If the tree is balanced, each level roughly doubles the node count: 1, 2, 4, 8, and so on. So n nodes fit in about log₂ n levels, and search is O(log n). We built a million-node tree and searched it:

# tree of 1,000,000 keys, inserted in random order:
#   height              = 50        (log2(1,000,000) ≈ 19.9)
#   search steps for 20 random keys: min 17, max 35, avg 26.1

A million keys, and a lookup touches on average 26 nodes, not a million — that is the log at work, with each of those 26 comparisons halving what remained. The height here is 50 rather than the ideal 20, because a randomly-built BST is only roughly balanced. More on that, and on how to force it down to 20, is coming shortly.

Let's make that log concrete, because it is the whole reason the tree is fast, and the trick to hold onto is doubling. One level holds 1 node, two levels hold up to 3, and ten levels hold up to 1023, since 2^10 is 1024. Keep doubling and 2^20 reaches 1,048,576, which is just past a million. So a perfectly balanced million-key tree is about 20 levels tall, and a lookup makes at most 20 comparisons. That is why 26 nodes can answer a million-key query: each step down does not shave off one candidate, it throws away half of what is left.

Hold those two numbers side by side, because the gap between them is the entire payoff. A flat linear scan of a million keys is up to a million comparisons in the worst case. The balanced tree answers the exact same question in about 20. That is a fifty-thousand-fold cut in work — 1,000,000 ÷ 20 is 50,000 — bought with nothing but the shape of the pointers. And the trade only sweetens as the data grows. Every level you add doubles the keys the tree can hold, so the cost creeps up by one comparison while the capacity leaps by a factor of two.

Search reads the tree. Insert has to grow it — and it turns out inserting is just searching for the empty spot where the key belongs →

03Insert: search for where it isn't, then hang a node

Here's the trick that makes insert almost free: it reuses search entirely. To add a key, you search for it, comparing and stepping left or right, until you fall off the bottom of the tree at a None. That spot is exactly where the key belongs. The path you walked is the same path a future search will walk to find it. So you allocate a new node and hang it there. One walk down, one link:

def insert(root, key):
    if root is None:                 # empty spot found → this is the place
        return Node(key)
    if key < root.key:
        root.left  = insert(root.left,  key)   # belongs somewhere on the left
    elif key > root.key:
        root.right = insert(root.right, key)   # …or somewhere on the right
    # key == root.key: already present, do nothing (a BST holds a set)
    return root

Line by line: hit a None and you have arrived. Return a fresh node, and the caller links it in. Otherwise compare and recurse into the correct subtree, re-attaching the possibly grown subtree on the way back up. Equal keys are ignored here, so this BST behaves as a set. The cost is the length of the walk, which is O(h) again, the same descent as search, plus one node allocation. Crucially, the existing nodes never move. Unlike a sorted array, inserting into the middle of the key range shifts nothing. You only rewire one None into a pointer.

Why is the freshly allocated node guaranteed to land somewhere legal? Follow the logic of the walk that got you there. At every node along the way you compared and turned toward the side the key belongs on, so by the time you fall off the bottom at a None, every ancestor above you has already agreed the key sits on its correct side of them. The empty slot you arrived at is therefore the one place in the whole tree that keeps the invariant intact. That is why insert can stay blissfully careless about the rest of the tree and never break it — the search already did the checking on the way down.

Walk one insert by hand to feel it. Start with an empty tree and add 50. It becomes the root, since there is nothing to compare against. Now add 30. Compare with 50, 30 is smaller, so step left, and the left slot is empty, so 30 hangs there. Add 70. Compare with 50, 70 is larger, so step right into the empty slot. Add 40. Compare with 50 and go left to 30, then compare with 30 and go right into its empty slot. Four keys, four short walks, and no existing node ever moved. That is the whole operation.

Insert always plants the node at the end of its search path. Which raises a dangerous question: what if every key's search path leads to the same side — every single time? →

04The catastrophe: sorted input collapses the tree into a list

Everything above assumed the tree is bushy, short and wide, but nothing in insert guarantees that. The shape is decided entirely by the order keys arrive in, so feed a BST already-sorted data and watch what happens. Insert 1 and it becomes the root. Insert 2, which is bigger, so go right. Insert 3, bigger than 1 so go right, then bigger than 2 so go right again. Every new key is the largest so far, so every insert goes right, right, right, and the tree grows a single right-leaning limb with no left children at all. We ran it and measured the heights:

# insert 1,2,3,4,5,6,7 in that order → height = 7   (a chain of 7)
# insert 4,2,6,1,3,5,7 (jumbled)      → height = 3   (a bushy tree)

#        n   sorted-insert height   random-insert height   log2(n)
#       15                     15                      8      3.9
#     1000                   1000                     20     10.0
#    10000                  10000                     30     13.3
#    30000                  30000                     36     14.9

Read the columns of horror. Sorted insertion gives height exactly n: every node has a single child, forming one straight line. That is no longer a tree at all. It is a linked list that happens to store its "next" pointer in the right field, and a linked list means search is O(n) — to find the last key you walk all n nodes. The BST's entire reason for existing, O(log n), is gone. The random column shows what balance would give you instead: 1000 keys in height 20, and 30000 keys in height 36, hugging log₂ n. Same keys, same code, same invariant, and yet a 50× difference in height, decided only by arrival order.

You might now worry that every real tree collapses. It does not, and here is the honest reason. If keys arrive in random order, each new key is about as likely to go left as right at every node, so the tree tends to stay bushy on its own. That is why the random column sat near log₂ n without any special effort. The danger is not randomness. It is structure in the input: already-sorted data, reverse-sorted data, or a long run of increasing keys. Those patterns are common in the wild, which is exactly why nobody ships a plain BST for serious work. They ship one that refuses to lean, no matter what order you feed it.

We even timed the collapse, searching for the deepest key in each tree:

#   n     degenerate (chain)   balanced (random)
#  1000        115 µs               1.06 µs
#  2000        231 µs               1.06 µs
#  4000        462 µs               0.55 µs

The degenerate column doubles as n doubles, the fingerprint of O(n). The balanced column just sits near a microsecond no matter the size, the fingerprint of O(log n). At n=4000 the balanced tree answers roughly 800× faster for the same keys. These timings are from this machine and will vary run to run. But the shapes, one line climbing and one flat, are the invariant truth.

from dataclasses import dataclass
from typing import Optional
import random, sys

@dataclass(slots=True)
class Node:
    key: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def insert(root, key):
    """The recursive version: walk to the empty slot, then hang a node there."""
    if root is None:
        return Node(key)                       # the slot - this is the place
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                                # equal: a BST holds a set

def contains(root, key):
    """Iterative on purpose - a spine must not be able to blow the stack."""
    node, compares = root, 0
    while node is not None:
        compares += 1
        if key == node.key:
            return True, compares
        node = node.left if key < node.key else node.right
    return False, compares

def build(keys):
    """Iterative insert, so 1000 sorted keys cannot raise RecursionError."""
    root = None
    for k in keys:
        if root is None:
            root = Node(k); continue
        cur = root
        while True:
            if k < cur.key:
                if cur.left is None:  cur.left  = Node(k); break
                cur = cur.left
            elif k > cur.key:
                if cur.right is None: cur.right = Node(k); break
                cur = cur.right
            else:
                break
    return root

def height(root):
    """Explicit stack: measures a 1000-deep spine without recursing 1000 times."""
    best, stack = -1, [(root, 0)]
    while stack:
        n, d = stack.pop()
        if n is None:
            best = max(best, d - 1); continue
        stack.append((n.left, d + 1)); stack.append((n.right, d + 1))
    return best

random.seed(57)
print("--- the two shapes, same 1000 keys ---")
keys = list(range(1000))
shuffled = keys[:]; random.shuffle(shuffled)
for label, feed in (("random order", shuffled), ("sorted order", keys)):
    root = build(feed)
    found, compares = contains(root, 999)
    print(f"  {label}: height = {height(root):4}   contains(999) -> {found},"
          f" {compares} compares")

print("\n--- height vs n ---")
for n in (100, 1000, 10_000):
    s = list(range(n)); random.shuffle(s)
    print(f"  n={n:6,}   random height {height(build(s)):5}"
          f"   sorted height {height(build(range(n))):6}"
          f"   log2(n) = {(n-1).bit_length():2}")

print("\n--- and the recursive insert, fed sorted input ---")
print("  sys.getrecursionlimit() =", sys.getrecursionlimit())
try:
    root = None
    for k in range(3000):
        root = insert(root, k)
    print("  survived 3000 sorted inserts")
except RecursionError as e:
    print("  RecursionError:", e)

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# --- the two shapes, same 1000 keys ---
#   random order: height =   23   contains(999) -> True, 11 compares
#   sorted order: height =  999   contains(999) -> True, 1000 compares
#
# --- height vs n ---
#   n=   100   random height    12   sorted height     99   log2(n) =  7
#   n= 1,000   random height    22   sorted height    999   log2(n) = 10
#   n=10,000   random height    31   sorted height   9999   log2(n) = 14
#
# --- and the recursive insert, fed sorted input ---
#   sys.getrecursionlimit() = 1000
#   RecursionError: maximum recursion depth exceeded

A structure whose whole value can be destroyed by sorted input is a structure begging for a guardian. Humans built one →

05The fix humans invented: trees that rebalance themselves

The degeneracy problem has a clean statement: after enough one-sided inserts, the tree gets tall. So the fix is a structure that notices when it's leaning and straightens itself back out, a self-balancing tree. The key mechanical trick is the rotation. A rotation is a small, local rewiring of three or four pointers. It lifts a deep subtree up and pushes a shallow one down, without breaking the left<node<right invariant. A rotation is O(1), because it touches a constant number of pointers. It changes the tree's shape but not its sorted meaning.

Here is a rotation in the flesh, on the leaning chain the figure shows. We have 30 at the root, its left child 20, and 20's left child 10. To straighten it, we rotate 20 up into the root's place. Now 30 becomes the right child of 20, and 10 stays as 20's left child. We rewired a handful of pointers and nothing else. Read the new tree in-order and you still get 10, 20, 30, exactly as before. The shape got shorter, from three levels down to two, but the sorted meaning never budged. That invariance is why a self-balancing tree can rotate freely after every insert.

Two famous designs wrap rotations in a self-balancing policy. You use their descendants constantly, so meet them by name. An AVL tree keeps every node's two subtree heights within 1 of each other. The moment an insert violates that, it rotates. It is the strictest, so it is the shortest and the fastest to search. A red-black tree is looser. It colours nodes red or black and enforces rules that keep the longest path at most twice the shortest. That means fewer rotations on insert and delete, a better all-round trade. We stay at the concept here. The promise is "height stays O(log n)", and the exact rotation cases are a topic of their own. Red-black trees are not academic trivia. They are the ordered map and ordered set in your standard library: C++'s std::map/std::set, Java's TreeMap/TreeSet, and the Linux kernel's process scheduler and virtual-memory areas. Every time you iterate a Java TreeMap in sorted order, you are walking a balanced BST in-order.

One assumption has been quietly holding all of this up: the tree lives in RAM, where chasing a pointer costs a few nanoseconds and you can afford 20 or 30 of them per lookup. Change that single assumption and the whole design shifts under your feet. Put the tree on disk — a database index far too big to fit in memory — and every pointer you follow can become a physical read from storage. Now the number that decides your speed is not comparisons but disk reads, and a skinny binary tree, branching only two ways per level, forces far too many of them. That change of venue, from memory to disk, is exactly what summons the next structure.

Why fat nodes for disk? This is mandate #3, how the machine gets the benefit. It is the same cache story from Volume 3, one level down. Reading from a disk, even an SSD, happens in fixed blocks of typically 4 KB or more. And a single disk seek is glacial next to RAM, hundreds of thousands of times slower. A binary tree of a billion keys is ~30 levels deep. So a lookup could be 30 separate disk seeks, which is catastrophic. A B-tree sizes each node to fill exactly one disk block, packing perhaps 100–500 keys into it. Now the tree is only 3–4 levels deep for a billion keys, because each level branches 100+ ways instead of 2. A lookup is 3–4 block reads instead of 30 seeks. The design move is simple: match the node to the transfer unit of the storage. Pointer-chasing a skinny binary tree wastes almost the entire block it drags in. A B-tree makes every expensive block read carry hundreds of useful keys.

The fan-out arithmetic is worth doing once. Suppose each B-tree node holds 200 keys, which gives it about 200 children. One level reaches 200 nodes, and two levels reach 200 × 200, or 40,000. Three levels reach 200 × 40,000, which is 8 million, and four levels reach 1.6 billion, comfortably past a billion keys. That is the whole magic: widen each node and the depth collapses. Four block reads, and you have found your row in a billion.

Search, insert, and balance handle growing the tree. One operation is still missing, and it's the only one with a genuine puzzle in it: taking a node out →

06Delete: the operation with a twist

Deleting from a BST has to preserve the invariant, and that makes it the one operation with real cases. Find the node (an O(h) search), then handle three situations by how many children it has:

Make the three cases concrete with a small tree. Say the root is 50, with 30 on the left and 70 on the right, and 70 has one child 60. Deleting 30 is the easy case. It is a leaf with no children, so we null out the pointer to it and we're done. Deleting 70 is the one-child case. It has only the child 60, so we splice 60 up into 70's place, and the branch stays legal. The hard case is deleting 50, the root, which has two children. We cannot just null it, and we cannot pick either child, because that would strand the other subtree. That is why we need one specific replacement value, and the successor is what gives it to us.

• No children (a leaf). Easiest: just null out the parent's pointer to it. The node vanishes; refcount drops to zero; Python reclaims it (Vol 1).
• One child. Splice it out — connect the node's parent directly to the node's single child. The subtree slides up one level, order intact.
• Two children. The puzzle. You can't just remove it — two subtrees would be orphaned. The classic fix: don't remove the node, overwrite its key with its in-order successor — the smallest key in its right subtree, which is exactly the next value in sorted order — then delete that successor (which, being leftmost, has at most one child, reducing to an easy case).

Why the successor works: the smallest key on the right is larger than everything on the left, and smaller than everything else on the right. So it is the unique value that can sit in the vacated spot without breaking left<node<right. We ran all three cases and checked the in-order output stayed sorted after each:

def delete(root, key):
    if root is None: return None
    if key < root.key:   root.left  = delete(root.left,  key)
    elif key > root.key: root.right = delete(root.right, key)
    else:                                     # found the node to remove
        if root.left  is None: return root.right   # 0/1 child
        if root.right is None: return root.left    # 1 child
        succ = root.right                          # 2 children:
        while succ.left is not None:               #   find in-order successor
            succ = succ.left                       #   (leftmost of right subtree)
        root.key = succ.key                        # overwrite, don't unlink
        root.right = delete(root.right, succ.key)  # delete the successor
    return root

Line by line: the first two branches are just search, recursing left or right and re-linking. Once found, if a child is missing, return the other child. That covers the leaf and one-child cases in two lines. With two children, walk right then left-to-the-end to reach the successor. Copy its key up into the current node, and delete the successor from the right subtree. The output confirmed order held through every case:

# start:            [1, 2, 3, 4, 5, 6, 7, 8, 9]
# delete leaf 1:    [2, 3, 4, 5, 6, 7, 8, 9]
# delete 7 (1 child)[2, 3, 4, 5, 6, 8, 9]
# delete 3 (2 kids) [2, 4, 5, 6, 8, 9]   ← 3 replaced by successor 4
# delete root 5     [2, 4, 6, 8, 9]      ← new root is successor 6

Every line is still perfectly sorted. The invariant survived deletion of a leaf, a one-child node, a two-child node, and even the root. All of it is O(h): a search to find the node plus a walk to the successor, both bounded by the height. In a balanced tree that is O(log n), and in that degenerate chain, O(n). So the same tax hangs over delete as over everything else in the tree.

That question is the whole point of learning structures. The answer is the last idea in the chapter →

07When to reach for a tree — the access pattern is the answer

A hash table wins on a single point lookup, hands down. "Is key X here, and what's its value?" answers in O(1) versus O(log n). If that is all you do, use the dict, and don't reach for a tree to feel clever. The tree earns its keep the moment your questions become ordered ones. Those are the exact questions a hash table, which scatters keys to random slots, physically cannot answer without scanning everything:

• Range queries. "All keys between 100 and 200." In a balanced BST: find 100 in O(log n), then walk in-order until you pass 200. A hash table would have to examine every key.
• Order statistics & neighbours. Smallest key, largest key, the next key above X, the previous key below X — all O(log n) in a tree, all impossible-without-a-scan in a hash.
• Sorted iteration. "Give me everything in order." An in-order walk, O(n) with no separate sort. A hash table would need to extract and sort, O(n log n).

That's the transferable move, mandate #5: choosing the structure is choosing which questions are cheap. If all you do is point lookups, reach for a hash. If you need ordered questions on data that keeps changing, reach for a balanced tree. And if the ordered data rarely changes, you don't even need a tree — sort an array once and binary-search it, as in Volume 3, because a contiguous array streams through cache far faster than a tree of scattered nodes. The decision table:

INPUTimport bisect

board = []
for score in [512, 340, 780, 195, 640]:
    bisect.insort(board, score)          # walk to the slot, then insert there
    print(f"insort({score:3}) -> {board}")

i = bisect.bisect_left(board, 640)
print("\nwhere would 500 go?  ", bisect.bisect_left(board, 500))
print("is 640 stored?       ", i < len(board) and board[i] == 640)
print("everything 340..640: ",
      board[bisect.bisect_left(board, 340):bisect.bisect_right(board, 640)])
print("the top three:       ", board[-3:][::-1])

dup = [1, 2, 2, 2, 3]                    # _left lands before the equals, _right after
print("left/right on dups:  ", bisect.bisect_left(dup, 2), bisect.bisect_right(dup, 2))

people = [("ana", 31), ("bo", 44), ("cy", 58)]
bisect.insort(people, ("dee", 50), key=lambda p: p[1])   # 3.10+
print("insort by key=age:   ", people)

OUTPUTinsort(512) -> [512]
insort(340) -> [340, 512]
insort(780) -> [340, 512, 780]
insort(195) -> [195, 340, 512, 780]
insort(640) -> [195, 340, 512, 640, 780]

where would 500 go?   2
is 640 stored?        True
everything 340..640:  [340, 512, 640]
the top three:        [780, 640, 512]
left/right on dups:   1 4
insort by key=age:    [('ana', 31), ('bo', 44), ('dee', 50), ('cy', 58)]

A BST spends O(log n) to keep total order — every key rank exact. But a huge class of problems doesn't need the whole order — only "what's the most extreme one right now?" Give up full sorting, keep just that, and you get a structure so lean it lives in a flat array with no pointers at all. That's the heap, chapter 58 →