trees preliminaries implementation of trees tree traversals with an application binary trees implementation an exampleexpression trees the search tree adt--binary search trees contains findmin and findmax insert remove destructor and copy constructor average-case analysis avl trees single rotation double rotation splay trees simple idea (that does not work splaying tree traversals (revisited -trees sets and maps in the standard library sets maps implementation of set and map an example that uses several maps summary exercises references hashing general idea hash function separate chaining hash tables without linked lists linear probing quadratic probing double hashing rehashing hash tables in the standard library ix