UNIT-III TREES

RED BLACK TREES

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit,
and that bit is often interpreted as the colour (red or black). These colors are used to ensure that
the tree remains balanced during insertions and deletions.

Properties of Red-Black Tree:

1. Every node has a color either red or black.
2. The root of tree is always black.
3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4. Every path from a node (including root) to any of its descendant NULL node has the
same number of black nodes.

Insertion of a node in Red Black Tree:

In a Red-Black Tree, every new node must be inserted with the color RED. The insertion
operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is
inserted with a color property. After every insertion operation, we need to check all the
properties of Red-Black Tree. If all the properties are satisfied then we go to next operation
otherwise we perform the following operation to make it Red Black Tree.

• 1. Recolor
• 2. Rotation
• 3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following steps...

• Step 1 - Check whether tree is Empty.

• Step 2 - If tree is Empty then insert the newNode as Root node with color Black and
exit from the operation.
• Step 3 - If tree is not Empty then insert the newNode as leaf node with color Red.
• Step 4 - If the parent of newNode is Black then exit from the operation.
• Step 5 - If the parent of newNode is Red then check the color of parentnode's sibling
of newNode.
• Step 6 - If it is colored Black or NULL then make suitable Rotation and Recolor it.
• Step 7 - If it is colored Red then perform Recolor. Repeat the same until tree becomes
Red Black Tree.
Deletion of a node in Red Black Tree:

1) Perform standard Binary Search Tree delete. When we perform standard delete operation in
BST, we always end up deleting a node which is either leaf or has only one child (For an
internal node, we copy the successor and then recursively call delete for successor, successor
is always a leaf node or a node with one child). So we only need to handle cases where a node
is leaf or has one child. Let v be the node to be deleted and u be the child that replaces v (Note
that u is NULL when v is a leaf and color of NULL is considered as Black).

2) Simple Case: If either u or v is red, we mark the replaced child as black (No change in black
height). Note that both u and v cannot be red as v is parent of u and two consecutive reds are
not allowed in red-black tree.

3) If Both u and v are Black.

3.1) Color u as double black. Now our task reduces to convert this double black to single
black. Note that If v is leaf, then u is NULL and color of NULL is considered as black. So the
deletion of a black leaf also causes a double black.

3.2) Do following while the current node u is double black and it is not root. Let sibling of
node be s.
(a): If sibling s is black and at least one of sibling’s children is red, perform rotation(s).
Let the red child of s be r. This case can be divided in four subcases depending upon
positions of s and r.
(i) Left Left Case (s is left child of its parent and r is left child of s or both children of s are
red). This is mirror of right right case shown in below diagram.
(ii) Left Right Case (s is left child of its parent and r is right child). This is mirror of right left
case shown in below diagram.
(iii) Right Right Case (s is right child of its parent and r is right child of s or both children of s
are red)
(iv) Right Left Case (s is right child of its parent and r is left child of s)

(b): If sibling is black and its both children are black, perform recoloring, and recur for
the parent if parent is black.

(c): If sibling is red, perform a rotation to move old sibling up, recolor the old sibling and
parent. The new sibling is always black (See the below diagram). This mainly converts the
tree to black sibling case (by rotation) and leads to case (a) or (b). This case can be divided in
two subcases.

(i) Left Case (s is left child of its parent). This is mirror of right right case shown in below
diagram. We right rotate the parent p.

(ii) Right Case (s is right child of its parent). We left rotate the parent p.
3.3) If u is root, make it single black and return (Black height of complete tree reduces by 1).
SPLAY TEES
Splay Tree is a self - adjusted Binary Search Tree in which every operation on element
rearranges the tree so that the element is placed at the root position of the tree.
In a splay tree, every operation is performed at the root of the tree. All the operations in splay
tree are involved with a common operation called "Splaying". Splaying an element, is the
process of bringing it to the root position by performing suitable rotation operations.
By splaying elements we bring more frequently used elements closer to the root of the tree so
that any operation on those elements is performed quickly. That means the splaying operation
automatically brings more frequently used elements closer to the root of the tree.

Every operation on splay tree performs the splaying operation. For example, the insertion
operation first inserts the new element using the binary search tree insertion process, then the
newly inserted element is splayed so that it is placed at the root of the tree. The search operation
in a splay tree is nothing but searching the element using binary search process and then
splaying that searched element so that it is placed at the root of the tree.

Rotations in Splay Tree

• Zig Rotation (Right)

• Zag Rotation (Left)
• Zig - Zig Rotation
• Zag - Zag Rotation
• Zig - Zag Rotation
• Zag - Zig Rotation
Zig Rotation
The Zig Rotation in splay tree is similar to the single right rotation in AVL Tree rotations. In zig rotation,
every node moves one position to the right from its current position. Consider the following example...

Zag Rotation
The Zag Rotation in splay tree is similar to the single left rotation in AVL Tree rotations. In zag rotation,
every node moves one position to the left from its current position. Consider the following example...

Zig-Zig Rotation
The Zig-Zig Rotation in splay tree is a double zig rotation. In zig-zig rotation, every node moves two
positions to the right from its current position. Consider the following example...

Zag-Zag Rotation
The Zag-Zag Rotation in splay tree is a double zag rotation. In zag-zag rotation, every node moves two
positions to the left from its current position. Consider the following example...
Zig-Zag Rotation
The Zig-Zag Rotation in splay tree is a sequence of zig rotation followed by zag rotation. In zig-zag
rotation, every node moves one position to the right followed by one position to the left from its current
position. Consider the following example...

Zag-Zig Rotation
The Zag-Zig Rotation in splay tree is a sequence of zag rotation followed by zig rotation. In zag-zig
rotation, every node moves one position to the left followed by one position to the right from its current
position. Consider the following example...
Insertion Operation on Splay Tree:

Deletion Operation on Splay Tree: