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 updated