UNIT – III

SYLLABUS
SEARCH TREES

• BINARY SEARCH TREE

Definition
Implementation
Operations – searching, insertion, deletion
• AVL TREES
Definition
Height of an AVL tree
Operations- insertion, deletion and searching
• RED- BLACK TREES
• SPLAY TREES

91
 BINARY SEARCH TREE

Binary Search Tree is a special kind of binary tree in which nodes are arranged in a
specific order.

In a binary search tree (BST), each node contains-

• Only smaller values in its left sub tree
• Only larger values in its right sub tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties −
• The value of the key of the left sub-tree is less than the value of its parent (root) node's
key.
• The value of the key of the right sub-tree is greater than or equal to the value of its
parent (root) node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree
and can be defined as –
left_subtree (keys) < node (key) ≤ right_subtree (keys)

BST is a collection of nodes arranged in a way where they maintain BST properties. Each
node has a key and an associated value. While searching, the desired key is compared to the
keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST –

92
We observe that the root node key (27) has all less-valued keys on the left sub-tree and the
higher valued keys on the right sub-tree.
Example-

Number of Binary Search Trees-

93
Example-
Number of distinct binary search trees possible with 3 distinct keys
= 2×3C3 / 3+1
= 6C3 / 4
=5

If three distinct keys are A, B and C, then 5 distinct binary search trees are-

Binary Search Tree Construction-

Let us understand the construction of a binary search tree using the following example-

Example-

Construct a Binary Search Tree (BST) for the following sequence of numbers-
50, 70, 60, 20, 90, 10, 40, 100

When elements are given in a sequence,

94
• Always consider the first element as the root node.
• Consider the given elements and insert them in the BST one by one.

The binary search tree will be constructed as explained below-

Insert 50-

Insert 70-
• As 70 > 50, so insert 70 to the right of 50.

Insert 60-
• As 60 > 50, so insert 60 to the right of 50.
• As 60 < 70, so insert 60 to the left of 70.

Insert 20-
• As 20 < 50, so insert 20 to the left of 50.

95
 Insert 90-
• As 90 > 50, so insert 90 to the right of 50.
• As 90 > 70, so insert 90 to the right of 70.

Insert 10-
• As 10 < 50, so insert 10 to the left of 50.
• As 10 < 20, so insert 10 to the left of 20.

96
 Insert 40-
• As 40 < 50, so insert 40 to the left of 50.
• As 40 > 20, so insert 40 to the right of 20.

Insert 100-
• As 100 > 50, so insert 100 to the right of 50.
• As 100 > 70, so insert 100 to the right of 70.
• As 100 > 90, so insert 100 to the right of 90.

97
 This is the required Binary Search Tree.

Basic Operations
Following are the basic operations of a tree −
• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Pre-order Traversal − Traverses a tree in a pre-order manner.
• In-order Traversal − Traverses a tree in an in-order manner.
• Post-order Traversal − Traverses a tree in a post-order manner.

Node
Define a node having some data, references to its left and right child nodes
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};

98
 Search Operation
Search Operation is performed to search a particular element in the Binary Search Tree

Whenever an element is to be searched, start searching from the root node. Then if the data
is less than the key value, search for the element in the left subtree. Otherwise, search for
the element in the right subtree. Follow the same algorithm for each node.
Rules-

For searching a given key in the BST,

• Compare the key with the value of root node.
• If the key is present at the root node, then return the root node.
• If the key is greater than the root node value, then recur for the root node’s right subtree.
• If the key is smaller than the root node value, then recur for the root node’s left subtree.

Example-
Consider key = 45 has to be searched in the given BST-

• We start our search from the root node 25.

• As 45 > 25, so we search in 25’s right subtree.

99
• As 45 < 50, so we search in 50’s left subtree.
• As 45 > 35, so we search in 35’s right subtree.
• As 45 > 44, so we search in 44’s right subtree but 44 has no subtrees.
• So, we conclude that 45 is not present in the above BST.

Algorithm
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {
printf("%d ",current->data);

//go to left tree

if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}

