Insertion Example

Insert 65
47

32 71

93
Insertion Example
Insert 65
47

32 71

65 93
Insertion Example
Insert 65
Insert 82 47

32 71

65 93
Insertion Example
Insert 65
Insert 82 47

32 71

65 93

82
Insertion Example
Insert 65
Insert 82 47

32 71

65 93

change nodes’ colors

82
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 93

82
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 93

82

87
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 93

82

87
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 93

87

82
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 93

change nodes’ colors

87

82
Insertion Example
Insert 65
Insert 82 47
Insert 87
32 71

65 87

82 93
Left Rotation:
Modified algorithm
TreeNode<T> leftRotate(TreeNode<T> root,TreeNode<T> x)
//returns a new root; Pre: right child of x is a proper node (with value)
{
TreeNode<T> z = [Link]();

[Link]([Link]());
// Set parent reference
if ([Link]() != null)
[Link]().setParent(x);

[Link](x); //move x down

[Link]([Link]());
// Set parent reference of x
if ([Link]() != null) //x is not the root
if (x == [Link]().getLeft()) //left child
[Link]().setLeft(z);
else
[Link]().setRight(z);
else
root=z;

[Link](z);
return root;
}
RB Tree: Insertion Algorithm
TreeNode<T> rbInsert(TreeNode<T> root,TreeNode<T> x)
// returns a new root
{
root=bstInsert(root,x); // a modification of BST insertItem
[Link](red);
while (x != root and [Link]().getColor() == red) {
if ([Link]() == [Link]().getParent().getLeft()) {
//parent is left child
y = [Link]().getParent().getRight() //uncle of x
if ([Link]() == red) {// uncle is red
[Link]().setColor(black);
[Link](black);
[Link]().getParent().setColor(red);
x = [Link]().getParent();
} else { // uncle is black
// ................
}
} else
// ... symmetric to if
} // end while
[Link](black);
return root;
}
RB Tree: Insertion Algorithm
TreeNode<T> rbInsert(TreeNode<T> root,TreeNode<T> newNode)
// returns a new root
{
root=bstInsert(root,newNode); // a modification of BST insertItem
[Link](red);
while (x != root and [Link]().getColor() == red) {
if ([Link]() == [Link]().getParent().getLeft()) {
//parent is left

left_rotate on p
y = [Link]().getParent().getRight() //uncle of x
if ([Link]() == red) {// uncle is red
// ................ p

} else { // uncle is black

if (x == [Link]().getRight()) { x

x = [Link]();
root = left_rotate(root,x);
} right_rotate on p^2[x]
[Link]().setColor(black);
[Link]().getParent().setColor(red);
root = right_rotate(root,[Link]().getParent());
}
} else
// ... symmetric to if
} // end while
[Link](black);
return root;
}
Red-black Tree Deletion
 First use the standard BST tree deletion algorithm
 If the node to be deleted is replaced by its
successor/predecessor (if it has two non-null children), consider
the deleted node’s data as being replaced by it’s
successor/predecessor's, and its color remaining the same
 The successor/predecessor node is then removed
 Let y be the node to be removed
 If the removed node was red, no property could get violated, so
just remove it.
 Otherwise, remove it and call the tree-fix algorithm on y’s child x
(the node which replaced the position of y)
 Remember, the removed node can have at most one real (non-null)
child
 If it has one real child, call the tree-fix algorithm on it
 If it has no real children (both children are null), Note that this child
may be a (black) pretend (null) child
Fixing a red-black Tree
 The tree-fix algorithm considers the parameter (x)
as having an “extra” black token
 This corrects the violation of property 4 caused by
removing a black node
 If x is red, just color it black
 But if x is black then it becomes “doubly black”
 This is a violation of property 1
 The extra black token is pushed up the tree until
 a red node is reached, when it is made black
 the root node is reached or
 it can be removed by rotating and recoloring
Deletion Example 1
Delete 87
47

32 71

65 87

82 93
Deletion Example 1
Delete 87
47

32 71

65 87
82
Replace data with predecessor

Predecessor red: no violation

82 93
Deletion Example 2
Delete 71
47

32 71

65 87

51 82 93
Deletion Example 2
Delete 71
47

32 71
65

65 87
Replace with predecessor
Attach predecessor’s child

51 82 93
Deletion Example 2
Delete 71
47

32 65

87
Replace with predecessor
Attach predecessor’s child

Fix tree by coloring 51 82 93

predecessor’s child black
Deletion Example 3
Delete 32
47

32 71

65 87

82 93
Deletion Example 3
Delete 32
47

32 71
x

x
65 87
Identify x – the removed
node’s left child
Remove target node
Attach x to parent of target 82 93
Deletion Example 3
Delete 32
47

x 71

