UNIT-III

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −
• The left sub-tree of a node has a key less than or equal to its parent node's key.
• The right sub-tree of a node has a key greater than or equal to its parent 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)
Binary Tree Representation
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 −

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.
Basic Operations:
Following are the basic operations of a Binary Search Tree −
• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Delete- Delete 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.
Defining a Node
Define a node that stores some data, and references to its left and right child nodes.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
Search Operation
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.
Algorithm
1. START
2. Check whether the tree is empty or not
3. If the tree is empty, search is not possible
4. Otherwise, first search the root of the tree.
5. If the key does not match with the value in the root,
search its subtrees.
6. If the value of the key is less than the root value, search the left subtree
7. If the value of the key is greater than the root value, search the right subtree.
8. If the key is not found in the tree, return unsuccessful search.
9. END

Now, let's understand the searching in binary tree using an example. We are taking the binary search tree formed
above. Suppose we have to find node 20 from the below tree.
Insertion Operation
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.
Algorithm
1. START
2. If the tree is empty, insert the first element as the root node of the tree. The following elements are added as
the leaf nodes.
3. If an element is less than the root value, it is added into the left subtree as a leaf node.
4. If an element is greater than the root value, it is added into the right subtree as a leaf node.
5. The final leaf nodes of the tree point to NULL values as their child nodes.
6. END
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

Now, the creation of binary search tree is completed.

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 -
o The node to be deleted is the leaf node, or,
o The node to be deleted has only one child, and,
o The node to be deleted has two children
When the node to be deleted is the leaf node
It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL and simply free
the allocated space.

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.
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 -
o First, find the inorder successor of the node to be deleted.
o After that, replace that node with the inorder successor until the target node is placed at the leaf of tree.
o And at last, replace the node with NULL and free up the allocated space.

Inorder Traversal
The inorder traversal operation in a Binary Search Tree visits all its nodes in the following order −
• Firstly, we traverse the left child of the root node/current node, if any.
• Next, traverse the current node.
• Lastly, traverse the right child of the current node, if any.
Algorithm
1. START
2. Traverse the left subtree, recursively
3. Then, traverse the root node
4. Traverse the right subtree, recursively.
5. END
Preorder Traversal
The preorder traversal operation in a Binary Search Tree visits all its nodes. However, the root node in it is first
printed, followed by its left subtree and then its right subtree.
Algorithm
1. START
2. Traverse the root node first.
3. Then traverse the left subtree, recursively
4. Later, traverse the right subtree, recursively.
5. END
Postorder Traversal
Like the other traversals, postorder traversal also visits all the nodes in a Binary Search Tree and displays them.
However, the left subtree is printed first, followed by the right subtree and lastly, the root node.
Algorithm
1. START
2. Traverse the left subtree, recursively
3. Traverse the right subtree, recursively.
4. Then, traverse the root node
5. END

B TREE in Data Structure: Search, Insert, Delete Operation Example

B Tree is a self-balancing data structure based on a specific set of rules for searching, inserting, and deleting the
data in a faster and memory efficient way. In order to achieve this, the following rules are followed to create a B
Tree.
Rules for B-Tree
Here, are important rules for creating B_Tree
 • All leaves will be created at the same level.
• B-Tree is determined by a number of degree, which is also called “order” (specified by an external actor,
like a programmer), referred to as m onwards. The value of m depends upon the block size on the disk
on which data is primarily located.
• The left subtree of the node will have lesser values than the right side of the subtree. This means that
the nodes are also sorted in ascending order from left to right.
• The maximum number of child nodes, a root node as well as its child nodes can contain are calculated by
this formula: m – 1
For example: m = 4
max keys: 4 – 1 = 3

• Every node, except root, must contain minimum keys of