//not found
if(current == NULL){
return NULL;
}
}
}

return current;
}

100
 Insertion Operation

Insertion Operation is performed to insert an element in the Binary Search Tree.

Rules-
The insertion of a new key always takes place as the child of some leaf node.
For finding out the suitable leaf node,
• Search the key to be inserted from the root node till some leaf node is reached.
• Once a leaf node is reached, insert the key as child of that leaf node.

Whenever an element is to be inserted, first locate its proper location. Start searching from
the root node, then if the data is less than the key value, search for the empty location in the
left subtree and insert the data. Otherwise, search for the empty location in the right subtree
and insert the data.

101
 Example-
Consider the following example where key = 40 is inserted in the given BST-

• We start searching for value 40 from the root node 100.

• As 40 < 100, so we search in 100’s left subtree.
• As 40 > 20, so we search in 20’s right subtree.
• As 40 > 30, so we add 40 to 30’s right subtree.

Algorithm
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;

tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;

//if tree is empty

if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;

102
 while(1) {
parent = current;

//go to left of the tree

if(data < parent->data) {
current = current->leftChild;
//insert to the left

if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;

//insert to the right

if(current == NULL) {
parent->rightChild = tempNode;
return;
}
} } } }
Deletion Operation-

Deletion Operation is performed to delete a particular element from the Binary Search Tree.

When it comes to deleting a node from the binary search tree, following three cases are
possible-

Case-01: Deletion Of A Node Having No Child (Leaf Node)-

Just remove / disconnect the leaf node that is to deleted from the tree.

103
Example-

Consider the following example where node with value = 20 is deleted from the BST-

Case-02: Deletion Of A Node Having Only One Child-

Just make the child of the deleting node, the child of its grandparent.

Example-

Consider the following example where node with value = 30 is deleted from the BST-

104
 Case-02: Deletion Of A Node Having Two Children-

A node with two children may be deleted from the BST in the following two ways-
Method-01:
• Visit to the right subtree of the deleting node.
• Pluck the least value element called as inorder successor.

Example-
Consider the following example where node with value = 15 is deleted from the BST-

105
 Method-02:
• Visit to the left subtree of the deleting node.
• Pluck the greatest value element called as inorder predecessor.
• Replace the deleting element with its inorder predecessor.

Example-
Consider the following example where node with value = 15 is deleted from the BST-

If the input to binary search tree comes in a sorted manner ., then BST looks like this(the
tree which is below) −

106
It is observed that BST's worst-case performance is closest to linear search algorithms, that
is Ο(n). In real-time data, we cannot predict data pattern and their frequencies.
So, a need arises to balance out the existing BST.

For example If three distinct keys are A, B and C, then 5 distinct binary search trees are-

➔ in the above trees all trees have the height as 3 except the one which is the middle.

The tree which is in the middle has minimum height i.e., 2 when compared to all other
trees.

107
➔ We require minimum height balanced tree, as time to perform search operation will be
reduced.

➔the need to balance out the existing BST ., gives rise to AVL TREEs.

AVL TREES
AVL Trees are named after their inventor Adelson, Velski & Landis.
AVL trees are height balancing binary search tree.
AVL tree checks the height of the left and the right sub-trees and assures that the
difference is not more than 1. This difference is called the Balance Factor.
Balance factor(bf) = height of left subtree(hl) – height of right subtree(hr)
bf = hl-hr = {-1,0,1}
|bf| = |hl – hr| ≤ 1
We calculate balance factor for each node
Here we see that the first tree is balanced and the next two trees are not balanced −

In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so
the difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing,
so it is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only
1.
If the difference in the height of left and right sub-trees is more than 1, then the tree is not
balanced ., then the tree should be balanced using some rotation techniques.

108
AVL Rotations

To balance itself, an AVL tree may perform the following four kinds of rotations −

• Left Left rotation(LL - rotation)

• Right Right rotation(RR - rotation)
• Left-Right rotation(LR - rotation)
• Right-Left rotation(RL - rotation)
The first two rotations are single rotations and the next two rotations are double rotations.
To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's
understand them one by one.
Note : rotations are performed on three nodes only .

