C++ Balanced Binary Search Tree. Please fix my code!! Hello there, I made a prog
ID: 3841097 • Letter: C
Question
C++ Balanced Binary Search Tree. Please fix my code!!
Hello there, I made a program for binary search tree register machine in C++.
When I run my program, my commands (create,insert,remove,merge, etc..) do not work. It actually gives me segmentation fault whenever I type commands.
My instructor told me that my tree implementation doesn't do any of the rebalancing/rotations needed after an insert or delete to preserve the AVL height-balance property.
So I guess that is the only thing wrong with my program.
I'm attaching the original prompt for the program so you can understand what I was actually trying to do.
I am pretty sure that I have completed part 1 so far.
And below is my code:
#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <istream>
using std::string;
struct node {
int key;
node* right;
node* left;
node* parent;
int height;
};
node*& find(node*& root, int key){
if(root == nullptr)
return root;
else if(root->key == key)
return root;
else if(key > root->key)
return find(root->right, key);
else
return find(root->left, key);
}
void insert(node*& root, int key){
node* n = find(root, key);
if(n == nullptr)
n = new node {key, nullptr, nullptr, nullptr, 1};
}
node*& largest(node*& root){
if(!root)
return root;
else if(!root->right)
return root;
else
return largest(root->right);
}
node*& pred(node*& target, int key){
if(target->left)
return largest(target -> left);
else
return largest(target -> right);
}
void remove(node*& root, int key){
node* n = find(root, key);
if(n){
if(!n -> left && !n -> right){
delete n;
n = nullptr;
}
if(!n -> right){
node* t = n -> left;
delete n;
n = t;
}
else if(!n -> left){
node* t = n -> right;
delete n;
n = t;
}
else{
node* k = pred(root, key);
std::swap(n -> key, k -> key);
remove(k, key);
}
}
}
//Instead of using void print function, I chose to use this one below.
void inorder(node* root, std::function<void(node*&)> visit){
if(!root)
return;
if(root->left)
inorder(root->left, visit);
visit(root);
if(root->right)
inorder(root->right, visit);
}
void spine(node* p, node*& prev, node*& head){
if(!p)
return;
spine(p->left, prev, head);
if(prev) prev->right = p;
else head = p;
prev = p;
p -> left = 0;
spine(p->right, prev, head);
}
void advance(node*& last, node*& n){
last->right = n;
last = n;
n = n-> right;
}
node* mergespines(node* n1, node* n2){
node head;
node* last = &head;
while(n1 || n2){
if(!n1)
advance(last, n2);
else if(!n2)
advance(last, n1);
else if(n1->right < n2->right)
advance(last, n1);
else if(n1->right > n2->right)
advance(last, n2);
else{
advance(last, n1);
n2 = n2 ->right;
}
}
return head.right;
}
node* balance2(node*& list, int start, int end){
if(start > end)
return nullptr;
int mid = start + (end - start) / 2;
node *leftchild = balance2(list, start, mid-1);
node *parent = list;
parent-> left = leftchild;
list = list->right;
parent->right = balance2(list, mid+1, end);
return parent;
}
node* balance(node *head){
int size = 0;
for(node* n = head; n; n = n ->right)
size++;
return balance2(head, 0, size-1);
}
node* merge(node* t1, node* t2){
node *prev, *head1, *head2;
prev = head1 = 0;
spine(t1, prev, head1);
prev = head2 = 0;
spine(t2, prev, head2);
return balance(mergespines(head1, head2));
}
bool check(node* root){
if(root == nullptr)
return false;
node* n = root;
if(n->right < root)
return false;
else if(n->left > root)
return false;
else if(n->left > n->right)
return false;
return true;
int main() {
using std::cout;
using std::cin;
using std::stringstream;
string input, c;
string command;
string y, z;
string reg[1];
int values[1];
string mergetrees[2];
cout << "Type commands." << std::endl;
while(true){
cout << "> ";
std::getline(cin, input);
std::istringstream split_string(input);
split_string >> command;
node* r;
if(command.compare("clear") == 0){
split_string >> reg[0];
delete[] reg;
}
else if(command.compare("insert") == 0){
split_string >> values[0] >> reg[0];
c = reg[0];
node* c;
insert(c, values[0]);
}
else if(command.compare("remove") == 0){
split_string >> values[0] >> reg[0];
c = reg[0];
node* c;
remove(c, values[0]);
}
else if(command.compare("merge") == 0){
split_string >> mergetrees[0] >>mergetrees[1];
y = mergetrees[0];
z = mergetrees[1];
node* y;
node* z;
merge(y,z);
}
else if(command.compare("test") == 0){
split_string >> values[0] >> reg[0];
int testvalue = values[0];
c = reg[0];
node* c;
if(find(c, testvalue))
cout << "true" << std::endl;
else
cout << "false" << std::endl;
}
else if(command.compare("print") == 0){
split_string >> reg[0];
c = reg[0];
node* c;
//inorder print
inorder(c, [](node*& n) { cout << n-> key << " ";});
}
else
cout << "Wrong command" << std::endl;
}
}
------------------------------------------------
I've been getting trolled in the Q&A section for more than five times.
If you don't think you can fix this code to actually run properly, please skip my question.
I'm really desparate on expert-level help on this.
Thank you in advance!!
In this assignment you're going to implement splay trees, and then re-use some of your code from assignment 1 to create a tree register machine, a machine with four registers whose values are search trees. Part 1: AVL Trees Implement AVL trees (with parent pointers) Implement it as a binary search tree with integer keys (i.e., an ordered set). Your nodes should have type struct node int key; node* left. node right node parent; int height; Other members as needed by your tree implementation. Note that maintaining parent pointers complicates some of the algorithms I would suggest implementing the basic, unbalanced BST operations first, and then adding the parent pointers and making sure everything still works, and finally adding the balancing code You must implement the following tree operations.Explanation / Answer
Okay, firt of all apologies for the trouble you had to face with this question.
Coming to your problem, first of all please copy the below code to notepad++ for better viewing. I just finished reviewing your code. There seems to be a few changes to be made in the program for its working.
1. Please start commenting the code. Whenever you write functions, put a line or two above its definition stating its purpose. Some of your functions with names like spine and advance took a while for me to understand. Commenting at places should be kept in practise,
2. Considering now that you have copied the below code in your editor, let's start from the LOC : 48.If a node doesn't have a left subtree, then its predecessor is its parent node or NULL in case of root. This won't be covered in your code.
Try something like :
node*& pred(node*&root, node*& target, int key){
if(root==target && root->left==nullptr) //for the case when the target is root and it doesn't have a left subtree
return nullptr;
if(target -> left)
return largest(target -> left);
else
{
while(root->left!=target && root->right!=target) //find the parent node of target in case target doesn't have a left subtree.
{
if(root->data<key)
root=root->left;
else
root=root->right;
}
if(root->right=target) //root is the predecessor in this case
return root;
else if(root->left=target) //no predecessor
return nullptr;
}
}
and change the calling of this function at line : 69 also.
3. Coming to your remove function, check the comment at line 58 and 63. You are deleting the pointer pointing to your target node with no pointer to its parent thereby detatching the subtree rooted at the target pointer from the original tree. Infact since now you have defined a function to find the predecessor of a node including all the corner cases, you can simply write this :
void remove(node*& root, int key){
node* n = find(root, key);
if(n){
if(!n -> left && !n -> right){
delete n;
n = nullptr;
}
else{
node* k = pred(root, key); //pred(root, n, key)
std::swap(n -> key, k -> key);
remove(k, key);
}
}
4. Lastly, looking into your mergespines function, initially head is not assigned to any node. Hence last also is nullptr. assigning last->right=n won't in that case. Head will be smaller of the two heads (n1 and n2). Hence it will be like:
node* mergespines(node* n1, node* n2){
node *head; //it needs to be assigned to smallest of two starting nodes
if(n1->key<n2->key)
head=n1;
else
head=n2;
node* last = &head;
while(n1 || n2){
if(!n1)
advance(last, n2);
else if(!n2)
advance(last, n1);
else if(n1->right < n2->right)
advance(last, n1);
else if(n1->right > n2->right)
advance(last, n2);
else{
advance(last, n1);
n2 = n2 ->right;
}
}
}
That's all I would like to modify in the given code. Hope this one works as per your requirement.
Please find below your code with my comments.
#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <istream>
using std::string;
struct node {
int key;
node* right;
node* left;
node* parent;
int height;
};
// finding a node
node*& find(node*& root, int key){
if(root == nullptr)
return root;
else if(root->key == key)
return root;
else if(key > root->key)
return find(root->right, key);
else
return find(root->left, key);
}
//inserting a node
void insert(node*& root, int key){
node* n = find(root, key);
if(n == nullptr)
n = new node {key, nullptr, nullptr, nullptr, 1};
}
//finding the largest node
node*& largest(node*& root){
if(!root)
return root;
else if(!root->right)
return root;
else
return largest(root->right);
}
// Please check my code above for thie function
node*& pred(node*& target, int key){
if(target->left)
return largest(target -> left);
else
return largest(target -> right); //this is wrong. If a node doesn't have a left child, then this function will not work. In that case the predecessor is its parent.
}
//removing a node. This function needs certain modifications. Please check my code above
void remove(node*& root, int key){
node* n = find(root, key);
if(n){
if(!n -> left && !n -> right){
delete n;
n = nullptr;
}
if(!n -> right){ // n is the pointer to the node which needs to be deleted. Hence delete n will detatch the subtree rooted at n from the original tree
node* t = n -> left;
delete n;
n = t;
}
else if(!n -> left){ // // n is the pointer to the node which needs to be deleted. Hence delete n will detatch the subtree rooted at n from the original tree
node* t = n -> right;
delete n;
n = t;
}
else{
node* k = pred(root, key); //pred(root, n, key)
std::swap(n -> key, k -> key);
remove(k, key);
}
}
}
//Instead of using void print function, I chose to use this one below.
void inorder(node* root, std::function<void(node*&)> visit){
if(!root)
return;
if(root->left)
inorder(root->left, visit);
visit(root);
if(root->right)
inorder(root->right, visit);
}
//Converting the tree to a linkedlist
void spine(node* p, node*& prev, node*& head){
if(!p)
return;
spine(p->left, prev, head);
if(prev) prev->right = p;
else head = p;
prev = p;
p -> left = 0;
spine(p->right, prev, head);
}
//connecting the two lists
void advance(node*& last, node*& n){
last->right = n;
last = n;
n = n-> right;
}
//Merge the two lists.
node* mergespines(node* n1, node* n2){
node head;
node* last = &head; //head is not assigned to any of the list. Please check my code above
while(n1 || n2){
if(!n1)
advance(last, n2);
else if(!n2)
advance(last, n1);
else if(n1->right < n2->right)
advance(last, n1);
else if(n1->right > n2->right)
advance(last, n2);
else{
advance(last, n1);
n2 = n2 ->right;
}
}
return head.right;
}
//Merge the doubly linkedlist to make a balanced search tree
node* balance2(node*& list, int start, int end){
if(start > end)
return nullptr;
int mid = start + (end - start) / 2;
node *leftchild = balance2(list, start, mid-1);
node *parent = list;
parent-> left = leftchild;
list = list->right;
parent->right = balance2(list, mid+1, end);
return parent;
}
//Function to balance the two merged BSTs
node* balance(node *head){
int size = 0;
for(node* n = head; n; n = n ->right)
size++;
return balance2(head, 0, size-1);
}
//merge two Balanced BSTs
node* merge(node* t1, node* t2){
node *prev, *head1, *head2;
prev = head1 = 0;
spine(t1, prev, head1);
prev = head2 = 0;
spine(t2, prev, head2);
return balance(mergespines(head1, head2));
}
//What is the purpose of the below function? You haven't called this function anywhere.
//If it is to check if a tree is a BST or not, then it is the wrong logic.
bool check(node* root){
if(root == nullptr)
return false;
node* n = root;
if(n->right < root)
return false;
else if(n->left > root)
return false;
else if(n->left > n->right)
return false;
return true;
}
int main() {
using std::cout;
using std::cin;
using std::stringstream;
string input, c;
string command;
string y, z;
string reg[1];
int values[1];
string mergetrees[2];
cout << "Type commands." << std::endl;
while(true){
cout << "> ";
std::getline(cin, input);
std::istringstream split_string(input);
split_string >> command;
node* r;
if(command.compare("clear") == 0){
split_string >> reg[0];
delete[] reg;
}
else if(command.compare("insert") == 0){
split_string >> values[0] >> reg[0];
c = reg[0];
node* c;
insert(c, values[0]);
}
else if(command.compare("remove") == 0){
split_string >> values[0] >> reg[0];
c = reg[0];
node* c;
remove(c, values[0]);
}
else if(command.compare("merge") == 0){
split_string >> mergetrees[0] >>mergetrees[1];
y = mergetrees[0];
z = mergetrees[1];
node* y;
node* z;
merge(y,z);
}
else if(command.compare("test") == 0){
split_string >> values[0] >> reg[0];
int testvalue = values[0];
c = reg[0];
node* c;
if(find(c, testvalue))
cout << "true" << std::endl;
else
cout << "false" << std::endl;
}
else if(command.compare("print") == 0){
split_string >> reg[0];
c = reg[0];
node* c;
//inorder print
inorder(c, [](node*& n) { cout << n-> key << " ";});
}
else
cout << "Wrong command" << std::endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.