An AVL algorithm for secondary memory
William E. Wright · 2005
Binary search trees are shown to be practical file structures for magnetic bubble memory. A practical algorithm for maintaining AVL trees in secondary memory is shown. The algorithm is shown to have an efficient design which minimizes the number of accesses to secondary memory. The number of extra accesses is shown to be primarily a function of the traceback path length. The AVL algorithm is shown to be faster than the basic nonbalancing algorithm for almost all practical applications. The savings by the AVL algorithm is shown to increase logarithmically with the tree size, and linearly with the ratio of retrievals to insertions.