65 87
Identify x – the removed
node’s left child
Remove target node
Attach x to parent of target 82 93
Call rbTreeFix on x
RB Tree Deletion Algorithm
TreeNode<T> rbDelete(TreeNode<T> root,TreeNode<T> z)
//return new root, z contains item to be deleted
{
TreeNode<T> x,y;
// find node y, which is going to be removed
if ([Link]() == null || [Link]() == null)
y = z;
else {
y = successor(z); // or predecessor
[Link]([Link]); // move data from y to z
}

// find child x of y
if ([Link]() != null)
x = [Link]();
else
x = [Link]();

// Note x might be null; create a pretend node

if (x == null) {
x = new TreeNode<T>(null);
[Link](black);
}
RB Tree Deletion Algorithm
[Link]([Link]()); // detach x from y
if ([Link]() == null)
// if y was the root, x is a new root
root = x;
else
// Atttach x to y’s parent
if (y == [Link]().getLeft()) // left child
[Link]().setLeft(x);
else
[Link]().setRight(x);

if ([Link]() == black)
root=rbTreeFix(root,x);

if ([Link]() == null) // x is a pretend node

if (x==[Link]().getLeft())
[Link]().setLeft(null);
else
[Link]().setRight(null);

return root;
}
Deletion Example 3
(continued)
After deleting 32,
x is a node with 47
black token
y
x 71

65 87
Identify y, x’s sibling
Make y black and y’s parent
red
82 93
Left rotate x’s parent
Deletion Example 3
After deleting 32, y
x is a node with 71
black token
47 87

x new y
65 82 93
Identify y, x’s sibling
Make y black and
y’s parent red
Left rotate x’s parent
Identify y – x’s new sibling
Deletion Example 3
After deleting 32,
x is a node with 71
black token new x
47 87

x
y
65 82 93
Identify y, x’s sibling
Make y black and
y’s parent red
Left rotate x’s parent
Identify y – x’s new sibling
Color y red
Assign x it’s parent, and color it black
Tree Fix algorithm cases: case (1)
x is red
 The simplest case
 x has a black token and is colored red, so just
color it black and remove token a we are
done!

 In the remaining cases, assume x is black

(and has the black token, i.e., it’s double
black)
Tree Fix algorithm cases: case (2)
x’s sibling is red
Colors of y and z
Left_rotate(y)
were swapped

Colors of x and y
Right_rotate(y) were swapped

Remarks:
 the roots of subtrees C and D are black
 the second is the symmetric case, when x is the right child
 in the next step (case (3) or (4)) the algorithm will finish!
Tree Fix algorithm cases: case (3)
x’s sibling is black and both nephews are black

Remarks:
 nephews are roots of subtrees C and D
 the black token is passed one level up
Tree Fix algorithm cases: case (4)
x’s sibling is black and at least one nephew is red

Right_rotate(w) Left_rotate(y) Colors of y and z

were swapped.
Far nephew is
colored black and
Colors of z and w
black token is removed.
were swapped

Left_rotate(x) Right_rotate(z) Colors of z and y

were swapped.
Far nephew is
colored black and
black token is removed.
Colors of x and y
were swapped
Remarks:
 in this case, the black token is removed completely
 if the “far” nephew is black (subcase (i)), rotate its parent, so that
a new “far” nephew is red; otherwise start in subcase(ii)
Tree Fix Algorithm
TreeNode<T> rbTreeFix(TreeNode<T> root,TreeNode<T> x)
//return new root; x is a node with the black token
{
while (x != root && [Link]() == black) // not case (1)
if (x == [Link]().getLeft()) { // x is left child
y = [Link]().getRight(); // y is x’s sibling
if ([Link]() == red) { // case (2)
[Link](black);
[Link]().setColor(red); // p was black
root = left_rotate(root,[Link]());
y = [Link]().getRight(); // new sibling
}
if ([Link]().getColor() == black &&
[Link]().getColor() == black) {
// nephews are black - case (3)
[Link](red); Colors of y and z
x = [Link](); Left_rotate(y)
were swapped
} else { // case (4)
// ..........
}
} else { Colors of x and y
… // x is right child - symmetric Right_rotate(y) were swapped
}
// end while loop
[Link](black);
return root;
}
Tree Fix Algorithm (continued)
} else { // case (4)
if ([Link]().getColor() == black) {
// subcase (i)
[Link]().setColor(black);
[Link](red);
root = right_rotate(root,y);
y = [Link]().getRight();
}
// subcase (ii)
[Link]([Link]().getColor());
[Link]().setColor(black);
[Link]().setColor(black);
root = left_rotate(root, [Link]());
x = root; // we can finish
}

Right_rotate(w) Left_rotate(y)

Colors of z and w
were swapped

Left_rotate(x) Right_rotate(z) Colors of z and y

were swapped.
RB Trees efficiency
 All operations work in time O(height)
 and we have proved that heigh is O(log n)

 hence, all operations work in time O(log n)! – much more

efficient than linked list or arrays implementation of sorted list!

Sorted List Search Insertion Deletion

with arrays O(log n) O(n) O(n)
with linked list O(n) O(n) O(n)
with RB trees O(log n) O(log n) O(log n)