AVL TREE

avl.cpp

#include"avl.h" 
#include<algorithm> 

namespace Tree{ 

    // constructor 
    AVLTree::AVLTree( void ){ } 
    // destructor 
    AVLTree::~AVLTree( void ){
        this->TreeDestory( this->root ); 
    } 

    void AVLTree::TreeDestory( TreeNode *tree ){ 
        if( tree != NULL ){ 
            this->TreeDestory( tree->llink ); 
            this->TreeDestory( tree->rlink ); 
            delete tree; 
        } 
    } 

    // member function 
    void AVLTree::insertNode( int val ){ 

        TreeNode *newNode = new TreeNode; 

        if( this->root == NULL ){ 
            newNode->val = val; 
            newNode->llink = newNode->rlink = newNode->plink = NULL; 
            std::cout << "Data has been added to AVL Tree, AVL initialized\n\n"; 
            this->root = newNode; 
        }else{ 
            if( NULL != this->search( this->root, val ) ){ 
                std::cout << "Data exist!!" << std::endl; 
                return; 
            }else{ 

                newNode->val = val; 
                newNode->rlink = newNode->llink = NULL; 
                if( this->preNode->val > val ) this->preNode->llink = newNode; 
                else this->preNode->rlink = newNode; 
                newNode->plink = this->preNode; 
                std::cout << "Data has been added to AVL Tree\n\n"; 
            }
        }

        this->calBal( this->root ); 
        this->checkInsert( newNode, val ); 

    } 

    AVLTree::TreeNode *AVLTree::search( TreeNode *tree, int target ){  

        if( tree == NULL ) return NULL; 

        this->preNode = tree; 

        if( tree->val > target ) 
            return this->search( tree->llink, target ); 
        else if( tree->val < target ) 
            return this->search( tree->rlink, target ); 
        return tree;  
    } 

    void AVLTree::checkInsert( TreeNode *newNode, int key ){ 
        
        //TreeNode *pivot = this->findPivot( newNode ); 
        TreeNode *pivot = newNode;  
        if( pivot == NULL ) return; // all nodes are valid. 
        
        if( pivot->balance > 1 && key < (pivot->llink->val) ){ // LL
            std::cout << "DEBUG: LL\n"; 
            this->RightRotation( pivot ); 
        }else if( pivot->balance > 1 && key > (pivot->llink->val) ){ // LR 
            std::cout << "DEBUG: LR\n"; 
            this->LeftRightRotation( pivot ); 
        }else if( pivot->balance < -1 && key < (pivot->rlink->val) ) { // RL  
            std::cout << "DEBUG: RL\n"; 
            this->RightLeftRotation( pivot ); 
        }else if( pivot->balance < -1 && key > (pivot->rlink->val) ) { // RR  
            std::cout << "DEBUG: RR\n"; 
            this->LeftRotation( pivot ); 
        } 

        std::cout << "DEBUG: AFTER ROTATION\n"; 
        std::cout << "root->val = " << this->root->val << std::endl; 
        this->calBal( pivot ); 
        std::cout << "DEBUG: AFTER calBaHeight\n"; 
        this->checkInsert( pivot->plink, key ); 

    } 

    void AVLTree::deleteNode( int val ){ 
        
        if( this->root == NULL ){ 
            std::cout << "Tree has not be initialized!\n\n";  
            return; 
        } 

        if( this->search( this->root, val ) != NULL ){   
            this->deleteNode( this->root, val ); 
        }else{ 
            std::cout << "The data you input is not exist!!.\n"; 
        } 

    } 

