ShujaatMirza ShujaatMirza - 7 months ago
250 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;
    cout<<"Right rotate about 8."<<endl;
    f= B.find(8);
    B.rotate(f, f->left);
    B.printTree();
    
    cout<<"Left rotate about 4."<<endl;
    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;
}