Binary search trees
Not met yet
A binary search tree keeps everything down a card's left side smaller than it and everything down its right side bigger. Finding a number walks down from the root, going left or right at each card, so it looks at one card per level. Adding is the same walk; the new card goes in the empty place where the walk ends. Filed in a jumbled order the tree stays bushy, about log n levels; filed in order it becomes a stick n levels high, and searching it is no better than a list.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks a binary search tree stays bushy whatever order the cards are added in, so a search always takes about log n looks.
- Thinks searching a binary search tree has to look down both sides of a card, rather than only the side the number belongs on.
- Thinks a new card goes in at the top of a binary search tree, pushing the others down, rather than at the empty place its walk ends.