APEX INSTITUTE OF TECHNOLOGY

Bachelor of Engineering (Computer Science &

Engineering)

Subject: Data Structure

Subject Code: 23CSH-241
Chapter: Binary Search Tree
Subject Coordinator:
Ms. Upasana Tiwari
(E15791)

Binary Search Tree

Lecture No.-3.6 DISCOVER . LEARN .
EMPOWER
Index
• Binary Search trees
• Searching
• AVL Tree
• B Tree

2 2
Binary Search Tree
• What is a Binary Search tree?
• A binary search tree follows some order to arrange
the elements. In a Binary search tree, the value of
left node must be smaller than the parent node,
and the value of right node must be greater than
the parent node. This rule is applied recursively to
the left and right subtrees of the root.
Advantages Of Binary
Search Tree
• Searching an element in the Binary search tree is
easy as we always have a hint that which subtree
has the desired element.
• As compared to array and linked lists, insertion and
deletion operations are faster in BST.
Example of creating a
binary search tree
• Now, let's see the creation of binary search tree using an
example.
• Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
• First, we have to insert 45 into the tree as the root of the tree.
• Then, read the next element; if it is smaller than the root node,
insert it as the root of the left subtree, and move to the next
element.
• Otherwise, if the element is larger than the root node, then
insert it as the root of the right subtree.
• Now, let's see the process of creating the Binary search tree using
the given data element. The process of creating the BST is shown
below -
Continue..
• Step 1 - Insert 45.

• Step 2 - Insert 15: As 15 is smaller than 45, so insert

it as the root node of the left subtree
Continue..
• Step 3 - Insert 79.
As 79 is greater than 45, so insert it as the root node
of the right subtree.
Continue
• Step 4 - Insert 90.
90 is greater than 45 and 79, so it will be inserted as
the right subtree of 79.
Continue
• Step 5 - Insert 10.
10 is smaller than 45 and 15, so it will be inserted as
a left subtree of 15.
Continue
• Step 6 - Insert 55.
55 is larger than 45 and smaller than 79, so it will be
inserted as the left subtree of 79.
Continue
• Step 7 - Insert 12.
12 is smaller than 45 and 15 but greater than 10, so it
will be inserted as the right subtree of 10.
Continue
• Step 8 - Insert 20.
20 is smaller than 45 but greater than 15, so it will be
inserted as the right subtree of 15.
Continue
• Step 9 - Insert 50.
50 is greater than 45 but smaller than 79 and 55. So,
it will be inserted as a left subtree of 55.
Searching In Binary
Search Tree
Searching means to find or locate a specific element or node in a data
structure. In Binary search tree, searching a node is easy because elements
in BST are stored in a specific order. The steps of searching a node in Binary
Search tree are listed as follows -
• First, compare the element to be searched with the root element of the
tree.
• If root is matched with the target element, then return the node's
location.
• If it is not matched, then check whether the item is less than the root
element, if it is smaller than the root element, then move to the left
subtree.
• If it is larger than the root element, then move to the right subtree.
• Repeat the above procedure recursively until the match is found.
• If the element is not found or not present in the tree, then return NULL.
Searching In Binary
Search Tree Example
We are taking the binary search tree formed above.
Suppose we have to find node 20 from the below
tree.
Step1:
Continue..
Step2:
Continue..
Step 3:
Algorithm to search an
element in Binary
search tree
Search (root, item)
Step 1 - if (item = root → data) or (root = NULL)
return root
else if (item < root → data)
return Search(root → left, item)
else
return Search(root → right, item)
END if
Step 2 - END
Deletion in Binary
Search tree
In a binary search tree, we must delete a node from
the tree by keeping in mind that the property of BST
is not violated. To delete a node from BST, there are
three possible situations occur -
• The node to be deleted is the leaf node, or,
• The node to be deleted has only one child, and,
• The node to be deleted has two children
We will understand the situations listed above in
detail.
Leaf Node Deletion in Binary
Search Tree
We can see the process to delete a leaf node from
BST in the below image. In below image, suppose we
have to delete node 90, as the node to be deleted is
a leaf node, so it will be replaced with NULL, and the
allocated space will free.
When the node to be deleted has
only one child
In this case, we have to replace the target node with
its child, and then delete the child node. It means
that after replacing the target node with its child
node, the child node will now contain the value to be
deleted. So, we simply have to replace the child node
with NULL and free up the allocated space.
In the below image, suppose we have to delete the
node 79, as the node to be deleted has only one
child, so it will be replaced with its child 55.
So, the replaced node 79 will now be a leaf node that
can be easily deleted.
When the node to be deleted has
only one child
When the node to be deleted has
two children

