Binary Search Trees and File Organization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Binary Search Trees and File Organization

Full text

Pdf (850 KB)

Source

ACM Computing Surveys (CSUR) archive
Volume 6 , Issue 3 (September 1974) table of contents

Pages: 195 - 207

Year of Publication: 1974

ISSN:0360-0300

Author

J. Nievergelt

Department of Computer Science, University of Illinois, Urbana, Illinois

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 86, Citation Count: 22

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356631.356634 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Ad62	ADELSON-VELsKII, G. M.; AND LANDIS, YE. M. "An algorithm for the organization of information." Dokl. Akad. Naulc SSSR 146 (1962), 263-266 (Russian), English translation in Soviet Math. Dokl. 3 (1962), 1259-1262.
	Ba72a	BAYER, R., AND MCCREIGHT. "Organization and maintenance of large ordered indexes." Acla Informatica 1, 3 (1972), 173-189.
	Ba72b	BAYER, R. "Symmetric binary B-trees: data structure and maintenance algorithms." Acta Informalica 1, 4 (1972), 290-306.
	Br71	BRUNO, J.; AND COFFMAN, E. G. "Nearly optimal binary search trees." Proc. 1FIP Congress 71. North-Holland Publishing Co., Amsterdam 1972, 99-103.
	Co70	COFFMAN, E. G.; AND BRUNO, J. "On file structuring for non-uniform access frequencies." BIT 10 (1970), 443-456.
	Fo65	C. C. Foster, Information retrieval: information storage and retrieval using AVL trees, Proceedings of the 1965 20th national conference, p.192-205, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806043]
	Fo73	Caxton C. Foster, A generalization of AVL trees, Communications of the ACM, v.16 n.8, p.513-517, Aug. 1973 [doi>10.1145/355609.362340]
	Fr60	Edward Fredkin, Trie memory, Communications of the ACM, v.3 n.9, p.490-499, September 1960 [doi>10.1145/367390.367400]
	Gh69	S. P. Ghosh , M. E. Senko, File Organization: On the Selection of Random Access Index Points for Sequential Files, Journal of the ACM (JACM), v.16 n.4, p.569-579, Oct. 1969 [doi>10.1145/321541.321546]
	Hf52	HUFFMAN, D. A. "A method for the construction of minimum redundancy codes." Proc. IRE, Vol. 40, (1952), 1098-1101.
	Hi62	Thomas N. Hibbard, Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting, Journal of the ACM (JACM), v.9 n.1, p.13-28, Jan. 1962 [doi>10.1145/321105.321108]
	Ho61	C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
	Hu71	HU, T. C. ; AND TUCKER, A. C. "Optimal computer search trees and variable-length alphabetic codes." SIAM J. Appl. Math. 21, 4 (Dec. 1971), 514-532.
	Kn68	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	Kn71	KNUTH, D. E. "Optimum binary search trees." Acta Informatica 1 (1971), 14-25.
	Kn73	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	Kt71	Gary D. Knott, A balanced tree storage and retrieval algorithm, Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval, April 01-02, 1971, College Park, Maryland [doi>10.1145/511285.511305]
	Mo68	Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
	Mu70	MUNTZ, R.; AND UZGALIS, R. "Dynamic storage allocation for binary search trees in a two-level memory." Proc. 4th Annual Princeton Conference, Princeton, N.J., 1970.
	Ni71	NIEVERGELT, J.; AND WONG, C. K. "On binary search trees." Proc. IFIP Congress 71, North Holland Publ. Co., Amsterdam 1972, 91-98.
	Ni73a	C. K. Wong , J. Nievergelt, Upper Bounds for the Total Path Length of Binary Trees, Journal of the ACM (JACM), v.20 n.1, p.1-6, Jan. 1973 [doi>10.1145/321738.321739]
	Ni73b	NIEVERGELT, J.; AND REINGOLD, E. M. "Binary search trees of bounded balance." SIAM J. Computing 2, 1 (March 1973), 33-43.
	Se74	Dennis G. Severance, Identifier Search Mechanisms: A Survey and Generalized Model, ACM Computing Surveys (CSUR), v.6 n.3, p.175-194, Sept. 1974 [doi>10.1145/356631.356633]
	Su63	Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]
	Wa71	WALKER, W. A.; AND GOTLIEB, C. C. "A top-down algorithm for constructing nearly-optimal lexieographic trees." R. C. Read (ed.), Graph Theory and Computing, Academic Press, New York, 1972, 303- 323.
	We71	WEINER, P. "On the heuristic design of binary search trees." Proc. 5th Annual Princeton Conference, Princeton, N.J., March 1971.
	Wo72	WONG, C. K.; AND CHANG, S. K. "The generation and balancing of binary search trees." (to appear).

