The binary search tree
The ordering property, search, insertion, deletion in its three cases (leaf, one child, two children), the in-order traversal that returns the keys sorted, the height and the degeneration into a list.
- 24 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- The numbers
- Scenarios
- Understand
A few cards from the deck
Binary tree: what is it?
Show the answer
A structure of nodes where each has at most two children, told apart as left and right, and where a single node, the root, has no parent.
Its height, counted here in nodes along the longest path from the root to a leaf, bounds the cost of any descent. Some courses count it in edges, one fewer.
We insert 50, 30, 70, 20, 40, 60 then 35 into an empty binary search tree. Where does 35 go?
- Left child of 40
- Right child of 30
- Left child of 20
- Right child of 40
Show the answer
Left child of 40
35 < 50: go left. 35 > 30: go right, to 40. 35 < 40: go left, an empty spot. The right child of 30 is already 40.
In a binary search tree, we go … if the sought key is smaller than the node's, … if it is larger.
Show the answer
In a binary search tree, we go left if the sought key is smaller than the node's, right if it is larger.
Each comparison discards a whole subtree. A key equal to the node's means the search has succeeded.
Binary search tree: what is it?
Show the answer
A binary tree where each key is greater than all those of its left subtree and smaller than all those of its right subtree.
At each node, one comparison discards an entire subtree: a search costs the height of the tree. The rule applies to the whole subtree, not only to the direct children.
An index built with an ordinary binary search tree is filled from a file already sorted by number. Searches become as slow as walking a list. Which fix?
- Insert the keys from largest to smallest
- Use a balanced tree, which rebalances on each insertion
- Replace comparisons with an in-order traversal at each search
- Regularly delete the root to shorten the tree
Show the answer
Use a balanced tree, which rebalances on each insertion
Sorted keys degenerate the tree into a chain: height n. Inserting them in reverse gives a chain leaning the other way. A balanced tree (AVL, red-black) keeps a height of about log n whatever the arrival order.