[m/2]-1
For example:
m=4
min keys: 4/2-1 = 1
• The maximum number of child nodes a node can have is equal to its degree, which is m
• The minimum children a node can have is half of the order, which is m/2 (the ceiling value is taken).
• All the keys in a node are sorted in increasing order.
Insert Operation
Since B Tree is a self-balancing tree, you cannot force insert a key into just any node.
The following algorithm applies:
• Run the search operation and find the appropriate place of insertion.
• Insert the new key at the proper location, but if the node has a maximum number of keys already:
• The node, along with a newly inserted key, will split from the middle element.
• The middle element will become the parent for the other two child nodes.
• The nodes must re-arrange keys in ascending order.
B+ TREE : Search, Insert and Delete Operations Example
A B+ Tree is primarily utilized for implementing dynamic indexing on multiple levels. Compared to B- Tree, the
B+ Tree stores the data pointers only at the leaf nodes of the Tree, which makes search more process more
accurate and faster.
Rules for B+ Tree
Here are essential rules for B+ Tree.
• Leaves are used to store data records.
• It stored in the internal nodes of the Tree.
• If a target key value is less than the internal node, then the point just to its left side is followed.
• If a target key value is greater than or equal to the internal node, then the point just to its right side is
followed.
• The root has a minimum of two children.
B+ Tree vs. B Tree
Here, are the main differences between B+ Tree vs. B Tree
B+ Tree B Tree
Search keys can be repeated. Search keys cannot be redundant.
Data is only saved on the leaf nodes. Both leaf nodes and internal nodes can store data
Data stored on the leaf node makes the search more Searching is slow due to data stored on Leaf and internal
accurate and faster. nodes.
Deletion is not difficult as an element is only Deletion of elements is a complicated and time-consuming
removed from a leaf node. process.
B+ Tree B Tree
Linked leaf nodes make the search efficient and
You cannot link leaf nodes.
quick.
Insert Operation
Insert Operation Algorithm
1.Even inserting at-least 1 entry into the leaf container does not make it full then add the record
2. Else, divide the node into more locations to fit more records.
a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
c. Divide the top-level node if it gets full of keys and addresses.
i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.
d. Continue to execute the above steps until a top-level node is found that does not need to be divided
anymore.
3) Build a new top-level root node of 1 Key and 2 indicators.

AVL Trees: Rotations, Insertion, Deletion with Example

AVL trees are binary search trees in which the difference between the height of the left and right subtree is either
-1, 0, or +1.
AVL trees are also called a self-balancing binary search tree. These trees help to maintain the logarithmic search
time. It is named after its inventors (AVL) Adelson, Velsky, and Landis.
Balance Factor in AVL Trees
Balance factor (BF) is a fundamental attribute of every node in AVL trees that helps to monitor the tree’s height.
Properties of Balance Factor

Balance factor AVL tree

• The balance factor is known as the difference between the height of the left subtree and the right
subtree.
• Balance factor(node) = height(node->left) – height(node->right)
• Allowed values of BF are –1, 0, and +1.
• The value –1 indicates that the right sub-tree contains one extra, i.e., the tree is right heavy.
• The value +1 indicates that the left sub-tree contains one extra, i.e., the tree is left heavy.
• The value 0 shows that the tree includes equal nodes on each side, i.e., the tree is perfectly balanced.
AVL Rotations
We perform the following LL rotation, RR rotation, LR rotation, and RL rotation.
• Left – Left Rotation
• Right – Right Rotation
• Right – Left Rotation
• Left – Right Rotation
Left – Left Rotation
This rotation is performed when a new node is inserted at the left child of the left subtree.

Right – Right Rotation

This rotation is performed when a new node is inserted at the right child of the right subtree.

Right – Left Rotation

This rotation is performed when a new node is inserted at the right child of the left subtree.

Left – Right Rotation

This rotation is performed when a new node is inserted at the left child of the right subtree.

Insertion in AVL Trees

Insert operation is almost the same as in simple binary search trees. After every insertion, we balance the height
of the tree. Insert operation takes O(log n) worst time complexity.
AVL tree insertion implementation
Step 1: Insert the node in the AVL tree using the same insertion algorithm of BST. In the above example, insert
160.
Step 2: Once the node is added, the balance factor of each node is updated. After 160 is inserted, the balance
factor of every node is updated.
Step 3: Now check if any node violates the range of the balance factor if the balance factor is violated, then
perform rotations using the below case. In the above example, the balance factor of 350 is violated and case 1
becomes applicable there, we perform LL rotation and the tree is balanced again.
1. If BF(node) = +2 and BF(node -> left-child) = +1, perform LL rotation.
2. If BF(node) = -2 and BF(node -> right-child) = 1, perform RR rotation.
3. If BF(node) = -2 and BF(node -> right-child) = +1, perform RL rotation.
4. If BF(node) = +2 and BF(node -> left-child) = -1, perform LR rotation.

Deletion in AVL Trees

 Red-black tree: Rotations, Insertion, Deletion with Example
The red-Black tree is a binary search tree. The prerequisite of the red-black tree is that we should know about
the binary search tree. In a binary search tree, the values of the nodes in the left subtree should be less than the
value of the root node, and the values of the nodes in the right subtree should be greater than the value of the
root node.
Properties of Red-Black tree:
o It is a self-balancing Binary Search tree. Here, self-balancing means that it balances the tree itself by
either doing the rotations or recoloring the nodes.
o This tree data structure is named as a Red-Black tree as each node is either Red or Black in color. Every
node stores one extra information known as a bit that represents the color of the node. For example, 0
bit denotes the black color while 1 bit denotes the red color of the node. Other information stored by
the node is similar to the binary tree, i.e., data part, left pointer and right pointer.
o In the Red-Black tree, the root node is always black in color.
o In a binary tree, we consider those nodes as the leaf which have no child. In contrast, in the Red-Black
tree, the nodes that have no child are considered the internal nodes and these nodes are connected to
the NIL nodes that are always black in color. The NIL nodes are the leaf nodes in the Red-Black tree.
o If the node is Red, then its children should be in Black color. In other words, we can say that there should
be no red-red parent-child relationship.
o Every path from a node to any of its descendant's NIL node should have same number of black nodes.

