C++ Balanced Binary Search Tree Hello there, I have to make a program regarding
ID: 3840683 • Letter: C
Question
C++ Balanced Binary Search Tree
Hello there, I have to make a program regarding to binary search tree in C++ and I need you to fix my code which it is not yet completed.
My tree implementation doesn't do any of the rebalancing/rotations needed after an insert or delete to preserve the AVL height-balance property. << this is what im supposed to fix.
If you copy my code and try running it, it compiles without errors but does not actually do anything. (it only gives segmentation fault)
I'm attaching the original prompt for the program so you can understand what I was actually trying to do.
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
i make changes to the program and re run it:
program:
#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;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.