BST
The binary search tree. A classic when it comes to learning about trees.
The thing about them
They are not some new ds that we haven't seen, they are specifically an ordering to the data within the data structure.
Lets program them, but first whiteboard the algorithm
- Find
- Running time?
- Insertion
- what does this do to running time?
- Deletion
- Trickier than you thought? O Y E S
Lets write binary search!
- Just the search part (its super easy)
Lets compare
Binary search an array vs a tree?
- What feels easier to implement?