COMP3600/6466 – Algorithms
Abstract Data Structures Cont.:
Red-Black Tree Cont. [CLRS ch. 13.4]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/ Comp_3600_6466@anu.edu.au
Assessments
• Final Project – Milestone 1
• Marking release: We’re aiming for 25 Sep
• A2
Topics
üBinary Search Tree üHeaps
üAVL Tree
• Red-black Tree
üWhat is it?
üGuarantee on height of the tree üInsertion
• Deletion
• Usage
Deletion: Intuition
• Delete the node following the BST deletion method but with additional step to adjust the color, then repair the red-black requirement
• Suppose the deleted node is 𝑧 • If 𝑧 only has NIL children
• If 𝑧 is red, remove 𝑧, set the edge that lead to 𝑧 to now lead to a NIL node, and done
• If 𝑧 is black, remove as above but repair is needed
Deletion: Intuition
• If 𝑧 has 1 non-NIL child
• In this case, 𝑧 must be black and the non-NIL child must be red to satisfy black height and no consecutive red requirements. Why?
• Delete as BST, replace 𝑧 with its only non-NIL child and color it the same as 𝑧’s color.
• No repair is needed
Deletion: Intuition
• If 𝑧 has 2 non-NIL children
• Let 𝑦 be the node that replaces 𝑧 (i.e., 𝑧‘s successor). • If y is red, recolor 𝑦 to follow the color of 𝑧 and done.
Note that in this case, 𝑦 can only have 2 NIL children. Why?
• If y has 1 non-NIL child (i.e., it is black and its non-NIL child is red), then swap data of 𝑧 with y, apply the rule in the
previous slide to remove 𝑧 (which is now in the original 𝑦’s position) and done.
• Otherwise, delete as BST. repair is needed.
Deletion: Repair Intuition
• Repair is only needed whenever 𝑧 is a black node with only NIL children or its successor, 𝑦, is black.
• Repair starts from the node 𝑥, where 𝑥 is
• A NIL node that replaces 𝑧’s position if 𝑧 is black with
only NIL children
• The node that replaces 𝑦’s position
Deletion: Repair Intuition
• To ensure the black height is maintained, we add black to 𝑥, making 𝑥 to either be black-black (𝑥 original color is black) or red-black (𝑥 original color is red), which is no longer the color requirement in red-black tree.
• If 𝑥 is red-black, recolor to be black
• If 𝑥 is black-black, find nearest red and “distribute” one of 𝑥 black to change that node color from red to black. Next slides are about this
Deletion: Repair for 𝑥 black-black
Deletion: Repair Intuition
• There’s 2 categories and 4 cases per category.
• Note, here 𝑥 is black-black and we denote 𝑥’s sibling as 𝑤 • Category1: 𝑥 is the left child of its parents
• Case1: 𝑤 is red
Swap the color between 𝑤 and 𝑥’s parent, then rotate left on 𝑥’s parent. Then, continue to case 2/3/4, setting 𝑤 = 𝑥. 𝑝. 𝑟𝑖𝑔h𝑡
Deletion: Repair Intuition
• Category1: 𝑥 is the left child of its parents
• Case2: 𝑤 and both of its children are black
Take one black from 𝑥 and 𝑤 (setting 𝑤 to be red), move this black to 𝑥. 𝑝. Since 𝑥. 𝑝 can initially be red or black, it will become red-black or black-black. If we enter this case from case-1, 𝑥. 𝑝 will be red-black, and we can recolor it with red and done. Otherwise, continue by setting 𝑥 = 𝑥. 𝑝
Deletion: Repair Intuition
• Category1: 𝑥 is the left child of its parents
• Case3: 𝑤 and its right child are black, but its left child is red
Swap color between 𝑤 and its left child, then rotate right around 𝑤, and continue to case 4
Deletion: Repair Intuition
• Category1: 𝑥 is the left child of its parents • Case4: 𝑤 is black, 𝑤’s right child is red
Set the color of 𝑤 to be the color of 𝑥.𝑝 and set the color of 𝑥. 𝑝 and 𝑤. 𝑟𝑖𝑔h𝑡 to be black. Then, rotate left around 𝑥. 𝑝. The color change of 𝑥. 𝑝 and 𝑤. 𝑟𝑖𝑔h𝑡 allows us to remove one of the black of 𝑥 without violating red-black tree requirements.
Time Complexity
• RB-Delete (without the repair): 𝑂(log 𝑛)
• RB-Delete-Fixup (aka repair): 𝑂(log 𝑛)
• At most 3 rotation
• Case 1, 3, 4: Constant number of color change + at most 3 rotation
• Case 2: The pointer can move at most 𝑂(log 𝑛) time
Topics
üBinary Search Tree üHeaps
üAVL Tree
• Red-black Tree
üWhat is it?
üGuarantee on height of the tree üInsertion
üDeletion
• Usage
AVL Tree vs Red-black Tree
• In deletion, red-black tree provides guarantee that there’s at most rotation operation (which usually is the costly operation in tree rebalancing)
• Red-black tree provides more flexibility on “balance” tree. But, AVL Tree provides better balance than Red- black tree, which leads to better look-up performance
• In general, if you know you’ll do lots of deletion, Red- black is preferred, while if your data is not changing much and you do much more lookup, AVL would be preferable
Augmenting Data Structures
• In many cases, we can’t use the data structures as is. But, don’t just throw away existing data structures either.
• We can augment existing known abstract data structures to work. Usually, 4 steps: • Set underlying data structures
• What additional information is needed?
• Maintaining structures and information • Develop new operations
Topics
üBinary Search Tree üHeaps
üAVL Tree üRed-black Tree
Next: Hashing