Deals with dynamic data structures, which
can grow and contract in size
support efficient searches
The data structures are
priority queues, which
support insertions and deletions
hash tables, which
support insertions and deletions
have excellent average search time
do not support ordered traversals
binary search trees, which
support searching, inserting, and deleting
have good average times for these operations
support ordered traversing
balanced binary search trees, which
support all the operations of binary search trees
also support fast access to information in an arbitrary position in a sorted
ordering of the information stored
have good worst-case time for all the operations
Worst-case and average times are given for the operations on each data structure