Left rotation(LL rotation / L rotation ) :

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right
subtree, then we perform a single left rotation

In the above example, node A has become unbalanced as a node is inserted in the right
subtree of A's right subtree. We perform the left rotation by making A the left-subtree of B.

109
Right rotation(RR - rotation):

AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree.
The tree then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a
right rotation.

Left-Right rotation(LR - rotation) :

Double rotations are slightly complex version of already explained versions of rotations. To
understand them better, we should take note of each action performed while rotation. Let's
first check how to perform Left-Right rotation. A left-right rotation is a combination of left
rotation followed by right rotation.

State Action

110
A node has been inserted into the right subtree of the
left subtree. This makes C an unbalanced node. These
scenarios cause AVL tree to perform left-right rotation.

We first perform the left rotation on the left subtree

of C. This makes A, the left subtree of B.

Node C is still unbalanced, however now, it is because of

the left-subtree of the left-subtree.

We shall now right-rotate the tree, making B the new

root node of this subtree. C now becomes the right
subtree of its own left subtree.

111
 The tree is now balanced.

Right-Left Rotation (RL rotation):

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation
followed by left rotation.

State Action

A node has been inserted into the left subtree of the

right subtree. This makes A, an unbalanced node with
balance factor 2.

First, we perform the right rotation along C node,

making C the right subtree of its own left subtree B.
Now, B becomes the right subtree of A.

112
 Node A is still unbalanced because of the right subtree
of its right subtree and requires a left rotation.

A left rotation is performed by making B the new root

node of the subtree. A becomes the left subtree of its
right subtree B.

The tree is now balanced.

BASIC OPERATIONS:

INSERTION:
Algorithm for insertion operation

Step 1: First, insert a new element into the tree using BST's (Binary Search Tree) insertion
logic.
Step 2: After inserting the elements you have to check the Balance Factor of each node.
Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the
algorithm will proceed for the next operation.

113
 Step 4: When the balance factor of any node comes other than the above three values then
the tree is said to be imbalanced. Then perform the suitable Rotation to make it
balanced and then the algorithm will proceed for the next operation.

EXAMPLE : Construct AVL Tree for the following sequence of numbers-

50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48
Solution-

Step-01: Insert 50

Step-02: Insert 20
• As 20 < 50, so insert 20 in 50’s left sub tree.

Step-03: Insert 60
As 60 > 50, so insert 60 in 50’s right sub tree.

114
 Step-04: Insert 10
• As 10 < 50, so insert 10 in 50’s left sub tree.
• As 10 < 20, so insert 10 in 20’s left sub tree.

Step-05: Insert 8
• As 8 < 50, so insert 8 in 50’s left sub tree.
• As 8 < 20, so insert 8 in 20’s left sub tree.
• As 8 < 10, so insert 8 in 10’s left sub tree.

To balance the tree,

115
• Find the first imbalanced node on the path from the newly inserted node (node 8) to the
root node.
• The first imbalanced node is node 20.
• Now, count three nodes from node 20 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.
Following this, we

have-

Step-06: Insert 15
• As 15 < 50, so insert 15 in 50’s left sub tree.
• As 15 > 10, so insert 15 in 10’s right sub tree.
• As 15 < 20, so insert 15 in 20’s left sub tree.

To balance the tree,

• Find the first imbalanced node on the path from the newly inserted node (node 15) to the
root node.

116
• The first imbalanced node is node 50.
• Now, count three nodes from node 50 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.
Following this, we have-

Step-07: Insert 32
• As 32 > 20, so insert 32 in 20’s right sub tree.
• As 32 < 50, so insert 32 in 50’s left sub tree.

Step-08: Insert 46
• As 46 > 20, so insert 46 in 20’s right sub tree.
• As 46 < 50, so insert 46 in 50’s left sub tree.

117
• As 46 > 32, so insert 46 in 32’s right sub tree.

Step-09: Insert 11
• As 11 < 20, so insert 11 in 20’s left sub tree.
• As 11 > 10, so insert 11 in 10’s right sub tree.
• As 11 < 15, so insert 11 in 15’s left sub tree.

