> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/16.-adts-and-bsts/16.6-summary.md).

# 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”.