Cory's Wiki

Abstract generalization of AVL trees.

• * Each node has a “rank”
• Rank is an integer,not necessarily subtree height
• * “Rank difference” of a node is the rank of the parent minus the rank of a child
• * There are constraints on

AVL trees are rank-balanced trees in which rank equals the height of a subtree rooted at that node, and rank differences are either 1 or 2, and a maximum of 1 child can have rank difference 2. Red Black Trees are rank-balanced trees in which all rank differences are 0 or 1, and no node and its parent can both have rank-difference zero. Can also define a “weak AVL” tree in which both children can have rank difference of 2. This weak avl tree is easier to analyse.