B4.1.4 · Abstract data types (ADTs)
Binary search trees
By the end you can
Construct and trace binary search trees (BST), evaluating logarithmic average search versus O(n) degenerate skewing.
A general binary tree allows values to sit in any arbitrary position. A adds a strict mathematical ordering rule that enables rapid logarithmic search, insertion, and deletion:
- All keys in the left subtree of $X$ are < $X$.
- All keys in the right subtree of $X$ are > $X$.
Searching and inserting in a BST#
Searching for a target value $K$ in a BST works like Binary Search on an array:
- Start at the
rootnode. - If
root == null, the key is absent. - If
K == root.value, search succeeds! - If
K < root.value, recurse into the left subtree (discarding the entire right subtree). - If
K > root.value, recurse into the right subtree (discarding the entire left subtree).
Insertion follows the exact same path: walk down the tree following the comparison rules until you encounter a null pointer, then attach the new node there as a new leaf.
The danger of degenerate (skewed) trees#
In a balanced BST with $n = 1,000,000$ nodes, the tree height is $\approx \log_2(1,000,000) \approx 20$. A search completes in just 20 comparisons ($O(\log n)$).
However, what happens if you insert already-sorted data ([10, 20, 30, 40, 50])? Every new node is larger than the previous one and is placed on the right. The tree degenerates into a straight single-line linked list! Searching for the last item now takes $n$ comparisons ($O(n)$). To prevent this, production databases use self-balancing trees (such as AVL trees or B-trees) that automatically rotate nodes to maintain balanced height.
Check yourself
Binary search trees
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 9 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Describe the binary search tree (BST) ordering property that distinguishes it from a general binary tree, and explain how it enables efficient searching.
[4]Describe: A detailed account: say what happens, step by step if it is a process.
2.Explain why the worst-case search time complexity of a BST is O(n) while the average case is O(log n).
[3]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.State what mathematical sequence is produced when performing an In-order traversal on a binary search tree.
[2]State: Give a short answer, no explanation needed.
In a nutshell
- A binary search tree (BST) enforces an ordering property: left subtree keys are smaller, and right subtree keys are larger than the root.
- Searching, inserting, and deleting in a balanced BST takes O(log n) logarithmic time.
- Inserting already-sorted data degrades a BST into a degenerate linear linked list with O(n) worst-case time complexity.
- Self-balancing trees (AVL or Red-Black trees) automatically re-balance using rotations to guarantee O(log n) operations.