    AVLTree::TreeNode *AVLTree::deleteNode( TreeNode *tree, int val ){ 
        if( tree->val > val ) 
            tree->llink = this->deleteNode( tree->llink, val ); 
        else if( tree->val < val ) 
            tree->rlink = this->deleteNode( tree->rlink, val ); 
        else{ 

            if( tree->llink == NULL && tree->rlink == NULL ){ 
                TreeNode *tmp = new TreeNode; 
                tmp = tree; 
                tree = NULL;
                delete tmp; 
            }else if( tree->llink == NULL ){ 
                tree = tree->rlink; 
            }else if( tree->rlink == NULL ){ 
                tree = tree->llink; 
            }else{ 
                TreeNode *tmpNode = this->findMin( tree->rlink ); 
                tree->val = tmpNode->val;  
                tree->rlink = this->deleteNode( tree->rlink, tmpNode->val ); 
            } 

        }

        this->calBal( tree ); 
        tree = this->checkDelete( tree ); 
        return tree; 
    }

    AVLTree::TreeNode *AVLTree::findMin( TreeNode *tree ){ 
        if( tree->llink == NULL ) return tree; 
        return this->findMin( tree->llink ); 
    }

    AVLTree::TreeNode *AVLTree::checkDelete( TreeNode *tree ){ 

        if(tree!=NULL) std::cout<<"DEBUG: In checkDelete, tree->val = " << tree->val << std::endl; 
        if( tree != NULL ){  
            if( tree->balance > 1 && tree->llink->balance >= 0 ){ // LL 
                std::cout << "DEBUG: LL\n"; 
                tree = RightRotation( tree ); 
            }else if( tree->balance > 1 && tree->llink->balance < 0 ){ // LR 
                std::cout << "DEBUG: LR\n"; 
                tree = LeftRightRotation( tree ); 
            }else if( tree->balance < -1 && tree->rlink->balance >= 0 ){ //RL 
                std::cout << "DEBUG: RL\n"; 
                tree = RightLeftRotation( tree ); 
            }else if( tree->balance < -1 && tree->rlink->balance < 0 ){ // RR 
                std::cout << "DEBUG: RR\n"; 
                tree = RightRotation( tree ); 
            } 
        } 
        std::cout << "DEBUG" << std::endl; 
        this->calBal( this->root ); 
        return tree; 

    } 

    void AVLTree::calBal( TreeNode *tree ){ 
        if( tree != NULL ){ 
            this->calBal( tree->llink ); 
            this->calBal( tree->rlink ); 
            tree->balance = this->calHeight( tree->llink ) - this->calHeight( tree->rlink ); 
        } 
    } 


    int AVLTree::calHeight( TreeNode *tree ){ 
        if( tree == NULL ) return -1; 
        return std::max( this->calHeight( tree->llink ), this->calHeight( tree->rlink ) ) + 1; 
    }

    AVLTree::TreeNode *AVLTree::findPivot( TreeNode *tree ){ 

        if( tree != NULL ){ 
            if( tree->balance == 2 || tree->balance == -2 )  
                return tree; 
            return this->findPivot( tree->plink ); 
        } 
        return NULL; 

    }

    AVLTree::TreeNode *AVLTree::LeftRotation( TreeNode *tree ){ 

        TreeNode *tmpSubRightLeft = tree->rlink->llink; 

        if( tree->plink == NULL ){ 
            this->root = tree->rlink; 
            tree->rlink->plink = NULL; 
        }else{  
            tree->rlink->plink = tree->plink; 
            if( tree->val < tree->plink->val ) // left rotation for LR 
                tree->plink->llink = tree->rlink; 
            else // left rotation for LL  
                tree->plink->rlink = tree->rlink; 
        } 
        tree->plink = tree->rlink;  
        tree->rlink->llink = tree; 
        tree->rlink = tmpSubRightLeft; 
        return tree->plink; 
    }

    AVLTree::TreeNode *AVLTree::RightRotation( TreeNode *tree ){ 

        TreeNode *tmpSubLeftRight = tree->llink->rlink; 

        if( tree->plink == NULL ){ 
            this->root = tree->llink; 
            tree->llink->plink = NULL; 
        }else{  
            tree->llink->plink = tree->plink;  
            if( tree->val > tree->plink->val ) // right rotation for RL 
                tree->plink->rlink = tree->llink; 
            else // right rotation for RR  
                tree->plink->llink = tree->llink; 
        } 
        tree->plink = tree->llink;  
        tree->llink->rlink = tree;
        tree->llink = tmpSubLeftRight; 
        return tree->plink; 
    } 

