Example of a ranked binary tree d 1(e 0(a)1 0(C)1 If all rank differences positive, rank> height
Example of a ranked binary tree If all rank differences positive, rank height f 1 1 e 1 d b 2 a 1 c 1 1 0 0 0 1
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 node
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 are 0 or 1, no 0- child is the parent of another All need one balance bit per node
Basic height bounds n s minimum n for rank k Rank-balanced trees. 1,n1=2,nk=2r n, t k-2 =212→k≤2gn Red-black trees: same AVL trees: ks logo n a 1.44lg n p=(1+5/2
Basic height bounds nk = minimum n for rank k Rank-balanced trees: n0 = 1, n1 = 2, nk = 2nk-2 + 1, nk = 2 k/2 k 2lg n Red-black trees: same AVL trees: k log n 1.44lg n = (1 + 5)/2
Rank-Balanced Trees Red-Black Trees height≤2gn height≤2lg <2 rotations per rebalancing <3 rotations per rebalancing o(1)amortized rebalancing o(1)amortized rebalancing time time
Rank-Balanced Trees height 2lg n 2 rotations per rebalancing O(1) amortized rebalancing time Red-Black Trees height 2lg n 3 rotations per rebalancing O(1) amortized rebalancing time
Rank-Balanced Trees Red-Black Trees height s min(2g n, logo my height≤2gn <2 rotations per rebalancing <3 rotations per rebalancing o(1)amortized rebalancing o(1)amortized rebalancing time time I win
Rank-Balanced Trees height min{2lg n, log m} 2 rotations per rebalancing O(1) amortized rebalancing time Red-Black Trees height 2lg n 3 rotations per rebalancing O(1) amortized rebalancing time I win