Computer Science › Section I · Data abstractions › Topic I.4
A short case study: a binary tree
Suppose a program must keep names in alphabetical order, find any of them fast, and accept new ones at any time. Storing the list as a binary search tree does all three with three short recursive functions, and shows a data structure being built as a complete abstract tool.
The job: a list kept in order
A club's program keeps members' names in alphabetical order and must search for a name, print the list in order, and insert new names. A linked list makes insertion easy, but searching it means checking entries one by one, as in "Iterative structures: sequential search and insertion sort". A sorted array allows the faster binary search of "Recursive structures: binary search", but every insertion shuffles entries along. The solution here: a binary tree arranged so that binary search still works and new entries never force anything to move.
Turning a sorted list into a tree
Binary search looks first at the middle entry, then at the middle of one half, and so on. So make the middle entry the root, the middle of the first half its left child and the middle of the second half its right child, and repeat in each part, taking the middle of positions Low to High as (Low + High) div 2. The result is a binary search tree: for every node, all entries in its left subtree come before it and all entries in its right subtree come after it. Each node holds three fields: Value, and pointers Left and Right. None stands for the null pointer.
Worked example: building the tree
Build the tree for the 11 letters B, D, F, H, J, L, N, P, R, T, V. 1. The middle of positions 1 to 11 is 6, so L is the root. 2. Positions 1 to 5 give 3, so F is the left child; positions 7 to 11 give 9, so R is the right child. 3. Below F: B, with right child D, and H, with right child J. 4. Below R: N with right child P, and T with right child V. 5. Check: the tree has 4 levels, matching the \(\lfloor \log_2 11 \rfloor + 1 = 4\) entries binary search examines at most in a list of 11, and every left subtree holds only earlier letters.
Searching the tree
To search, compare the target X with the root. A match ends the search; otherwise only one subtree can hold X, so search that subtree the same way.
T points to the root of the tree or subtree being searched, and reaching None, the base case, means X is absent. This is binary search on ever smaller subtrees instead of ranges.
Worked example: two searches
Search the 11-letter tree, first for P. 1. P comes after L, so go right to R. 2. P comes before R, so go left to N. 3. P comes after N, so go right to P. 4. A match: Search returns the node holding P after 4 comparisons. Now search for K. 5. K comes before L, so go left to F. 6. K comes after F, so go right to H. 7. K comes after H, so go right to J. 8. K comes after J, but J's right pointer is None, so the next call returns None: K is absent. Again only 4 nodes were examined, never all 11.
Printing in alphabetical order
Printing seems harder, since the names are spread over several levels. But every entry left of a node comes before it and every entry on its right after it. So print the left subtree in order, then the root, then the right subtree in order. Each subtree is a smaller version of the same task, so the function is recursive.
An empty tree prints nothing. This order of visiting nodes is called an in-order traversal.
Worked example: tracing PrintTree
Trace PrintTree on the subtree rooted at F: B with right child D, and H with right child J. 1. PrintTree(F) first calls PrintTree(B). 2. B's left subtree is empty and prints nothing; then B is printed, then PrintTree(D) prints D. 3. Back in the call for F, F is printed. 4. PrintTree(H) prints nothing on the left, then H, then J. 5. The output is B, D, F, H, J, in alphabetical order. 6. Count the calls: one for each of the 5 nodes and one for each of the 6 empty subtrees, 11 in all. Every call works on a smaller tree than its caller, so an empty tree, the base case, is always reached.
Inserting a new entry
A new entry never needs room cut inside the tree: it becomes a new leaf. Search for it; being absent, the search ends at a None pointer, exactly where it belongs. NewNode(X) creates a node holding X with two None pointers.
Each call returns its subtree's root, so the parent's pointer is reset to the same node or set to the new leaf. If X is already present, nothing changes.
Worked example: inserting K
Insert K into the tree of 11 letters. 1. K comes before L, so Insert is called on the subtree rooted at F. 2. K comes after F, so it moves on to H, then J: the path of the failed search. 3. J's right pointer is None, so that call returns a new node holding K. 4. The call for J stores it in J.Right; every other call returns its own node, leaving those pointers unchanged. 5. Check: PrintTree now gives B, D, F, H, J, K, L, N, P, R, T, V. No node moved and one pointer changed, but the tree now has 5 levels.
When a tree loses its shape
Speed depends on shape. A balanced tree of n entries has about \(\log_2 n\) levels, so a search examines few nodes. But insertions can unbalance it. Insert A, B, C, D, E one at a time into an empty tree: each letter is larger than all before it, so it becomes the right child of the previous one. The result is a chain of 5 levels, searched no faster than by sequential search. Many libraries therefore use self-balancing designs, such as AVL and red-black trees, which reshape the tree after insertions so its levels stay a small multiple of \(\log_2 n\).
Common mistakes to avoid
First, reversing PrintTree's test to if (T == None), so it ignores real trees and fails on empty ones when reading T.Left. Second, printing the root before its left subtree, which loses alphabetical order. Third, forgetting to return the result of a recursive Search or Insert call, so the answer never reaches the first call. Fourth, believing an insertion must reorganise the tree; it only adds a leaf. Fifth, assuming every binary search tree is fast: sorted insertions produce a chain.
Key takeaways
A binary search tree keeps earlier entries in each node's left subtree and later ones in its right subtree. Building it from a sorted list by repeatedly taking the middle entry gives a balanced tree. Search compares with the root and recurses into one subtree, which is binary search on a tree. PrintTree prints the left subtree, the root and the right subtree: an in-order traversal. Insert follows the search path and attaches a new leaf where it meets None. Together they make a complete abstract tool, though unbalanced trees slow down.
Flashcards
Flashcard
A binary tree with earlier entries left of each node and later entries right
Test your understanding
Question 1 of 5
The sorted list 10, 20, 30, 40, 50, 60 is built into a tree by taking the middle entry, with Mid = (Low + High) div 2. What are the root and its right child?
Question 2 of 5
The tree built from B, D, F, H, J, L, N, P, R, T, V has root L, with R as L's right child, N as R's left child and P as N's right child. Searching for M, which entries are compared before the search fails?
Question 3 of 5
A binary search tree has root 8; 8's children are 3 and 10; 3's children are 1 and 6; 10 has only a right child, 14. What does PrintTree output?
Question 4 of 5
In the same tree (root 8, children 3 and 10, 3's children 1 and 6, 10's right child 14), where does Insert place the value 7?
Question 5 of 5
The values 5, 10, 15, 20, 25, 30 are inserted one at a time, in that order, into an empty tree. How many nodes does a search for 30 examine?
