Bottom-Up Red-Black TreesSlide 2Bottom-Up InsertClassification Of 2 Red Nodes/PointersXYrLLbLRbDeleteDelete A Black LeafSlide 10Delete A Black Degree 1 NodeDelete A Black Degree 2 NodeRebalancing StrategySlide 14Slide 15Slide 16Rb0 (case 1)Rb0 (case 2)Rb1 (case 1)Rb1 (case 2)Rb2Rr(n)Rr(0)Rr(1) (case 1)Rr(1) (case 2)Rr(2)Bottom-Up Red-Black Trees•Top-down red-black trees require O(log n) rotations per insert/delete.•Color flips cheaper than rotations.•Priority search trees.Two keys per element.Search tree on one key, priority queue on other.Color flip doesn’t disturb priority queue property.Rotation disturbs priority queue property.O(log n) fix time per rotation => O(log2n) overall time.Bottom-Up Red-Black Trees•Bottom-up red-black tree properties.At most 1 rotation per insert/delete.O(1) amortized complexity to restructure following an insert/delete.Bottom-Up Insert•New pair is placed in a new node, which is inserted into the red-black tree.•New node color options.Black node => one root-to-external-node path has an extra black node (black pointer).Hard to remedy.Red node => one root-to-external-node path may have two consecutive red nodes (pointers).May be remedied by color flips and/or a rotation.Classification Of 2 Red Nodes/Pointers•XYzX => relationship between gp and pp.pp left child of gp => X = L.Y => relationship between pp and p.p right child of pp => Y = R.z = b (black) if d = null or a black node.z = r (red) if d is a red node.a bcdgppppXYr•Color flip.a bcdgppppa bcdgpppp•Move p, pp, and gp up two levels.•Continue rebalancing if necessary.LLb•Rotate.•Done!•Same as LL rotation of AVL tree.yxa bzc da bcdgppppxyzLRb•Rotate.•Done!•Same as LR rotation of AVL tree.•RRb and RLb are symmetric.yxa bzc db cadgppppyxzDelete•Delete as for unbalanced binary search tree.•If red node deleted, no rebalancing needed.•If black node deleted, a subtree becomes one black pointer (node) deficient.Delete A Black Leaf107815304020253545603• Delete 8.Delete A Black Leafy• y is root of deficient subtree.• py is parent of y.10715304020253545603pyDelete A Black Degree 1 Node107815304020253545603• Delete 45.y• y is root of deficient subtree.pyDelete A Black Degree 2 Node107815304020253545603• Not possible, degree 2 nodes are never deleted.Rebalancing Strategy•If y is a red node, make it black.107815304020253545603ypyRebalancing Strategy•Now, no subtree is deficient. Done!601078153040202535453ypyRebalancing Strategy•y is a black root (there is no py).•Entire tree is deficient. Done!601078153040202535453yRebalancing Strategy•y is black but not the root (there is a py).•Xcny is right child of py => X = R.Pointer to v is black => c = b.v has 1 red child => n = 1.a bypyvRb0 (case 1)•Color change.•Now, py is root of deficient subtree.•Continue!a bypyvya bpyvRb0 (case 2)•Color change.•Deficiency eliminated.•Done!a bypyvya bpyvRb1 (case 1)•LL rotation.•Deficiency eliminated.•Done!a bypyvab yvpyRb1 (case 2)•LR rotation.•Deficiency eliminated.•Done!aypyvb cwc ywpya bvRb2•LR rotation.•Deficiency eliminated.•Done!aypyvb cwc ywpya bvRr(n)•n = # of red children of v’s right child w.aypyvb cwRr(0)•LL rotation.•Done!a bypyvab yvpyRr(1) (case 1)•LR rotation.•Deficiency eliminated.•Done!aypyvbwcycwpyavbRr(1) (case 2)•Rotation.•Deficiency eliminated.•Done!aypyvbwc dxydxpyavb cwRr(2)•Rotation.•Deficiency eliminated.•Done!aypyvbwc dxd yxpyavb