Transcript Introduction (CB chap. 1 & 2)

Implementing Red Black Trees
Ellen Walker
CPSC 201 Data Structures
Hiram College
Implementing Red-Black Trees
• Several implementations are possible (and many are
on the Internet)
– Some include parent links in RedBlackNodes - can be
iterative
– Textbook’s is recursive, recognizing need for rotations on the
way back up the tree (after recursive call)
• These slides follow your textbook, but…
– Code here is incomplete
– In places, code has been simplified for presentation
•
For complete, correct code, see your textbook and/or
the book code
About These Slides
• Follow textbook’s presentation but…
• … code is incomplete
• … code is slightly simplified for ease of
presentation
– Example: casts are removed
• Use these notes as a guide for understanding
when reading the actual textbook code
Classes (Koffman & Wolfgang)
SearchTree
(abstract class)
BinarySearchTree
(Adds RotateLeft and
RotateRight)
BSTWithRotate
RBTree
Single Rotation (RotateRight)
root
temp
3
4
8
4
3
8
6
6
temp = root.left;
root.left = temp.right;
temp.right = root;
return temp;
temp
root
Double Rotation
root
8
6
4
4
6
6
5
8
5
8
4
5
root.left = rotateLeft(root.left); return RotateRight(root);
RedBlackNode<E>
• E data
– Data contained in this node
• RedBlackNode left, RedBlackNode right
– References to children
• boolean isRed
– Color of this node (true means Red)
– Set to true in constructor, because all nodes
(except root) are red when added
Recall: BST Recursive Add
If (item.equals(localRoot.data))
addreturn = null; //duplicates not added
Return localRoot;
If (item.compareTo(localRoot.data)<0)
Add to the left
return localRoot;
Else
Add to the right
return localRoot;
Recall: BST Recursive Add (left side)
If localRoot.left == null
localRoot.left = new Node(item);
return localRoot;
Else
localRoot.left = add(localRoot.left,item);
return localRoot;
Add Recursion
• Base case at leaf of tree
– Create and link a new node
• Recursive case
– Recursively add on the correct side
– Link result of recursion back into the tree, or the
changes will be lost!
– localRoot.left = add(localRoot.left, item); //not just
add(localRoot.left, item);
Top Down Insertion Algorithm
• Search the binary tree in the usual way for
the insertion algorithm
• If you pass a 4-node (black node with two red
children) on the way down, split it
• Insert the node as a red child, and use the
split algorithm to adjust via rotation if the
parent is red also.
• Force the root to be black after every
insertion.
RBT Adding to the Left
If localRoot.left == null
localRoot.left = new Node(item);
return localRoot;
Else
//Split me if I’m a 4-node
moveBlackDown(localRoot);
localRoot.left = add(localRoot.left, item);
//Deal with consecutive red child & grandchild
//case 1: red left child with red left grandchild
//case 2: red left child with red right grandchild
RotateRight to Fix Left-Left Reds
localRoot
4
3
4
8
3
8
6
6
localRoot.left.isRed = false;
localRoot.isRed = true;
Return rotateRight(localRoot);
Double Rotation to Fix Left-Right Reds
8
8
localRoot
6
4
4
6
6
5
5
8
4
5
localRoot.left = rotateLeft(localRoot.left);
localRoot.left.isRed = false; localRoot.isRed = true;
return RotateRight(localRoot);
Putting the code all together
• Insert appropriate tests to recognize the
various red-red cases
• Repeat all the “left code” for the right side
– Swap “left” vs. “right” everywhere
• Write the “starter add method”
– Deals with an empty tree
– Makes the root black at the end
Starter Method
If (root == null) {
root = new RedBlackNode<E> (item);
root.isRed = false; //root is always black
addReturn = true; //item was added
}
Else {
root = add(root, item); //sets addReturn
root.isRed = false; //root is always black
}
return addReturn;
Insert 1, 2, 3
1
2
1
2
1
2
3
3
Left single rotation
Insert red leaf
(2 consecutive red nodes!)
Continued: Insert 4, 5
2
1
2
3
1
4
4-node (2 red children)
split on the way down
Root remains black
2
3
1
4
3
4
5
5
Single rotation to avoid
consecutive red nodes
Continued, Insert 9, 6
2
2
1
4
3
2
1
4
3
5
1
5
3
9
4-node (3,4,5) split on the way down,
4 is now red (passed up)
4
9
6
6
5
Double
rotation
9
Deletion Algorithm
• Find the node to be deleted (NTBD)
– On the way down, if you pass a 2-node upgrade it
by borrowing from its neighbor and/or parent
• If the node is not a leaf node,
– Find its immediate successor, upgrading all 2nodes
– Swap value of leaf node with value of NTBD
• Remove the current leaf node, which is now
NTBD (because of swap, if it happened)
Red-black “neighbor” of a node
• Let X be a 2-node to be deleted
• If X is its parent’s left child, X’s right neighbor
can be found by:
– Let S = parent’s right child. If S is black, it is the
neighbor
– Otherwise, S’s left child is the neighbor.
• If X is parent’s left child, then X’s left neighbor
is grandparent’s left child.
Neighbor examples
2
Right neighbor of 1 is 3
1
4
3
Right neighbor of 3 is 5
Left neighbor of 5 is 3
5
Left neighbor of 3 is 1
9
Upgrade a 2-node
• Find the 2-node’s neighbor (right if any, otherwise
left)
• If neighbor is also a 2-node (2 black children)
– Create a 4-node from neighbors and their parent.
– If neighbors are actually siblings, this is a color swap.
– Otherwise, it requires a rotation
• If neighbor is a 3-node or 4-node (red child)
– Move “inner value” from neighbor to parent, and “dividing
value” from parent to 2-node.
– This is a rotation
Deletion Examples (Delete 1)
2
4
1
2
4
3
1
6
5
9
6
3
5
9
Make a 4-node from 1, sibling
3, and “divider value” 2.
[Single rotation of 2,4,6]
Delete 6
4
4
2
6
3
5
2
9
9
3
4
6
Upgrade 6 by color flip,
swap with successor (9)
2
9
3
5
5
Delete 4
2
2
1
2
1
4
3
1
3
6
5
5
9
5
3
6
4
9
No 2-nodes to upgrade,
swap with successor (5)
6
9
Delete 2
2
2
1
5
3
1
6
6
5
9
Find 2-node enroute to successor (3)
Neighbor is 3-node (6,9)
Shift to get (3,5) and 9 as children,
6 up to parent.
9
3
Single rotation
Delete 2 (cont’d)
3
3
1
6
5
1
9
6
5
2
Swap with successor
Remove leaf
9