Binary search trees
Insert seven numbers into a binary search tree, smaller ones to the left and bigger ones to the right. Search it with very few comparisons, print it in order, and see how numbers that arrive already sorted turn the tree into a long chain.
Core concept
In a binary search tree every number on a node's left is smaller and every number on its right is bigger, so a search throws away half the tree at each step, but only while the tree stays bushy and short
Topic: Data structures
A tree in programming is drawn upside down: the first node, the root, is at the top, and each node can have a left child and a right child below it. In a binary: Counting with only two digits, 0 and 1. Computers store everything this way. All key words search tree there is one rule: everything to the left of a node is smaller than it, and everything to the right is bigger. To insert a number you start at the root and keep going left or right until you find an empty place. To search, you do the same: at each node you compare and go one way, so every comparison throws away the whole other side. A tree with seven numbers that is nicely bushy has only three levels, so any search takes at most three comparisons. Walking the tree in order (left side, the node, right side) prints the numbers from smallest to largest. But the shape depends on the order the numbers arrive in: numbers that arrive already sorted all go to the right, and the tree becomes a long chain, no faster than a list.
What you will learn
- Insert numbers into a binary search tree, going left for smaller and right for bigger.
- Search a tree and count the comparisons.
- Explain why an in-order walk prints the numbers in sorted order.
- Explain how the insertion order changes the tree's height and the search's speed.
Before you start
- Know binary search on a sorted list, and comparing numbers with < and >.
Materials
- A notebook to draw the trees
Equipment
- None
Procedure
- Run the program with the balanced order and search for 60.
- Step through to the end and read the in-order output.
- Choose the sorted order and search for 70; compare the height and the comparisons.
- Answer the practice challenges.