DSA SemII Unit V

SRES’s
SHREE RAMCHANDRA COLLEGE OFENGINEERING
Lonikand, Pune – 412216
Department of Computer Engineering
DSA Unit V

Q. Construct B tree of order 5 for the following data: [May 2022 6M]
78, 21, 14, 11, 97, 85, 74, 63, 45, 42, 57

Shree Ramchandra College of Engineering,Pune Page 1

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 2

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 3

DSA SemII Unit V

Q. Build B+ tree of order 3 for the following

data:
F, S, Q, K, C, L, H, T, V, W, M, R [May 2022 6M]

Shree Ramchandra College of Engineering,Pune Page 4

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 5

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 6

DSA SemII Unit V

Q. Construct a B Tree of order 5 with the following data : . [May 2023 9M]
DHZKBPQEASWTCLNYM

Shree Ramchandra College of Engineering,Pune Page 7

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 8

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 9

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 10

DSA SemII Unit V

Q Construct a B-Tree of order 3 by inserting numbers from 1 to 10. [May

2023 9M]

Shree Ramchandra College of Engineering,Pune Page 11

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 12

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 13

DSA SemII Unit V

Q Construct B-tree of order 4 by inserting the following data one at a time.

20, 10, 30, 15, 12, 40, 50 [Nov 22 6M]

Shree Ramchandra College of Engineering,Pune Page 14

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 15

DSA SemII Unit V

Q Construct the B+ Tree of order 4 for the following data: 1, 4, 7, 10, 17,
21, 31, 25, 19, 20, 28, 42. [Nov 22 6M]

Shree Ramchandra College of Engineering,Pune Page 16

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 17

DSA SemII Unit V

Q Build B+ tree of order 3 for the following:

1, 42, 38, 21, 31, 10, 17, 7, 31, 25, 20, 18. [Nov 22 6M]

Shree Ramchandra College of Engineering,Pune Page 18

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 19

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 20

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 21

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 22

DSA SemII Unit V

Q. What is trie tree? Explain insert and search operation on it.

[May 2023 8M]
Q. Explain with example trie.tree. Give advantage and applications of trie
tree. [May 2022 6M]

The Trie data structure is a tree-like data structure used for storing a dynamic
set of strings. It is commonly used for efficient retrieval and storage of keys in
a large dataset. The structure supports operations such as insertion, search,
and deletion of keys, making it a valuable tool in fields like computer science
and information retrieval. In this article we are going to explore insertion and
search operation in Trie Data Structure.

Representation of of Trie Node:

A Trie data structure consists of nodes connected by edges. Each node
represents a character or a part of a string. The root node, the starting point of the
Trie, represents an empty string. Each edge emanating from a node signifies a
specific character. The path from the root to a node represents the prefix of a
string stored in the Trie.
A simple structure to represent nodes of the English alphabet can be as follows.
struct TrieNode {

Shree Ramchandra College of Engineering,Pune Page 23

DSA SemII Unit V

// pointer array for child nodes of each node

TrieNode* childNode[26];

// Used for indicating ending of string

bool wordEnd;

TrieNode()
{
// constructor
// initialize the wordEnd variable with false
// initialize every index of childNode array with
// NULL
wordEnd = false;
for (int i = 0; i < 26; i++) {
childNode[i] = NULL;
}
}
};
Insertion in Trie Data Structure:
Let’s walk through the process of inserting the words into a Trie data structure.
We have already cover the basics of Trie and its node structure.
Here’s a visual representation of inserting the words “and” and “ant” into a Trie
data structure:

nsert Operation in Trie Data Structure

Shree Ramchandra College of Engineering,Pune Page 24

DSA SemII Unit V

Inserting “and” in Trie data structure:

 Start at the root node: The root node has no character associated with it and
its wordEnd value is 0, indicating no complete word ends at this point.
 First character “a”: Calculate the index using ‘a’ – ‘a’ = 0. Check if
the childNode[0] is null. Since it is, create a new TrieNode with the character
“a“, wordEnd set to 0, and an empty array of pointers. Move to this new
node.
 Second character “n”: Calculate the index using ‘n’ – ‘a’ = 13. Check
