Comment on page
16.6 Summary
Abstract data types (ADTs) are defined in terms of operations, not implementation.Several useful ADTs:
- Disjoint Sets, Map, Set, List.
- Java provides Map, Set, List interfaces, along with several implementations.
We’ve seen two ways to implement a Set (or Map):
- ArraySet: Θ(N) operations in the worst case.
- BST: Θ(logN) operations if tree is balanced.
BST Implementations:
- Search and insert are straightforward (but insert is a little tricky).
- Deletion is more challenging. Typical approach is “Hibbard deletion”.
Last modified 8mo ago