rotations, AVL or RB insertions or deletions require inspections and/or updates to AVL balance factors (or RB colors). RB insertions and deletions and AVL insertions require from zero to three tail-recursive rotations and run in amortized time, thus equally constant on average. AVL deletions requiring rotations in the worst case are also on average. RB trees require storing one bit of information (the color) in each node, while AVL trees mostly use two bits for the balance factor, although, when stored at the children, one bit with meaning «lower than sibling» suffices. The bigger difference between the two data structures is their height limit. For a tree of size an AVL tree's height is at most where the golden ratio, and . a RB tree's height is at most . AVL trees are more rigidly balanced than RB trees with an asymptotic relation AVL/RB ≈0.720 of the maximal heights. For insertions and deletions, Ben Pfaff shows in 79 measurements a relation of AVL/RB between 0.677 and 1.077 with median ≈0.947 and geometric mean ≈0.910. See also WAVL tree Splay tree Scapegoat tree B-tree T-tree List of data structures References Further reading Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Pages 458–475 of section 6.2.3: Balanced Trees. . External links 1962 in computing Articles with example pseudocode Binary trees Soviet inventions Search trees