if childNode[13] is null. It is, so create a new TrieNode with the character
“n“, wordEnd set to 0, and an empty array of pointers. Move to this new
node.
 Third character “d”: Calculate the index using ‘d’ – ‘a’ = 3. Check
if childNode[3] is null. It is, so create a new TrieNode with the character
“d“, wordEnd set to 1 (indicating the word “and” ends here).
Inserting “ant” in Trie data structure:
 Start at the root node: Root node doesn’t contain any data but it keep track of
every first character of every string that has been inserted.
 First character “a”: Calculate the index using ‘a’ – ‘a’ = 0. Check if
the childNode[0] is null. We already have the “a” node created from the
previous insertion. so move to the existing “a” node.
 First character “n”: Calculate the index using ‘n’ – ‘a’ = 13. Check
if childNode[13] is null. It’s not, so move to the existing “n” node.
 Second character “t”: Calculate the index using ‘t’ – ‘a’ = 19. Check
if childNode[19] is null. It is, so create a new TrieNode with the character
“t“, wordEnd set to 1 (indicating the word “ant” ends here).
#include <bits/stdc++.h>
using namespace std;

struct TrieNode {

// pointer array for child nodes of each node

TrieNode* childNode[26];

// Used for indicating ending of string

bool wordEnd;

TrieNode()
{
// constructor
// initialize the wordEnd variable with false
// initialize every index of childNode array with

Shree Ramchandra College of Engineering,Pune Page 25

DSA SemII Unit V

// NULL
wordEnd = false;
for (int i = 0; i < 26; i++) {
childNode[i] = NULL;
}
}
};

void insert_key(TrieNode* root, string& key)

{
// Initialize the currentNode pointer
// with the root node
TrieNode* currentNode = root;

// Iterate across the length of the string

for (auto c : key) {

// Check if the node exist for the current

// character in the Trie.
if (currentNode->childNode[c - 'a'] == NULL) {

// If node for current character does not exist

// then make a new node
TrieNode* newNode = new TrieNode();

// Keep the reference for the newly created

// node.
currentNode->childNode[c - 'a'] = newNode;
}

// Now, move the current node pointer to the newly

// created node.
currentNode = currentNode->childNode[c - 'a'];
}

// Increment the wordEndCount for the last currentNode

// pointer this implies that there is a string ending at
// currentNode.
currentNode->wordEnd = 1;
}
Time Complexity: O(number of words * maxLengthOfWord)

Shree Ramchandra College of Engineering,Pune Page 26

DSA SemII Unit V

Searching in Trie Data Structure:

Searching for a key in Trie data structure is similar to its insert operation.
However, It only compares the characters and moves down. The search can
terminate due to the end of a string or lack of key in the trie.
Steps by step approach for searching in Trie Data structure:
 Start at the root node. This is the starting point for all searches within the
Trie.
 Traverse the Trie based on the characters of the word you are searching for.
For each character, follow the corresponding branch in the Trie. If the
branch doesn’t exist, the word is not present in the Trie.
 If you reach the end of the word and the wordEnd flag is set to 1, the
word has been found.
 If you reach the end of the word and the wordEnd flag is 0, the word is
not present in the Trie, even though it shares a prefix with an existing
word.
Here’s a visual representation of searching word “dad” in Trie data
structure:
Let’s assume that we have successfully inserted the words “and“, “ant“,
and “dad” into our Trie, and we have to search for specific words within
the Trie data structure. Let’s try searching for the word “dad“:

Search Operation in Trie Data Structure

 We start at the root node.
 We follow the branch corresponding to the character ‘d’.

Shree Ramchandra College of Engineering,Pune Page 27

DSA SemII Unit V

 We follow the branch corresponding to the character a’.

 We follow the branch corresponding to the character ‘d’.
 We reach the end of the word and wordEnd flag is 1. This means that “dad”
