Binary Search Tree
Smaller values sit left, larger sit right, so a search walks one path down.
Binary Search Tree: Search for 45
45 is smaller than 50: go left.
Cost
- Search
- O(h)
- Insert
- O(h)
- Delete
- O(h)
- Space
- O(n)
h is the height. O(log n) when balanced O(n) when degenerate.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Binary Search Tree covers these too, in the same run.