notes some of the data structures discussed in this are extensively covered by knuth in his sorting and searching book [ ]and by mehlhorn in [ avl trees are due to adel'son-vel'skii and landis [ ]who invented this class of balanced search trees in binary search treesavl treesand hashing are described in knuth' sorting and searching [ book average-height analyses for binary search trees can be found in the books by ahohopcroftand ullman [ and cormenleisersonrivest and stein [ the handbook by gonnet and baeza-yates [ contains number of theoretical and experimental comparisons among map implementations ahohopcroftand ullman [ discuss ( treeswhich are similar to ( trees red-black trees were defined by bayer [ variations and interesting properties of red-black trees are presented in paper by guibas and sedgewick [ the reader interested in learning more about different balanced tree data structures is referred to the books by mehlhorn [ and tarjan [ ]and the book by mehlhorn and tsakalidis [ knuth [ is excellent additional reading that includes early approaches to balancing trees splay trees were invented by sleator and tarjan [ (see also [ ]