Scribd
Upload
45 views

Lab Assignment No.5(B)_Write-Up

The document outlines a lab assignment focused on implementing a Binary Search Tree (BST) to manage keywords and their meanings, including operations for insertion, deletion, updating, and displaying data. It provides detailed algorithms for each operation and emphasizes the efficiency of BSTs in data handling. The assignment also includes software requirements and a flowchart for visual representation of the algorithms.

Uploaded by

umeshsabale.2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
45 views

Lab Assignment No.5(B)_Write-Up

The document outlines a lab assignment focused on implementing a Binary Search Tree (BST) to manage keywords and their meanings, including operations for insertion, deletion, updating, and displaying data. It provides detailed algorithms for each operation and emphasizes the efficiency of BSTs in data handling. The assignment also includes software requirements and a flowchart for visual representation of the algorithms.

Uploaded by

umeshsabale.2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

LAB ASSIGNMENT NO.

5(B)
Aim:
A Dictionary stores keywords and its meanings. Provide facility for adding new keywords, deleting
keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/
Descending order. Also find how many maximum comparisons may require for finding any
keyword. Use Binary Search Tree for implementation.

Title:
Operations on a Binary Search Tree: Construction, Insertion, Traversal, and Modification
Software Requirements :
Operating System recommended:- 64-bit Open source Linux or its derivative
Programming tools recommended:- Open Source G++/GCC

Objective:
To build a Binary Search Tree (BST) and perform basic operations like adding a node,
finding the longest path, getting the smallest value, swapping left and right children, and
searching for a value.

Theory:

Binary Tree : A tree is said to be a Binary tree if each node of the tree have maximum of two
child nodes. The children of the node of binary tree are ordered.
Binary Search Tree (BST ) : A binary tree in which each internal node x stores an element
such that the element stored in the left subtree of x are less than or equal to x and elements
stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree
property.
Operations on Binary search Tree :
1. Insertion
Insertion begins as a search would begin; if the root is not equal to the value, we search the
left or right subtrees as before. Eventually, we will reach an external node and add the value
as its right or left child, depending on the node's value. In other words, we examine the root
and recursively insert the new node to the left subtree if the new value is less than the root, or
the right subtree if the new value is greater than or equal to the root.
2. Searching : Searching a binary tree for a specific value can be a recursive or iterative
process. This explanation covers a recursive method. We begin by examining the root node.
If the tree is null, the value we are searching for does not exist in the tree. Otherwise, if the
value equals the root, the search is successful. If the value is less than the root, search the left
subtree. Similarly, if it is greater than the root, search the right subtree. This process
is repeated until the value is found or the indicated subtree is null. If the searched value is not
found before a null subtree is reached, then the item must not be present in the tree.

3. Deletion :There are three possible cases to consider:


1. Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply
remove it from the tree.
2. Deleting a node with one child: Remove the node and replace it with its child.
3. Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead,
choose either its in-order successor node or its in-order predecessor node, R. Replace the
value of N with the value of R, then delete R.
As with all binary trees, a node's in-order successor is the left-most child of its right
subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either
case, this node will have zero or one children. Delete it according to one of the two simpler
cases above.

Algorithm

1. Insert a New Keyword and Its Meaning

 Procedure: Insert keyword and meaning into the BST.


 Steps:
1. If root is null, create a new node.
2. If keyword < root.keyword, insert in the left subtree.
3. If keyword > root.keyword, insert in the right subtree.
4. Return the root.

2. Delete a Keyword
 Procedure: Delete the node with the specified keyword.
 Steps:
1. Search the tree for the node.
2. If node has no children, set it to null.
3. If node has one child, link it to the parent.
4. If node has two children, find the inorder successor, replace, and delete the
successor.

3. Update the Meaning of a Keyword

 Procedure: Update the meaning of the keyword if found.


 Steps:
1. Search for the keyword.
2. If found, update the meaning.
3. If not found, print "Keyword not found".

4. Display Keywords in Sorted Order

 Procedure: Display keywords and meanings in ascending or descending order.


 Steps:
1. For ascending order: Perform in-order traversal of the tree.
2. For descending order: Perform reverse in-order traversal.

5. Find Maximum Comparisons for Keyword Search

 Procedure: Find the maximum comparisons required for searching a keyword.


 Steps:
1. The number of comparisons is equivalent to the height of the tree.
2. Compute the height of the tree using recursion.

Flowchart :

Draw flowchart for above algorithm

Conclusion:
A Binary Search Tree (BST) enables efficient data operations, making it useful in searching,
sorting, and database applications.

You might also like