%------------------------------------ % Binary trees - Tries %------------------------------------ @article {pi1, author="B. Pittel", title="Paths in Random Digital Tree: limiting distributions", journal="Adv. in Applied Prob.", year="1986", volume="18", number="", pages="139-155" } @article {bp, author="B. Pittel", title="Note on the height of random recursive trees and random m-ary search trees", journal="Random Structures and Algorithms", year="1994", volume="5", number="2", pages="" } @article {dev1, author="L. Devroye", title="On random cartesian trees", journal="Random Structures and Algorithms", year="1994", volume="5", number="2", pages="" } @article {rc, author="R. Carr and others", title="The maximum degree in a random tree and related problems", journal="Random Structures and Algorithms", year="1994", volume="5", number="1", pages="" } @article {kb, author="K. Balinska and others", title="Random recursive forests", journal="Random Structures and Algorithms", year="1994", volume="5", number="1", pages="" } @article {kp, author="P. Kirschenhofer and H. Prodinger", title="Multidimensional digital searching - Alternative data structures", journal="Random Structures and Algorithms", year="1994", volume="5", number="1", pages="" } @article {rk, author="R. Kemp", title="Balanced Ordered Trees", journal="Random Structures and algorithms", year="1994", volume="5", number="1", pages="" } @article {rk2, author="R. Kemp", title="The expected additive weight of trees", journal="Acta Informatica", year="1989", volume="26", number="", pages="711-740" } @article {mah1, author="H.M. Mahmoud", title="On the average internal path length of $m$-ary search trees", journal="Acta Informatica", year="1986", volume="23", number="", pages="111-117" } @article {dev2, author="L. Devroye", title="A note on the height of binary search trees", journal="J. of the ACM", year="1986", volume="33", number="3", pages="489-498" } @article {dev3, author="L. Devroye", title="A note on the average depth of tries", journal="Computing", year="1982", volume="28", number="", pages="367-371" } @article {dev4, author="L. Devroye", title="A probabilistic analysis of the height of tries and of the complexity of triesort", journal="Acta Informatica", year="1984", volume="21", number="", pages="229-237" } @article {fra, author="J. Fran\,con", title="Histoire de fichiers", journal="R.A.I.R.O Informatique Th\'eorique", year="1978", volume="12", number="1", pages="" } @article {vie, author="J. Fran\,con and G. Vi\'ennot ", title="Permutations selon leurs pics, creux, doubles mont\'ees, doubles descentes, nombres d'Euler et nombres de Genocchi", journal="Discrete Mathematics", year="1979", volume="28", number="", pages="" } @article {fla1, author="P. Flajolet and A. Odlyzko", title="The average height of binary search trees and other simple trees", journal="J. of Computer and System Sciences", year="1982", volume="25", number="", pages="171-213" } @article {dev5, author="L. Devroye", title="Branching processes in the analysis of the height of trees", journal="Acta Informatica", year="1987", volume="24", number="", pages="277-298" } @article {, author="A. Meir and J.W. Moon", title="On the altitude of nodes i random trees", journal="Can. J. Math.", year="1978", volume="XXX", number="5", pages="997-1015" } %------------------------------------ % Binary trees %------------------------------------ @article {, author="T. Harris", title="First passage and recurrence distributions", journal="Trans. Amer. Math. Society", year="1952", volume="73", number="", pages="471-486" } @article {, author="J. Riordan", title="Ballots and trees", journal="J. of Combinatorial Theory", year="1969", volume="6", number="", pages="408-411" } @article {, author="N.G. de Bruijn and D.E. Knuth and S.O.Rice", title="The average height of planted plane trees", journal="", year="", volume="", number="", pages="" } @article {, author="F. Harary and others", title="The number of plane trees", journal="Indag. Math.", year="1964", volume="", number="", pages="" } @article {, author="G.D. Knott", title="A numbering system for binary trees", journal="Communications of the A.C.M", year="1977", volume="20", number="2", pages="" } @article {pi2, author="B. Pittel", title="Asymptotical growth of a class of random trees", journal="The Annals of Probability", year="1985", volume="13", number="2", pages="414-427" } @article {em, author="E. McCreight", title="Priority search trees", journal="SIAM J. Computing", year="1985", volume="14", number="", pages="" } @article {ads, author="A. De Santis and G. Persiano", title="Tight upper and lower bounds on the path length of binary trees", journal="SIAM J. Computing", year="1994", volume="23", number="1", pages="" } @article {rst, author="R. Sundar and R. Tarjan", title="Unique binary-search-tree representations and equality testing of sets and sequences", journal="SIAM J. Computing", year="1994", volume="23", number="1", number="", pages="" } @article {rdp, author="R. De Prisco and A. De Santis", title="On binary search trees", journal="Information Processing Letters", year="1993", volume="45", number="", pages="249-253" } @inproceedings {tlw, author="T. Lai and D. Wood", title="Adaptative Heuristics for binary search trees and constant linkage cost", booktitle="SODA", address="", year="1990", pages="72-77" } @article {nr, author="J. Nievergelt and E. Reingold", title="Binary search trees of bounded balance", journal="SIAM J. Computing", year="1973", volume="2", number="1", pages="" } %------------------------------------ % Digitial trees %------------------------------------ @article {fls, author="P. Flajolet and R. Sedgewick", title="Digital search trees revisited", journal="SIAM J. Computing", year="1986", volume="15", number="3", pages="748-767" } @inproceedings {louc6, author="G. Louchard", title="Trie size in a dynamic list structure", booktitle="4th joint conference CAAP-FASE", address="Orsay-France", year="1993", pages="" } @article {louc7, author="G. Louchard", title="Exact and asymptotic distributions in digital and binary search trees", journal="Theorical Informatics and Applications", year="1987", volume="21", number="4", pages="479-496" }