advanced data structures and implementation draw the quad tree that corresponds to figure what factors influence how deep the (quadtree will bec describe an algorithm that performs an orthogonal range query in quad tree references top-down splay trees were described in the original splay tree paper [ similar strategybut without the crucial rotationwas described in [ the top-down red-black tree algorithm is from [ ] more accessible description can be found in [ an implementation of top-down red-black trees without sentinel nodes is given in [ ]this provides convincing demonstration of the usefulness of nullnode treaps [ are based on the cartesian tree described in [ related data structure is the priority search tree [ suffix trees were first described as position tree by weiner [ ]who provided linear-time algorithm for construction that was simplified by mccreight [ ]and then by ukkonen [ ]who provided the first online linear-time algorithm farach [ provided an alternate algorithm that is the basis for many of the linear-time suffix array construction algorithms numerous applications of suffix trees can be found in the text by gusfield [ suffix arrays were described by manber and myers [ the algorithm presented in the text is due to karkkainen and sanders [ ]another linear-time algorithm is due to ko and aluru [ the linear-time algorithm for constructing the lcp array from suffix array in exercise was given in [ survey of suffix array construction algorithms can be found in [ [ shows that any problem that is solvable via suffix trees is solvable in equivalent time with suffix arrays because the input sizes for practical applications are so largespace is importantand thus much recent work has centered on suffix array and lcp array construction in particularfor many algorithmsa cache-friendly slightly nonlinear algorithm can be preferable in practice to noncache friendly linear algorithm [ for truly huge input sizesin-memory construction is not always feasible [ is an example of an algorithm that can generate suffix arrays for gb of dna sequences in day on single machine with only gb of ramsee also [ for survey of external memory suffix array construction algorithms the - tree was first presented in [ other range-searching algorithms are described in [ the worst case for range searching in balanced - tree was obtained in [ ]and the average-case results cited in the text are from [ and [ the pairing heap and the alternatives suggested in the exercises were described in [ the study [ suggests that the splay tree is the priority queue of choice when the decreasekey operation is not required another study [ suggests that the pairing heap achieves the same asymptotic bounds as the fibonacci heapwith better performance in practice howevera related study [ using priority queues to implement minimum spanning tree algorithms suggests that the amortized cost of decreasekey is not ( fredman [ has settled the issue of optimality by proving that there are sequences for which the amortized cost of decreasekey operation is suboptimal (in factat least (log log )howeverhe has also shown that when used to implement prim' minimum spanning tree algorithmthe pairing heap is optimal if the graph is slightly dense (that isthe number of edges in the graph is ( ( +efor any epettie [ has shown an upper