Information retrieval: information storage and retrieval using AVL trees

ABSTRACT

ALTHOUGH TREES have long been used for the storage and retrieval of information 1,2, unfortunately there is a tradeoff between storage (construction) time and retrieval time. To keep retrieval time at a minimum, the tree must be balanced; but posting a new item under this constraint can require a complete reorganization of the tree. Conversely, if the tree is allowed to grow without restriction on its structure, the average number of probes (that is, references to main memory) required for retrieval can approach N/2, depending on the order of arrival of the items. Recently, Adel'son-Vel'skiy and Landis presented a tree structure that provides a good compromise between the two extremes of complete balancing and unrestricted growth 3. Their structures - called AVL trees here - are characterized by the constraint that the two subtrees dependent from any node will have maximum path lengths that will differ at most by one. This paper reviews the results of Adel'son-Vel'skiy and Landis, presenting somewhat expanded versions of their proofs. It then goes on to derive the mean number of probes for posting and retrieval in these structures. Finally, it shows that the number of probes required to post items on or retrieve items from AVL trees are few enough to permit a suitably organized computer, using only conventional components, to keep up with the delivery of requests from a buffered hypertape.

REFERENCES

• 1: Landauer, W. I., "The Tree as a Stratagem for Automatic Information Handling," Moore School Report 63-15, ASTIA No. AD293888, University of Pennsylvania; 1962.
• 2: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 3: Adel'son-Vel'skiy, G. M., and Landis, Ye. M., "An Algorithm for the Organization of Information," Deklady Akademii Nauk USSR, Moscow, p. 263-266; Vol. 16, No. 2, 1962; also available in translation as U.S. Department of Commerce OTS, JPRS 17, 137, Washington, D. C. and as NASA Document N63-11777.
• 4: Foster, C. C., "A Study of AVL Trees," GER-12158, Goodyear Aerospace Corporation, Akron, Ohio; 1965.
• 5: Windley, P. F., "Trees, Forests, and Rearranging," Comp. J., p. 84-88; Vol. 3, No. 2, 1960.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Theory