is present in the Trie.

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {

// pointer array for child nodes of each node

TrieNode* childNode[26];

// Used for indicating ending of string

bool wordEnd;

TrieNode()
{
// constructor
// initialize the wordEnd variable with false
// initialize every index of childNode array with
// NULL
wordEnd = false;
for (int i = 0; i < 26; i++) {
childNode[i] = NULL;
}
}
};

bool search_key(TrieNode* root, string& key)

{
// Initialize the currentNode pointer
// with the root node
TrieNode* currentNode = root;

// Iterate across the length of the string

for (auto c : key) {

// Check if the node exist for the current

// character in the Trie.
if (currentNode->childNode[c - 'a'] == NULL) {

// Given word does not exist in Trie

Shree Ramchandra College of Engineering,Pune Page 28

 DSA SemII Unit V

return false;
}

// Move the currentNode pointer to the already

// existing node for current character.
currentNode = currentNode->childNode[c - 'a'];
}

return (currentNode->wordEnd == true);

}

Advantages of Trie Tree

1. Trie (also known as prefix tree) is a tree-based data structure that is used to
store an associative array where the keys are sequences (usually strings).
Some advantages of using a trie data structure include:
2. Fast search: Tries support fast search operations, as we can search for a key
by traversing down the tree from the root, and the search time is directly
proportional to the length of the key. This makes tries an efficient data
structure for searching for keys in a large dataset.
3. Space-efficient: Tries are space-efficient because they store only the
characters that are present in the keys, and not the entire key itself. This
makes tries an ideal data structure for storing large dictionaries or lexicons.
4. Auto-complete: Tries are widely used in applications that require auto-
complete functionality, such as search engines or predictive text input.
5. Efficient insertion and deletion: Tries support fast insertion and deletion of
keys, as we can simply add or delete nodes from the tree as needed.
6. Efficient sorting: Tries can be used to sort a large dataset efficiently, as they
support fast search and insertion operations.
7. Compact representation: Tries provide a compact representation of a large
dataset, as they store only the characters that are present in the keys. This
makes them an ideal data structure for storing large dictionaries or lexicons.

Q Write an algorithm to insert a node in B Tree. [Nov 22 6M]

1. If the tree is empty, allocate a root node and insert the key.

2. Update the allowed number of keys in the node.

3. Search the appropriate node for insertion.

Shree Ramchandra College of Engineering,Pune Page 29
 DSA SemII Unit V

4. If the node is full, follow the steps below.

5. Insert the elements in increasing order.

6. Now, there are elements greater than its limit. So, split at the median.

7. Push the median key upwards and make the left keys as a left child and the right
keys as a right child.

8. If the node is not full, follow the steps below.

9. Insert the node in increasing order.

Shree Ramchandra College of Engineering,Pune Page 30

DSA SemII Unit V

Q. What is B+ tree? Give structure of it’s internal note. What is the difference
between B and B+ tree. [May 2022 6M]
B+ Tree is a generalization B Tree with effective and smooth functionality. In B+
Tree, records are stored in leaf nodes and Keys are stored in Internal node. In B+ Tree
each node contains data items.

Shree Ramchandra College of Engineering,Pune Page 31

DSA SemII Unit V

Q. Explain B+ tree delection with example. [May 2022 6M]

Q Write an algorithm to delete a node from B+tree. [Nov 22 6M]

o STEP 1: Find leaf L containing (key,pointer) entry to delete

o STEP 2:Remove entry from L
STEP 2a If L meets the "half full" criteria, then we're done.
STEP 2b Otherwise, L has too few data entries.
o STEP 3: If L's right sibling can spare an entry, then move smallest entry in
right sibling to L
STEP 3a: Else, if L's left sibling can spare an entry then move largest entry in
left sibling to L
STEP 3b: Else, merge L and a sibling
o STEP 4:If merging, then recursively deletes the entry (pointing toL or sibling)
from the parent.
o STEP 5: Merge could propagate to root, decreasing height

Shree Ramchandra College of Engineering,Pune Page 32

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 33

DSA SemII Unit V

Shree Ramchandra College of Engineering,Pune Page 34