    AVLTree::TreeNode *AVLTree::LeftRightRotation( TreeNode *tree ){ 
        tree->llink = this->LeftRotation( tree->llink ); 
        tree = this->RightRotation( tree ); 
        return tree; 
    }

    AVLTree::TreeNode *AVLTree::RightLeftRotation( TreeNode *tree ){ 
        tree->rlink = this->RightRotation( tree->rlink ); 
        tree = this->LeftRotation( tree ); 
        return tree; 
    } 

    void AVLTree::inorder( void ){ 
        this->inorder( this->root ); 
        std::cout << "\n";  
    }

    void AVLTree::inorder( TreeNode *tree ){ 
        using std::cout; 
        using std::endl; 
        if( tree != NULL ){ 
            this->inorder( tree->llink ); 
            cout << tree->val << " ";  
            cout << ", balance " << tree->balance << endl; 
            this->inorder( tree->rlink ); 
        } 
    }


} 

avl.h

#ifndef AVL_TREE_ 
#define AVL_TREE_ 

#include<iostream> 
#include<cstdlib> 
#include<cstring> 

namespace Tree{ 
    class AVLTree{ 

        private: 
            struct TreeNode{ 
                int val; 
                int balance; 
                TreeNode *llink, *rlink, *plink; 
            }; 
            TreeNode *root = NULL; 
            TreeNode *preNode = NULL; 
            TreeNode *curNode = NULL; 
            void inorder( TreeNode *tree ); 
            TreeNode *deleteNode( TreeNode *tree, int val ); 

        public: 
            /* constructor */ 
            AVLTree(void); 
            /* destructor */ 
            ~AVLTree(void); 
            void TreeDestory( TreeNode *tree );  

            /* member functions */ 
            void insertNode( int val ); 
            void deleteNode( int val ); 
            TreeNode *findMin( TreeNode *tree );  
            TreeNode *search( TreeNode *tree, int target ); 
            void checkInsert( TreeNode *tree, int key ); 
            AVLTree::TreeNode *checkDelete( TreeNode *tree ); 
            int calHeight( TreeNode *tree ); 
            void calBal( TreeNode *tree ); 
            AVLTree::TreeNode *findPivot( TreeNode *tree );  
            AVLTree::TreeNode *LeftRotation( TreeNode *tree ); 
            AVLTree::TreeNode *RightRotation( TreeNode *tree ); 
            AVLTree::TreeNode *LeftRightRotation( TreeNode *tree ); 
            AVLTree::TreeNode *RightLeftRotation( TreeNode *tree ); 
            void inorder( void ); 


            // void findPtr( void ); 
            // int findType( TreeNode *pivot ); 
            // friend std::ostream &operator<<( std::ostream &os, const AVLTree &t ); 
 
    }; 
} 

#endif 

main.cpp

#include"avl.h" 

void print(void);  

int main(void){ 

    using Tree::AVLTree; 
    using std::cout; 
    using std::cin; 
    using std::endl; 

    AVLTree *avltree = new AVLTree(); 
    int val, option; 
    
    print(); 
    cin >> option; 
    while( option != 0 ){ 

        switch( option ){ 
            case 1: 
                cout << ">> "; 
                cin >> val; 
                avltree->insertNode( val ); 
                break; 
            case 2: 
                cout << ">> "; 
                cin >> val; 
                avltree->deleteNode( val ); 
                break; 
            case 3: 
                avltree->inorder(); 
                break; 
            default: 
                cout << "Error options." << endl; 
                break; 
        }

        print(); 
        cin >> option; 
    }

    delete avltree; 

    return 0; 
}

void print(void){ 
    using std::cout; 
    using std::endl; 

    cout << endl; 
    cout << "1. add a int: " << endl; 
    cout << "2. delete a int: " << endl; 
    cout << "3. inorder: " << endl; 
    cout << "press 0 to end.\n>> "; 
}