Step-10: Insert 48
• As 48 > 20, so insert 48 in 20’s right sub tree.
• As 48 < 50, so insert 48 in 50’s left sub tree.
• As 48 > 32, so insert 48 in 32’s right sub tree.
• As 48 > 46, so insert 48 in 46’s right sub tree.

118
 To balance the tree,
• Find the first imbalanced node on the path from the newly inserted node (node 48) to the
root node.
• The first imbalanced node is node 32.
• Now, count three nodes from node 32 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.

Following this, we have-

119
120
DELETION
Algorithm for deletion operation

Step 1: Firstly, find that node where k is stored

Step 2: Secondly delete those contents of the node (Suppose the node is x)
Step 3: Claim: Deleting a node in an AVL tree can be reduced by deleting a leaf. There are
three possible cases:

• When x has no children then, delete x

• When x has one child, let x' becomes the child of x.
• Notice: x' cannot have a child, since subtrees of T can differ in height by at most
one :
▪ then replace the contents of x with the contents of x'
▪ then delete x' (a leaf)

Step 4: When x has two children,

• then find x's successor z (which has no left child)

• then replace x's contents with z's contents, and
• delete z
In all of the three cases, you will end up removing a leaf.

EXAMPLE: Deletion of element 30 from the given AVL tree

121
SEARCHING
In an AVL tree, the search operation is performed with O(log n) time complexity. The search
operation in the AVL tree is similar to the search operation in a Binary search tree. We use
the following steps to search an element in AVL tree...

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than
that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6 - If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is
compared with the leaf node.

122
Step 8 - If we reach to the node having the value equal to the search value, then display
"Element is found" and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element,
then display "Element is not found" and terminate the function.

Red Black Tree

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where
h is the height of the BST. The cost of these operations may become O(n) for a skewed
Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion
and deletion, then we can guarantee an upper bound of O(Logn) for all these operations.
The height of a Red-Black tree is always O(Logn) where n is the number of nodes in the tree.

Comparison with AVL Tree

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more
rotations during insertion and deletion. So if your application involves many frequent
insertions and deletions, then Red Black trees should be preferred. And if the insertions and
deletions are less frequent and search is a more frequent operation, then AVL tree should
be preferred over Red-Black Tree

Introduction

Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows
following rules.

• Every node has a color either red or black.

• Root of tree is always black.
• Every leaf node which is NIL is black.
• If the node is red then its children are black.
• There are no two adjacent red nodes (A red node cannot have a red parent or red
child).
• Every path from a node (including root) to any of its descendant NULL node has the
same number of black nodes.

123
Basic operations:

• Insertion
• Deletion
• Searching

124
Insertion operation
• If the tree is empty then create new node as root node with black color
• If the tree is not empty then create a new node as a leaf node with color red
• If the parent of the new node is black then exit
• If the parent of new node is red then check the color of parents sibling of the new
node
▪ If the color is black or null then do suitable rotation or recolor
▪ If the color is red then recolor and also check if parents parent of new node
is not root node then recolor it and re-check

Examples of Insertion

125
Deletion operation

Step 1: Perform BST Deletion

Step 2: Case 1:: if node to be deleted is red, then simply delete it

Case 2:: if a node to be deleted is black with one red child, then replace the
node which we want to delete with its red child and delete that red child simply.

126
127
Step 3: case 1:: if root is double black(DB), just remove DB and keep it simply black.

Case 2: if DB’s sibling is black and both its children are black, then
• remove DB and
• Add black to its parent (P)→ if P is red it becomes black or if P is black
then it becomes DB
• Make sibling red
• If still DB exists then apply the cases
Example:

128
Example:

129
Case 3: if DBs sibling is red, then.,
• swap colors of parent and its sibling
• Rotate parent in DB direction
• If DB still exists then Reapply cases

130
Case 4: if DBs sibling is black, siblings child who is far from DB is black but near child to
DB is red, then.,
• Swap color of DBs sibling and siblings child who is near to DB
• Rotate sibling in opposite direction of DB
• Still DB exist then apply the next case i.e., case 5

