ShujaatMirza - 2 years ago
524 0

No description

C++

# Assignment9-Problem1-AVLinsert&remove

``````#include <iostream>
using namespace std;

template <typename S>
class Node{
public:
S key;
int height;
Node<S> *left, *right, *parent;
};

template <typename T>
class BST{
private:
Node<T> *root;

void destroy(Node<T> *ptr);
Node<T>* findMin(Node<T> *ptr);
void insert2(Node<T>*ptr, T key);
Node<T>* find2(Node<T>* ptr, T key);
void printPreorder2(Node<T> *ptr);
void printInorder2(Node<T> *ptr);
void printTree2(T *A, bool *B, Node<T> *ptr, int n);
Node<T>* newnode(T key);
void remove2(Node<T> *ptr);
int depth2(Node<T>* ptr);
void AVLinsert2(Node<T> *inserted, Node<T> *toproot);

public:
BST();
~BST();
void insert(T key);
void remove(T key);
Node<T>* find(T key);
void printPreorder();
void printInorder();
void printTree();
int depth(Node<T>* ptr);
void rotate(Node<T> *parent, Node<T>* child);
void AVLinsert(T key);
int height(Node<T> *node);
};

template <typename T>
BST<T>::BST(){
root = nullptr;
}

template <typename T>
void BST<T>::destroy(Node<T>* ptr){
if(ptr != nullptr){
destroy(ptr->left);
destroy(ptr->right);
delete ptr;
}
}

template <typename T>
BST<T>::~BST(){
destroy(root);
}
template <typename T>
int BST<T>::height(Node<T> *node){
if( node==nullptr)
return -1;
else{
return 1 + max(height(node->left),height(node->right));
}
}

template <typename T>
int BST<T>::depth2(Node<T>* ptr){
int l, r;
if(ptr==nullptr) return -1;
l = depth2(ptr->left);
r = depth2(ptr->right);
if(l>r) return l+1;
return r+1;
}

template <typename T>
int BST<T>::depth(Node<T>* ptr){
return depth2(ptr);
}

template <typename T>
void BST<T>::printTree2(T *A, bool *B, Node<T> *ptr, int n){
if(ptr!=nullptr){
int mid = (n-1)/2;
A[mid] = ptr->key;
B[mid] = true;
printTree2(A,B,ptr->left,mid);
printTree2(A+(mid+1), B+(mid+1), ptr->right, mid);
}
}

template <typename T>
void BST<T>::printTree(){
char *space = "  ";
int d = depth(root);
int n = (1<<(d+1))- 1; // n = 2^(d+1)-1

T *A = new T[n];
bool *B = new bool[n];
for(int i=0; i<n; ++i) B[i]=false;

printTree2(A,B,root,n);

cout<<"\nTree:"<<endl;
for(int t=(n+1)/2; t>0; t=t/2){
for(int j=0; j<n; j++){
if( ((j+1)%t == 0) && B[j]){
cout<<A[j];
B[j] = false;
}
else{
cout<<space;
}
}
cout<<endl;
}
cout<<endl;
delete [] A;
delete [] B;
}

template <typename T>
void BST<T>::printPreorder2(Node<T>* ptr){
if(ptr!=nullptr){
cout<<ptr->key<<" ";
printPreorder2(ptr->left);
printPreorder2(ptr->right);
}
}

template <typename T>
void BST<T>::printPreorder(){
cout<<"Preorder: ";
printPreorder2(root);
cout<<endl;
}

template <typename T>
void BST<T>::printInorder2(Node<T>* ptr){
if(ptr!=nullptr){
printInorder2(ptr->left);
cout<<ptr->key<<" ";
printInorder2(ptr->right);
}
}

template <typename T>
void BST<T>::printInorder(){
cout<<"Inorder: ";
printInorder2(root);
cout<<endl;
}

template <typename T>
Node<T>* BST<T>::find2(Node<T> *ptr, T key){
if(ptr==nullptr) return nullptr;
if(key < ptr->key) return find2(ptr->left, key);
if(key > ptr->key) return find2(ptr->right, key);
return ptr;
}

template <typename T>
Node<T>* BST<T>::find(T key){
return find2(root, key);
}
template <typename T>
Node<T>* BST<T>::newnode(T key){
Node<T>* n = new Node<T>;
n->key = key;
n->left = n->right = nullptr;
n->height=0;
return n;
}

template <typename T>
void BST<T>::insert2(Node<T> *ptr, T key){

// assumes ptr!=nullptr
Node<T> *n;
if(key<ptr->key){
if(ptr->left == nullptr){
n = newnode(key);
n->parent = ptr;
ptr->left = n;
n->height=height(n);
}
else{
insert2(ptr->left, key);
}
}
else{// key >= ptr->data
if(ptr->right == nullptr){
n = newnode(key);
n->parent = ptr;
ptr->right = n;
n->height=height(n);
}
else{
insert2(ptr->right, key);
}
}

}

