Tree Review
Binary search trees ...
- data structures designed for O(logN) search
- consist of nodes containing item (incl. key) and two links
- can be viewed as recursive data structure (subtrees)
- have overall ordering (values(L) < root < values(R))
- insert new nodes as leaves, delete from anywhere
- have structure determined by insertion order (worst: O(N))
- operations: insert, delete, search, rotate, rebalance, ...
|