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.

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

#include

#include

#include

#include

#include

#include

#include

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 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 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

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

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

else

cout

}

else if(command.compare("print") == 0){

split_string >> reg[0];

c = reg[0];

node* c;

//inorder print

inorder(c, [](node*& n) { cout key

}

else

cout

}

}

------------------------------------------------

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. 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