a tree question

[John Hascall]

In article <421 at ohs.UUCP> bhil at ohs.UUCP (Brian T. Hill) writes:
}Does anyone have a good alternative to the AVL method of balancing
}binary trees?  It seems to me that the AVL method is wasteful of 
}both time and space.
 
    How so?

    Insertion (balancing) is O(log n) and requires only 2 extra bits
    per node (although almost everyone uses at least a byte).

    And half the time (roughly) no rebalancing is needed, with single
    and double rotation needed about one time in four each.

    If you insist on another method, how about B-trees?

John Hascall
ISU Comp Center