P-4.5 Trees and Binary Search Trees

What this is and why it exists

A search tree keeps data in order while still finding things quickly. A hash table cannot do that: it can find one key fast and has no idea which key comes next.

Everything about a search tree depends on its shape. Balanced, it gives logarithmic operations. Degenerate, it is a linked list wearing a tree's vocabulary.

That is why the interesting structures are the self-balancing ones. It is also why understanding the plain version first makes them comprehensible rather than magical.

The vocabulary

• Root — the node designated as the top.
• Child — a node directly below another.
• Leaf — a node with no children.
• Height — the length of the longest path down from the root.
• Binary search property — smaller on one side, larger on the other.
• Traversal — a defined order for visiting every node.
• Degenerate — a tree whose height equals its number of nodes.
• Self-balancing — a tree that does extra work to keep its height small.

The mental model

A tree is nodes connected without cycles, with one node designated the top. Height is the longest way down from it. Almost every cost in this topic is stated in terms of height, so keep that word close.

The binary search property is the engine. Everything smaller sits on one side, everything larger on the other. So each comparison discards half of what is left. That is the entire reason a search tree beats scanning. It should feel like the same idea as looking up a word in a dictionary.

Now the failure, which is more interesting than the success. Insert already-sorted values and every new item goes down the same side. The result is a tree of height equal to its size — a linked list. Nothing reports a problem. The code is correct, the structure is valid, and the performance is gone. This is worth doing once deliberately, because sorted input is not exotic. It is what you get from a database query that returned rows in order.

Traversals come next. Visiting in order yields the values sorted, which is the property a hash table cannot offer and the reason to choose this structure at all. The other orders have their own jobs: one for copying and evaluating structured expressions, another for deleting safely from the bottom up.

Which brings us to balancing. Self-balancing trees do extra work on every insertion to keep the height logarithmic. What you are buying is the conversion of an unpredictable worst case into a guaranteed bound. Understanding *that trade* matters considerably more than memorising the rotations, and it is the part that transfers to every other balanced structure you will meet.

What you should now be able to explain or do

Implement a binary search tree with insertion, lookup and traversal. State costs in terms of height. Explain why each comparison discards half the remaining possibilities. Show how sorted input produces the worst possible shape, and say why that is a realistic accident. Say what each traversal order is for. State what balancing guarantees and what it costs per insertion.

Check yourself