template <typename T>
void BST<T>::insert(T key){
if(root == nullptr){
root = newnode(key);
root->parent = nullptr;
}
else{
insert2(root, key);
}

Node<T>* current;
current = find(key);
current=current->parent;
while (current!=nullptr) {
if(current->parent!=nullptr){
if(current->height==current->parent->height){
current->height+=1;
current = current->parent;
}
}
}
}

template <typename T>
Node<T>* BST<T>::findMin(Node<T> *ptr){
Node<T> *p;
for(p = ptr; ptr!=nullptr; ptr=ptr->left){
p = ptr;
}
return p;
}

template <typename T>
void BST<T>::remove2(Node<T>* ptr){

Node<T> *parent, *succ, **pp;

if(ptr==nullptr) return;

parent = ptr->parent;

if(ptr == root){// i.e. parent == nullptr
pp = &root;
}
else{
if(ptr==parent->left){
pp = &(parent->left);
}
else{
pp = &(parent->right);
}
}

if(ptr->left==nullptr && ptr->right==nullptr){
*pp = nullptr;
delete ptr;
}
else if(ptr->left==nullptr){
*pp = ptr->right;
ptr->right->parent = parent;
delete ptr;
}
else if(ptr->right==nullptr){
*pp = ptr->left;
ptr->left->parent = parent;
delete ptr;
}
else{
succ = findMin(ptr->right);
ptr->key = succ->key;
remove2(succ);
}
}

template <typename T>
void BST<T>::remove(T key){
remove2(find(key));
}

template <typename T>
void BST<T>::rotate(Node<T> *parent, Node<T>* child){
// assumes parent and child are not nullptr
if (parent!=nullptr && child != nullptr){
Node<T> **pc, **pb;
Node<T> *grandparent;

grandparent = parent->parent;
child->parent = grandparent;
parent->parent = child;

if(grandparent == nullptr){ //i.e. root == parent
root = child;
}
if(grandparent != nullptr){
if(parent == grandparent->left){
grandparent->left = child;
}
else{// parent == grandparent->right
grandparent->right = child;
}
}

if(child == parent->left){
pc = &(parent->left);
pb = &(child->right);
}
else{// child == parent->right
pc = &(parent->right);
pb = &(child->left);
}

*pc = *pb;
if((*pc) != nullptr){
(*pc)->parent = parent;
}
*pb = parent;
}

}

template <typename T>
void BST<T>::AVLinsert2(Node<T> *inserted, Node<T> *toproot){
Node<T> *current;
current=inserted;
int r, l;
while (current!=nullptr) {
if(current->right != nullptr)
r = current->right->height;
else{
r =-1;
}
if(current->left != nullptr)
l = current->left->height;
else{
l =-1;
}
int diff = r-l;
//cout<<"r"<<r<<"l"<<l;
if (diff<-1 || diff >1){
cout<<"We need to rotate";
if(r>l){
if((current->right) !=nullptr){
cout<<"Let's go";
if(current->right->right){
cout<<"here you go";
rotate(current, current->right);
}else{
cout<<"There you go";
rotate(current->right, (current->right)->left);
rotate(current, current->right);
}
}
}else{
if(current->left!=nullptr){
cout<<"Let's not go";
if(current->left->right){
cout<<"here you not go";
rotate(current->left, (current->left)->right);
rotate(current, current->left);
}else{
cout<<"There you not go";
rotate(current, current->left);
}
}
}
}
current=current->parent;
}
}

template <typename T>
void BST<T>::AVLinsert(T key){
insert(key);
Node<T>* f;
f= find(key);
AVLinsert2(f, root);
}

int main()
{
int ins[] ={2,4,3,-1,8,7,3,6,9};
int n_ins = sizeof(ins)/sizeof(int);
BST<int> B;

// Check insert
cout<<"Inserts: ";
for(int i=0; i<n_ins; ++i){
B.insert(ins[i]);
B.printTree();
cout<<"height"<<B.find(ins[i])->height;

}
cout<<"height"<<B.find(2)->height;
cout<<"height"<<B.find(7)->height;
cout<<endl;

/*int rem[] = {10, 2,5,3,-1,-2, 4,6,7,8,15,9,11};
int n_rem = sizeof(rem)/sizeof(int);

BST<int> B;

// Check insert
cout<<"Inserts: ";
for(int i=0; i<n_ins; ++i){
B.AVLinsert(ins[i]);
B.printTree();
cout<<ins[i]<<" ";
}
cout<<endl;
B.printTree();

//check rotate
Node<int> *f;
f= B.find(8);
B.rotate(f, f->left);
B.printTree();

f = B.find(4);
B.rotate(f, f->right);
B.printTree();

//check remove
for(int i=0;i<n_rem; ++i){
cout<<"Remove "<<rem[i]<<".\n";
B.remove(rem[i]);
B.printTree();

}*/

cout<<endl<<endl;
return 0;
}``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download