bound of ( log log for decreasekey howevercomplete analysis of the pairing heap is still open the solutions to most of the exercises can be found in the primary references exercise represents "lazybalancing strategy that has become somewhat popular [ ][ ][ ]and [ describe specific strategies[ shows how to implement all of these strategies in one framework tree that satisfies the property in exercise is weight-balanced these trees can also be maintained by rotations [ part (dis from [ solution to exercises to can be found in [ quad trees are described in [ abouelhodas kurtzand ohlebush"replacing suffix trees with suffix arrays,journal of discrete algorithms ( ) - andersson"general balanced trees,journal of algorithms ( ) - aragon and seidel"randomized search trees,proceedings of the thirtieth annual symposium on foundations of computer science ( ) - baer and schwab" comparison of tree-balancing algorithms,communications of the acm ( ) - barskyu stegeand thomo" survey of practical algorithms for suffix tree construction in external memory,softwarepractice and experience ( - barskyu stegea thomoand upton"suffix trees for very large genomic sequences,proceedings of the eighteenth acm conference on information and knowledge management ( ) - bentley"multidimensional binary search trees used for associative searching,communications of the acm ( ) - bentley and friedman"data structures for range searching,computing surveys ( ) - chang and iyengar"efficient algorithms to globally balance binary search tree,communications of the acm ( ) - chanzy"range search and nearest neighbor search,master' thesismcgill university day"balancing binary tree,computer journal ( ) - ding and weiss"the - heapan efficient multi-dimensional priority queue,proceedings of the third workshop on algorithms and data structures ( ) - farach"optimal suffix tree construction with large alphabets,proceedings of the thirty-eighth annual ieee symposium on foundations of computer science ( ) - flajolet and puech"partial match retrieval of multidimensional data,journal of the acm ( ) - flamigpractical data structures in ++john wileynew york fredman"information theoretic implications for pairing heaps,proceedings of the thirtieth annual acm symposium on the theory of computing ( ) - fredmanr sedgewickd sleatorand tarjan"the pairing heapa new form of self-adjusting heap,algorithmica ( ) - guibas and sedgewick" dichromatic framework for balanced trees,proceedings of the nineteenth annual symposium on foundations of computer science ( ) - gusfieldalgorithms on stringstrees and sequencescomputer science and computational biologycambridge university presscambridgeu