Case 5: if DBs sibling is black, far child is red, then.,

• Swap color of parent and sibling
• Rotate parent in DBs direction
• Remove DB
• Change color of red child to black

131
Example: Given the following tree.,

Delete elements 55, 30, 90, 80, 50, 35, 15 one by one
Solution:

132
Hence, element 55 is deleted and all its DB cases are verified and rectified.

133
Similarly, all other nodes to be deleted with the continuity of the above tree.
SPLAY TREE:

The worst case time complexity of Binary Search Tree (BST) operations like search, delete,
insert is O(n). The worst case occurs when the tree is skewed. We can get the worst case
time complexity as O(log n) with AVL and Red-Black Trees.

Does splay trees does better than AVL or Red-Black trees in practical situations?

Like AVL and Red-Black Trees, Splay tree is also self-balancing BST. The main idea of splay
tree is to bring the recently accessed item to root of the tree, this makes the recently
searched item to be accessible in O(1) time if accessed again. The idea is to use locality of
reference (In a typical application, 80% of the access are to 20% of the items). Imagine a
situation where we have millions or billions of keys and only few of them are accessed
frequently, which is very likely in many practical applications.
All splay tree operations run in O(log n) time on average, where n is the number of entries in
the tree. Any single operation can take Theta(n) time in the worst case.
Splay Tree:

Splay Trees are self adjusted BST.

Basic operations:

Insertion of an element in splay tree ➔ insertion of BST + splaying

Deletion of an element in splay tree➔deletion of BST + splaying

Searching of an element in splay tree➔ searching of BST + splaying

SPLAYING ➔ move node to the root

SEARCH OPERATION :

The search operation in splay tree does the standard BST search, in addition to search it
also splays.

If the search is successful, then the node that is found is splayed and becomes the new
root node. Else the last node accessed prior to reaching the NULL is splayed and becomes
the new root.

134
There are following cases for the node being accessed:

1) Node is root We simply return the root, don’t do anything else as the accessed node is
already root.

2) Zig rotation / Zag rotation:

Node is child of root (the node has no grandparent). Node is either a left child of root
(we do a right rotation) or node is a right child of its parent (we do a left rotation).T1,
T2 and T3 are sub trees of the tree rooted with y (on left side) or x (on right side).

3) Node has both parent and grandparent.

a) Zig-Zig and Zag-Zag Rotation :

Node is left child of parent and parent is also left child of grandparent
(Two right rotations) OR node is right child of its parent and parent is also right child
of grandparent (Two Left Rotations).

135
b) Zig-Zag rotation and Zag-Zig rotation:
Node is left child of parent and parent is right child of grandparent (Left
Rotation followed by right rotation) OR node is right child of its parent and parent is
left child of grandparent (Right Rotation followed by left rotation).

136
 Node 20 is found
in the given tree
by applying
Example: Given graph., below., search node 20. standard BST
operation, then
splay node 20

NOTE: The search or splay operation not only brings the searched key to root, but also
balances the BST. For example in above case, height of BST is reduced by 1.
Example: Consider the given graph and apply search operation to find element 7.

137
Solution:
 apply standard binary search tree operation to find 7
Search is successful, element found at left of root node.
Element 7 is the left child of root node.
 Now apply splaying onto the element 7→make it the root of the tree.
→ apply right rotation ➔ ZIG ROTATION

Overview:

1) Splay trees have excellent locality properties. Frequently accessed items are easy to find.
Infrequent items are out of way.
2) All splay tree operations take O(Logn) time on average. Splay trees can be rigorously
shown to run in O(log n) average time per operation, over any sequence of operations
(assuming we start from an empty tree)
3) Splay trees are simpler compared to AVL and Red-Black Trees as no extra field is required
in every tree node.
4) Unlike AVL tree, a splay tree can change even with read-only operations like search.

Applications of Splay Trees:

• Splay trees have become the most widely used basic data structure invented in the
last 30 years, because they’re the fastest type of balanced search tree for many
applications.

138