Insertion in Red Black tree

The following are some rules used to create the Red-Black tree:
1. If the tree is empty, then we create a new node as a root node with the color black.
2. If the tree is not empty, then we create a new node as a leaf node with a color red.
3. If the parent of a new node is black, then exit.
4. If the parent of a new node is Red, then we have to check the color of the parent's sibling of a new node.
4a) If the color is Black, then we perform rotations and recoloring.
4b) If the color is Red then we recolor the node. We will also check whether the parents' parent
of a new node is the root node or not; if it is not a root node, we will recolor and recheck
the node.

Deletion in Red Back tree

Let's understand how we can delete the particular node from the Red-Black tree. The following are the rules
used to delete the particular node from the tree:
Step 1: First, we perform BST rules for the deletion.
Step 2:
Case 1: if the node is Red, which is to be deleted, we simply delete it.
Case 2: If the root node is also double black, then simply remove the double black and make it a single black.
Case 3: If the double black's sibling is black and both its children are black.
o Remove the double black node.
o Add the color of the node to the parent (P) node.
1. If the color of P is red then it becomes black.
2. If the color of P is black, then it becomes double black.
o The color of double black's sibling changes to red.
o If still double black situation arises, then we will apply other cases.
Case 4: If double black's sibling is Red.
o Swap the color of its parent and its sibling.
o Rotate the parent node in the double black's direction.
o Reapply cases.
Case 5: If double black's sibling is black, sibling's child who is far from the double black is black, but near child to
double black is red.
o Swap the color of double black's sibling and the sibling child which is nearer to the double black node.
o Rotate the sibling in the opposite direction of the double black.
o Apply case 6
Case 6: If double black's sibling is black, far child is Red
o Swap the color of Parent and its sibling node.
o Rotate the parent towards the Double black's direction
o Remove Double black
o Change the Red color to black.
Splay trees: Insert, Delete and Search Operations
Splay trees are the altered versions of the Binary Search Trees, since it contains all the operations of BSTs, like
insertion, deletion and searching, followed by another extended operation called splaying.
For instance, a value "A" is supposed to be inserted into the tree. If the tree is empty, add "A" to the root of the
tree and exit; but if the tree is not empty, use binary search insertion operation to insert the element and then
perform splaying on the new node.
Similarly, after searching an element in the splay tree, the node consisting of the element must be splayed as
well.
There are six types of rotations for it.
• Zig rotation
• Zag rotation
• Zig-Zig rotation
• Zag-Zag rotation
• Zig-Zag rotation
• Zag-Zig rotation

Zig rotation
The zig rotations are performed when the operational node is either the root node or the left child node of the
root node. The node is rotated towards its right.

After the shift, the tree will look like −

Zag rotation
The zag rotations are also performed when the operational node is either the root node or the right child nod of
the root node. The node is rotated towards its left.

The operational node becomes the root node after the shift −

Zig-Zig rotation
The zig-zig rotations are performed when the operational node has both parent and a grandparent. The node is
rotated two places towards its right.

The first rotation will shift the tree to one position right −

The second right rotation will once again shift the node for one position. The final tree after the shift will look
like this −

Zag-Zag rotation
The zag-zag rotations are also performed when the operational node has both parent and a grandparent. The
node is rotated two places towards its left.

After the first rotation, the tree will look like −

Then the final tree after the second rotation is given as follows. However, the operational node is still not the
root so the splaying is considered incomplete. Hence, other suitable rotations are again applied in this case until
the node becomes the root.

Zig-Zag rotation
The zig-zag rotations are performed when the operational node has both a parent and a grandparent. But the
difference is the grandparent, parent and child are in LRL format. The node is rotated first towards its right
followed by left.

After the first rotation, the tree is −

The final tree after the second rotation −

Zag-Zig rotation
The zag-zig rotations are also performed when the operational node has both parent and grandparent. But the
difference is the grandparent, parent and child are in RLR format. The node is rotated first towards its left
followed by right.

First rotation is performed, the tree is obtained as −

After second rotation, the final tree is given as below. However, the operational node is not the root node yet so
one more rotation needs to be performed to make the said node as the root.