Rank-Balanced trees AVL trees: every node is a 1, 1 -or 1, 2-node Rank-balanced trees: every node is a 1, 1,1, 2-, or 2, 2- node(rank differences are 1 or 2) Red-black trees: all rank differences areo or 1, no 0 child is the parent of another All need one balance bit per nodeRank-Balanced Trees AVL trees: every node is a 1,1- or 1,2-node Rank-balanced trees: every node is a 1,1-, 1,2-, or 2,2- node (rank differences are 1 or 2) Red-black trees: all rank differences are 0 or 1, no 0- child is the parent of another All need one balance bit per node