You will implement a binary search tree data structure in C++, and turn in a pro

Question

You will implement a binary search tree data structure in C++, and turn in a program evaluating the data structure. Implement a templated Binary Search Tree data structure, implementing the following functionality:

Add(value to insert)

Delete (delete given node, restructure sub-tree)

Maximum(Find Maximum Key)

To evaluate this data structure, write your program to read from an array of unsorted integers. You could also read from a data file (with the filename passed as a command line parameter) and populates the data structure. Rigorous testing is expected! Be sure to include tests for attempting to remove a node from an empty BST, attempting to insert a duplicate node, removing a node with no children, removing a node with one child, and removing a node with two children. Be sure to verify the BST organization and structure are correct.

BONUS - Performance Analysis of your Binary Tree Conduct a performance analysis of your BST and record the amount of time it takes to do Add and Remove the following: 100 nodes 1000 nodes 10000 nodes 100000 nodes Display your data in a data table and graph the results.

BONUS - Self-Balancing Binary Search Tree Implement a Self-Balancing Binary Search Tree (Links to an external site.)Links to an external site.. Evaluate the performance of this data structure as compared to the normal binary search tree on adding and removing 100, 1000, 10000, and 100000 nodes.

Explanation / Answer

Given below is the code for the question.
Please do rate the answer if it was helpful. Thank you

BST.h
=====
#ifndef BST_H
#define BST_H

struct TreeNode
{
int item;
TreeNode* Lchild;
TreeNode* Rchild;
};

class BST
{
public:
BST(); //default constructor
bool add(int i);
bool remove(int i);
void inorder();
int max();

private:
TreeNode *root;
void inorder(TreeNode *);
bool remove(TreeNode *n, TreeNode *parent);
};
#endif

BST.cpp
=======
#include "BST.h"
#include <iostream>
using namespace std;
BST::BST() //default constructor
{
root = NULL;
}
bool BST::add(int i)
{
TreeNode *n = new TreeNode();
n->item = i;
if(root == NULL)
{
root = n;
return true;
}
else
{
TreeNode *p = root;
while(p!=NULL)
{
if(i == p->item) //duplicate
return false;
else if(i < p->item) //if value to be inserted is less than current nodes value
{
if(p->Lchild == NULL) //go to left subtree
{
p->Lchild = n;
return true;
}
else
p = p->Lchild;
}
else
{
if(p->Rchild == NULL) //go to right subtree
{
p->Rchild = n;
return true;
}
else
p = p->Rchild;
}
}
}
return false;
}

bool BST::remove(TreeNode *n, TreeNode *parent)
{
if(n->Lchild == NULL && n->Rchild == NULL) //delteing leaf node
{
if(parent != NULL) //not deleting root
{
if(parent->Lchild == n)
parent->Lchild = NULL;
else
parent->Rchild = NULL;
}
else //deleteing root which is the only node in tree
root = NULL;

delete n;
}
else if(n->Lchild != NULL && n->Rchild ==NULL) //node to be deltedd has only left child
{
if(parent!=NULL)
{
if(parent->Lchild == n)
{
parent->Lchild = n->Lchild;
}
else
{
parent->Rchild = n->Lchild;
}
}
else //dleeting root with left child
root = n->Lchild; //update root

delete n;
}

else if(n->Rchild != NULL && n->Lchild ==NULL) //node to be deltedd has only right child
{
if(parent!=NULL) //not deleing root
{
if(parent->Lchild == n)
{
parent->Lchild = n->Rchild;
}
else
{
parent->Rchild = n->Rchild;
}
}
else //delting root with right child
root = n->Rchild; //update root

delete n;
}
else //node to be deleted has both the children
{
//find the rightmost node in left subtree i.e predecessor of n
TreeNode *q=n->Lchild,*qparent=n;
while(q->Rchild!=NULL)
{
qparent = q;
q = q->Rchild;
}
n->item = q->item;
return remove(q,qparent);
}

return true;
}
bool BST::remove(int i)
{

TreeNode *p = root, *parent =NULL;
while(p!=NULL)
{
if( p->item == i)
return remove(p, parent);

parent = p;
if(i < p->item)
{
p = p->Lchild;
}
else
{
p = p->Rchild;
}
}
return false;
}
void BST::inorder(TreeNode *n)
{
if(n == NULL )
return;

inorder(n->Lchild);
cout<<n->item<<" ";
inorder(n->Rchild);

}
void BST::inorder()
{
inorder(root);
cout<<endl;
}

int BST::max()
{
if(root == NULL)
return 0;
else
{
TreeNode* p = root;
while(p->Rchild != NULL)
p = p->Rchild;
return p->item;
}
}

BSTTest.cpp
==========
#include "BST.h"
#include <iostream>
using namespace std;
int main()
{
int arr[10] = { 15, 20 , 12, 60, 45, 33, 66, 89, 10, 3};
BST bst;
  
for(int i = 0 ; i < 10; i++)
{
cout << "Inserting " << arr[i] << endl;
bst.add(arr[i]);
}
  
  
int n;
string choice ="";
while(choice != "Q" && choice != "q")
{
cout << "Inorder traversal ";
bst.inorder();
  
cout << "Tree max: " << bst.max() << endl << endl;
  
  
cout << "(I)nsert (D)elete (Q)uit" << endl;
cout << "Enter your choice: ";
cin >> choice;
  
if(choice != "Q")
{
if(choice == "I" || choice == "i")
{
cout << "Enter a number to insert: ";
cin >> n;
if(bst.add(n))
cout << "Added " << n << " to BST " << endl;
else
cout << n << "is a duplicate" << endl;
  
}
else if(choice == "D" || choice == "d")
{
cout << "Enter number to delete from BST: ";
cin >> n;
if(bst.remove(n))
cout << "Removed " << n << " from BST " << endl;
else
cout << n << " not found in tree" << endl;

}
}
}
}

output
======

Inserting 15
Inserting 20
Inserting 12
Inserting 60
Inserting 45
Inserting 33
Inserting 66
Inserting 89
Inserting 10
Inserting 3
Inorder traversal 3 10 12 15 20 33 45 60 66 89
Tree max: 89

(I)nsert (D)elete (Q)uit
Enter your choice: i
Enter a number to insert: 5
Added 5 to BST
Inorder traversal 3 5 10 12 15 20 33 45 60 66 89
Tree max: 89

(I)nsert (D)elete (Q)uit
Enter your choice: i
Enter a number to insert: 100
Added 100 to BST
Inorder traversal 3 5 10 12 15 20 33 45 60 66 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: d
Enter number to delete from BST: 20
Removed 20 from BST
Inorder traversal 3 5 10 12 15 33 45 60 66 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: d
Enter number to delete from BST: 66
Removed 66 from BST
Inorder traversal 3 5 10 12 15 33 45 60 89 100
Tree max: 100

(I)nsert (D)elete (Q)uit
Enter your choice: q

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.