CITED BY 22

	Ben Shneiderman, Jump searching: a fast sequential search technique, Communications of the ACM, v.21 n.10, p.831-834, Oct. 1978
	D. S. Hirschberg, An insertion technique for one-sided height-balanced trees, Communications of the ACM, v.19 n.8, p.471-473, Aug. 1976
	J.-L. Baer , B. Schwab, A comparison of tree-balancing algorithms, Communications of the ACM, v.20 n.5, p.322-330, May 1977
	K. Hwang , S. B. Yao, Optimal Batched Searching of Tree Structured Files in Multiprocessor Computer Systems, Journal of the ACM (JACM), v.24 n.3, p.441-454, July 1977
	James Michael Cannady, Balancing methods for binary search trees, Proceedings of the 16th annual Southeast regional conference, p.181-186, April 13-15, 1978, Atlanta, Georgia
	Fabrizio Luccio , Linda Pagli, Power trees, Communications of the ACM, v.21 n.11, p.941-947, Nov. 1978
	Michael Z. Hanani, An optimal evaluation of Boolean expressions in an online query system, Communications of the ACM, v.20 n.5, p.344-347, May 1977
	William E. Wright, Dynamic Binary Search Trees, Proceedings of the 1978 annual conference, p.370-374, December 04-06, 1978, Washington, D.C., United States
	W. D. Maurer , T. G. Lewis, Hash Table Methods, ACM Computing Surveys (CSUR), v.7 n.1, p.5-19, March 1975
	Gaston H. Gonnet , Frank W. Tompa, A constructive approach to the design of algorithms and their data structures, Communications of the ACM, v.26 n.11, p.912-920, Nov. 1983
	William E. Wright, An empirical evaluation of algorithms for dynamically maintaining binary search trees, Proceedings of the ACM 1980 annual conference, p.505-515, January 1980
	Gopal K. Gupta, Self-assessment procedure XIII: a self-assessment procedure dealing with binary search trees and B-trees, Communications of the ACM, v.27 n.5, p.435-443, May 1984
	A. Thayse , M. Davio , J. -P. Deschamps, Optimization of multivalued decision algorithms, Proceedings of the eighth international symposium on Multiple-valued logic, p.171-178, January 1978, Rosemont, Illinois, United States
	Toby J. Teorey , James P. Fry, The Logical Record Access Approach to Database Design, ACM Computing Surveys (CSUR), v.12 n.2, p.179-211, June 1980
	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979
	Douglas Comer , Ravi Sethi, The Complexity of Trie Index Construction, Journal of the ACM (JACM), v.24 n.3, p.428-440, July 1977
	William E. Wright, Organizing and accessing files for magnetic bubble memory and charge coupled devices, Proceedings of the 1979 annual conference, p.221-227, January 1979
	Porter Eugene Smith , James H. Graham, A simple balanced search tree, Proceedings of the 1993 ACM conference on Computer science, p.461-465, February 16-18, 1993, Indianapolis, Indiana, United States
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Leo R. Gotlieb, Computing joins of relations, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California
	James R. Driscoll , Y. Edmund Lien, A selective traversal algorithm for binary search trees, Communications of the ACM, v.21 n.6, p.445-447, June 1978
	Glenn K. Manacher, On the feasibility of implementing a large relational data base with optimal performance on a minicomputer, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts

INDEX TERMS

Primary Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

Collaborative Colleagues:

J. Nievergelt: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player