This case of deleting a node in BST is a bit complex among other two cases.
In such a case, the steps to be followed are listed as follows -
• First, find the inorder successor of the node to be deleted.
• After that, replace that node with the inorder successor until the target
node is placed at the leaf of tree.
• And at last, replace the node with NULL and free up the allocated space.
The inorder successor is required when the right child of the node is not
empty. We can obtain the inorder successor by finding the minimum
element in the right child of the node.
We can see the process of deleting a node with two children from BST in
the below image. In the below image, suppose we have to delete node 45
that is the root node, as the node to be deleted has two children, so it will
be replaced with its inorder successor. Now, node 45 will be at the leaf of
the tree so that it can be deleted easily.
When the node to be deleted has
two children
Insertion in Binary Search tree
A new key in BST is always inserted at the leaf. To
insert an element in BST, we have to start searching
from the root node; if the node to be inserted is less
than the root node, then search for an empty location
in the left subtree. Else, search for the empty location
in the right subtree and insert the data. Insert in BST is
similar to searching, as we always have to maintain
the rule that the left subtree is smaller than the root,
and right subtree is larger than the root.
Now, let's see the process of inserting a node into BST
using an example.
Insertion in Binary Search tree
AVL Tree

• AVL Tree is invented by GM Adelson - Velsky and

EM Landis in 1962. The tree is named AVL in honors
of its inventors.
• AVL Tree can be defined as height balanced binary
search tree in which each node is associated with a
balance factor which is calculated by subtracting
the height of its right sub-tree from that of its left
sub-tree.
AVL Tree

• Tree is said to be balanced if balance factor of each

node is in between -1 to 1, otherwise, the tree will be
unbalanced and need to be balanced.
• Balance Factor (k) = height (left(k)) - height (right(k))
• If balance factor of any node is 1, it means that the left
sub-tree is one level higher than the right sub-tree.7
• If balance factor of any node is 0, it means that the left
sub-tree and right sub-tree contain equal height.
• If balance factor of any node is -1, it means that the
left sub-tree is one level lower than the right sub-tree.
AVL Tree Example

• An AVL tree is given in the following figure. We can

see that, balance factor associated with each node
is in between -1 and +1. therefore, it is an example
of AVL tree.
Why AVL Tree?

• AVL tree controls the height of the binary search

tree by not letting it to be skewed. The time taken
for all operations in a binary search tree of height h
is O(h). However, it can be extended to O(n) if the
BST becomes skewed (i.e. worst case). By limiting
this height to log n, AVL tree imposes an upper
bound on each operation to be O(log n) where n is
the number of nodes.
Operations on AVL tree

• Due to the fact that, AVL tree is also a binary search

tree therefore, all the operations are performed in
the same way as they are performed in a binary
search tree. Searching and traversing do not lead to
the violation in property of AVL tree. However,
insertion and deletion are the operations which can
violate this property and therefore, they need to be
revisited.
Operations on AVL tree
Sl. Operation Description
No

1 Insertion Insertion in AVL tree is performed in the same way as it is

performed in a binary search tree. However, it may lead
to violation in the AVL tree property and therefore the
tree may need balancing. The tree can be balanced by
applying rotations.

2 Deletion Deletion can also be performed in the same way as it is

performed in a binary search tree. Deletion may also
disturb the balance of the tree therefore, various types of
rotations are used to rebalance the tree.
AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other
than -1, 0, and 1. There are basically four types of rotations which are as
follows:
• L L rotation: Inserted node is in the left subtree of left subtree of A
• R R rotation : Inserted node is in the right subtree of right subtree of A
• L R rotation : Inserted node is in the right subtree of left subtree of A
• R L rotation : Inserted node is in the left subtree of right subtree of A
Where node A is the node whose balance Factor is other than -1, 0, 1.
The first two rotations LL and RR are single rotations and the next two
rotations LR and RL are double rotations. For a tree to be unbalanced,
minimum height must be at least 2. Let us understand each rotation.
RR Rotation
When BST becomes unbalanced, due to a node is
inserted into the right subtree of the right subtree
of A, then we perform RR rotation, RR rotation is an
anticlockwise rotation, which is applied on the edge
below a node having balance factor -2

In above example, node A has balance factor -2

because a node C is inserted in the right subtree of
A right subtree. We perform the RR rotation on the
edge below A.
LL Rotation
When BST becomes unbalanced, due to a node is inserted into the
left subtree of the left subtree of C, then we perform LL rotation,
LL rotation is clockwise rotation, which is applied on the edge
below a node having balance factor 2.

