Access Restriction

Author Foster, Caxton C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Information storage and retrieval ♦ Avl trees ♦ Balanced trees
Abstract A generalization of AVL trees is proposed in which imbalances up to Δ are permitted, where Δ is a small integer. An experiment is performed to compare these trees with standard AVL trees and with balanced trees on the basis of mean retrieval time, of amount of restructuring expected, and on the worst case of retrieval time. It is shown that, by permitting imbalances of up to five units, the retrieval time is increased a small amount while the amount of restructuring required is decreased by a factor of ten.A few theoretical results are derived, including the correction of an earlier paper, and are duly compared with the experimental data. Reasonably good correspondence is found.0
Description Affiliation: Univ. of Massachusetts, Amherst, MA (Foster, Caxton C.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 16
Issue Number 8
Page Count 5
Starting Page 513
Ending Page 517

Open content in new tab

   Open content in new tab
Source: ACM Digital Library