A balanced tree storage and retrieval algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A balanced tree storage and retrieval algorithm

Full text

Pdf (763 KB)

Source

Annual ACM Conference on Research and Development in Information Retrieval archive
Proceedings of the 1971 international ACM SIGIR conference on Information storage and retrieval table of contents

College Park, Maryland

SESSION: File organization and evaluation table of contents

Pages: 175 - 196

Year of Publication: 1971

Author

Gary D. Knott

National Institutes of Health, Bethesda, Maryland

Sponsors

SIGIR: ACM Special Interest Group on Information Retrieval
: National Aeronautics and Space Administration
University of Maryland : University of Maryland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 63, Citation Count: 6

Additional Information:

abstract 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/511285.511305 What is a DOI?

ABSTRACT

A storage and retrieval scheme which places items to be stored at the nodes of a binary tree is discussed. The tree is always balanced in a certain sense thus insuring that no excessively long search paths can exist. In addition to presenting the storage and retrieval algorithms, the deletion problem is also solved. The programming approaches involved yield a non-trivial case study of list-processing techniques. Finally, a cost analysis is given.

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.

	1	ADEL'SON-VEL'SKIJ, G. M.; LANDIS, Y. M. An algorithm for the organization of information. Doklady Akademii Nauk USSR, vol. 16, no. 2, p. 263:266, Moscow, USSR; also available in translation as U.S. Dept. of Commerce OTS, JPRS 17,137; and as NASA Document N63-11777.
	2	BOOTH, A. D.; COLIN, H. J. T. On the efficiency of a new method of dictionary construction. Information and Control, vol. 3, p. 334:341, December 1960.
	3	FERGUSON, DAVID E. Balanced tree searching. internal document, Programmatics Inc., January 1968.
	4	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]
	5	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]
	6	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]
	7	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	8	KNUTH, DONALD E. Optimum binary search trees. Stanford Computer Science Dept. Technical Report CS 149, Stanford University, January 1970.
	9	WINDLEY, P. R. Trees, forests, and rearranging. Computer Journal, vol. 3, no. 2, p. 84:88, July 1960.

CITED BY 6

	Caxton C. Foster, A generalization of AVL trees, Communications of the ACM, v.16 n.8, p.513-517, Aug. 1973
	P. L. Karlton , S. H. Fuller , R. E. Scroggs , E. B. Kaehler, Performance of height-balanced trees, Communications of the ACM, v.19 n.1, p.23-28, Jan. 1976
	J. Nievergelt, Binary search trees and file organization, Proceedings of 1972 ACM-SIGFIDET workshop on Data description, access and control, p.165-187, January 1972
	J. Nievergelt, Binary Search Trees and File Organization, ACM Computing Surveys (CSUR), v.6 n.3, p.195-207, Sept. 1974
	W. A. Martin , D. N. Ness, Optimizing binary trees grown with a sorting algorithm, Communications of the ACM, v.15 n.2, p.88-93, Feb. 1972
	J. C. Huang, A note on information organization and storage, Communications of the ACM, v.16 n.7, p.406-410, July 1973

INDEX TERMS

Keywords:
balanced trees, data structures, searching, storage and retrieval

Collaborative Colleagues:

Gary D. Knott: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player