Michael Data

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.