In above example, node C has balance factor 2 because a node A is

inserted in the left subtree of C left subtree. We perform the LL
rotation on the edge below A.
LR Rotation
Double rotations are bit tougher than
single rotation which has already
explained above. LR rotation = RR
rotation + LL rotation, i.e., first RR
rotation is performed on subtree and
then LL rotation is performed on full tree,
by full tree we mean the first node from
the path of inserted node whose balance
factor is other than -1, 0, or 1.
LR Rotation
State Action

A node B has been inserted into the right subtree

of A the left subtree of C, because of which C has
become an unbalanced node having balance
factor 2. This case is L R rotation where: Inserted
node is in the right subtree of left subtree of C
As LR rotation = RR + LL rotation, hence RR
(anticlockwise) on subtree rooted at A is
performed first. By doing RR rotation, node A,
has become the left subtree of B.

After performing RR rotation, node C is still

unbalanced, i.e., having balance factor 2, as
inserted node A is in the left of left of C

Now we perform LL clockwise rotation on full

tree, i.e. on node C. node C has now become the
right subtree of node B, A is left subtree of B

Balance factor of each node is now either -1, 0, or

1, i.e. BST is balanced now.
RL Rotation
• As already discussed, that double rotations
are bit tougher than single rotation which
has already explained above. RL Rotation =
LL rotation + RR rotation, i.e., first LL
rotation is performed on subtree and then
RR rotation is performed on full tree, by
full tree we mean the first node from the
path of inserted node whose balance
factor is other than -1, 0, or 1.
RL Rotation
State Action

A node B has been inserted into the left subtree

of C the right subtree of A, because of which A
has become an unbalanced node having balance
factor - 2. This case is RL rotation where: Inserted
node is in the left subtree of right subtree of A

As RL rotation = LL rotation + RR rotation,

hence, LL (clockwise) on subtree rooted at C is
performed first. By doing RR rotation,
node C has become the right subtree of B.

After performing LL rotation, node A is still

unbalanced, i.e. having balance factor -2, which is
because of the right-subtree of the right-subtree
node A.

Now we perform RR rotation (anticlockwise

rotation) on full tree, i.e. on node A. node C has
now become the right subtree of node B, and node
A has become the left subtree of B.

Balance factor of each node is now either -1, 0, or

1, i.e., BST is balanced now.
Example
Construct an AVL tree having the following
elements:
H, I, J, B, A, E, C, F, D, G, K, L
Ans:
1. Insert H, I, J
Continue..
On inserting the above elements, especially in the
case of H, the BST becomes unbalanced as the
Balance Factor of H is -2. Since the BST is right-
skewed, we will perform RR Rotation on node H.
The resultant balance tree is:
Continue..
• 2. Insert B, A
Continue..
On inserting the above elements, especially in case
of A, the BST becomes unbalanced as the Balance
Factor of H and I is 2, we consider the first node
from the last inserted node i.e. H. Since the BST
from H is left-skewed, we will perform LL Rotation
on node H.
The resultant balance tree is:
Continue..
• 3. Insert E

On inserting E, BST becomes unbalanced as the Balance Factor of I is

2, since if we travel from E to I we find that it is inserted in the left
subtree of right subtree of I, we will perform LR Rotation on node
I. LR = RR + LL rotation
Continue..
• 3 a) We first perform RR rotation on node B
• The resultant tree after RR rotation is:
Continue..
3b) We first perform LL rotation on the node I
The resultant balanced tree after LL rotation is:
Continue..
4. Insert C, F, D

On inserting C, F, D, BST becomes unbalanced as the

Balance Factor of B and H is -2, since if we travel from D to
B we find that it is inserted in the right subtree of left
subtree of B, we will perform RL Rotation on node I. RL =
LL + RR rotation.
Continue..
• 4a) We first perform LL rotation on node E
• The resultant tree after LL rotation is:
Continue..
• 4b) We then perform RR rotation on node B
• The resultant balanced tree after RR rotation is:
Continue..
• 5. Insert G

On inserting G, BST become unbalanced as the

Balance Factor of H is 2, since if we travel from G to H,
we find that it is inserted in the left subtree of right
subtree of H, we will perform LR Rotation on node I. LR
= RR + LL rotation
Continue..
• 5 a) We first perform RR rotation on node C
The resultant tree after RR rotation is:
Continue..
• 5 b) We then perform LL rotation on node H
The resultant balanced tree after LL rotation is:
Continue..
• 6. Insert K

On inserting K, BST becomes unbalanced as the

Balance Factor of I is -2. Since the BST is right-skewed
from I to K, hence we will perform RR Rotation on the
node I.
Continue..
• The resultant balanced tree after RR rotation is:
Continue..
7. Insert L
On inserting the L tree is still balanced as the Balance
Factor of each node is now either, -1, 0, +1. Hence
the tree is a Balanced AVL tree
B Tree
B Tree is a specialized m-way tree that can be widely
used for disk access. A B-Tree of order m can have
at most m-1 keys and m children. One of the main
reason of using B tree is its capability to store large
number of keys in a single node and large key
values by keeping the height of the tree relatively
small.
Properties of B Tree
A B tree of order m contains all the properties of an M
way tree. In addition, it contains the following properties.
1. Every node in a B-Tree contains at most m children.
2. Every node in a B-Tree except the root node and
the leaf node contain at least m/2 children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.
It is not necessary that, all the nodes contain the same
number of children but, each node must have m/2
number of nodes.
Example
• A B tree of order 4 is shown in the following image.

• While performing some operations on B Tree, any property

of B Tree may violate such as number of minimum children a
node can have. To maintain the properties of B Tree, the tree
may split or join.
Operations
Searching :
Searching in B Trees is similar to that in Binary search tree. For
example, if we search for an item 49 in the following B Tree. The
process will something like following :
1. Compare item 49 with root node 78. since 49 < 78 hence,
move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.
Searching in a B tree depends upon the height of the tree. The search
algorithm takes O(log n) time to search any element in a B tree.
Operations
Inserting
• Insertions are done at the leaf node level. The following algorithm
needs to be followed in order to insert an item into B Tree.
• Traverse the B Tree in order to find the appropriate leaf node at which
the node can be inserted.
• If the leaf node contain less than m-1 keys then insert the element in
the increasing order.
• Else, if the leaf node contains m-1 keys, then follow the following steps.
• Insert the new element in the increasing order of elements.
• Split the node into the two nodes at the median.
• Push the median element upto its parent node.
• If the parent node also contain m-1 number of keys, then split it too by
following the same steps.
Example:
• Insert the node 8 into the B Tree of order 5 shown
in the following image.
Continue
• 8 will be inserted to the right of 5, therefore insert
8.
Continue
• The node, now contain 5 keys which is greater than
(5 -1 = 4 ) keys. Therefore split the node from the
median i.e. 8 and push it up to its parent node
shown as follows
Deletion
• Deletion is also performed at the leaf nodes. The node which is to be deleted
can either be a leaf node or an internal node. Following algorithm needs to be
followed in order to delete a node from a B tree.
• Locate the leaf node.
• If there are more than m/2 keys in the leaf node then delete the desired key
from the node.
• If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.
• If the left sibling contains more than m/2 elements then push its largest element up
to its parent and move the intervening element down to the node where the key is
deleted.
• If the right sibling contains more than m/2 elements then push its smallest element
up to the parent and move intervening element down to the node where the key is
deleted.
• If neither of the sibling contain more than m/2 elements then create a new leaf
node by joining two leaf nodes and the intervening element of the parent node.
• If parent is left with less than m/2 nodes then, apply the above process on the
parent too.
• If the node which is to be deleted is an internal node, then replace the node
with its in-order successor or predecessor. Since, successor or predecessor will
always be on the leaf node hence, the process will be similar as the node is
being deleted from the leaf node.
Example 1
Delete the node 53 from the B Tree of order 5 shown
in the following figure.
Continue..
• 53 is present in the right child of element 49. Delete it.

• Now, 57 is the only element which is left in the node, the

minimum number of elements that must be present in a
B tree of order 5, is 2. it is less than that, the elements in
its left and right sub-tree are also not sufficient
therefore, merge it with the left sibling and intervening
element of parent i.e. 49.
Continue..
The final B tree is shown as follows.
Application of B tree
B tree is used to index the data and provides fast
access to the actual data stored on the disks since,
the access to value stored in a large database that
is stored on a disk is a very time consuming
process.
Searching an un-indexed and unsorted database
containing n key values needs O(n) running time in
worst case. However, if we use B Tree to index this
database, it will be searched in O(log n) time in
worst case.
References
WEB LINKS
• https://www.geeksforgeeks.org/data-structures/
• https://www.javatpoint.com/data-structure-tutorial
• https://www.tutorialspoint.com/data_structures_al
gorithms/index.htm
VIDEO LINK
• https://www.youtube.com/watch?v=jDM6_TnYIqE
• https://www.youtube.com/watch?v=cySVml6e_Fc
• https://www.youtube.com/watch?v=aNU9XYYCHu8
THANK YOU

70