Wednesday, May 11, 2011

AVL Tree example c c++

Following code is another example of AVL Tree implementation in C++ language.
AVL Tree is a tree data structure whose height is always balanced by rotation tree nodes.

[AVL Tree example]


// Node.h 
#pragma once 
#define PURE =0 
#define null 0 
template <typename T> class Node 
{ 
protected: 
        T *value; 
 
        Node() 
        { 
                value = null; 
        } 
public: 
        Node(T *v) : value(v) 
        { 
        } 
         
        virtual ~Node() 
        { 
                if(value != null) 
                { 
                        delete value; 
                        value = null; 
                } 
        } 
 
public: 
        virtual Node<T> *Insert(Node<T> *n) PURE;        
        virtual Node<T> *Delete() PURE;                          
        virtual Node<T> *Search(T *v) PURE;                      
        virtual void PrintValue() PURE;                          
}; 

// AVL.h 
#pragma once   
  
#define null 0   
 
template <typename T> class AVL_Node : public Node<T> 
{    
protected:    
        AVL_Node<T> *parent;    
        AVL_Node<T> *leftChild;    
        AVL_Node<T> *rightChild;    
        int balanceFactor;   
 
        bool rightRotation() 
        {   
                AVL_Node* child = rightChild, *grandChild = null;   
 
                if(child->balanceFactor == 1)    
                {   
                        //cout << "RL rotation" << endl; 
                        grandChild = child->leftChild;  
 
                        child->leftChild = grandChild->rightChild;   
                        if(grandChild->rightChild != null)   
                                grandChild->rightChild->parent = child;   
 
                        this->rightChild = grandChild->leftChild;   
                        if(grandChild->leftChild != null)   
                                grandChild->leftChild->parent = this;   
 
                        replaceParent(this, grandChild);  
 
                        grandChild->rightChild = child;   
                        grandChild->leftChild = this;   
                        child->parent = grandChild;   
                        this->parent = grandChild;   
 
                        switch(grandChild->balanceFactor) 
                        { 
                        case -1: 
                                this->balanceFactor = 1; 
                                child->balanceFactor = 0; 
                                break; 
                        case 1: 
                                this->balanceFactor = 0; 
                                child->balanceFactor = -1; 
                                break; 
                        case 0: 
                                this->balanceFactor = 0; 
                                child->balanceFactor = 0; 
                                break; 
                        } 
                        grandChild->balanceFactor =0; 
                }   
                else  
                { 
                        //cout << "RR rotation" << endl; 
                        this->rightChild = child->leftChild;   
                        if(child->leftChild != null)   
                                child->leftChild->parent = this;   
 
                        child->leftChild = this;   
                        replaceParent(this, child);  
                        this->parent = child;   
 
                        if(child->balanceFactor == -1) 
                        {    
                                this->balanceFactor = 0;   
                                child->balanceFactor = 0;   
                        }  
                        else    
                        {    
                                this->balanceFactor = -1;   
                                child->balanceFactor = 1;   
 
                                return false; 
                        } 
                }        
                 
                return true;  
        }   
 
        bool replaceParent(AVL_Node<T> *current, AVL_Node<T> *replace)  
        {  
                bool returnValue = false;  
 
                if(replace!=null)  
                        replace->parent = current->parent;  
 
                if(current->parent != null)   
                {   
                        if(current->parent->leftChild == current)  
                        {  
                                returnValue = true;  
                                current->parent->leftChild = replace;    
                        }  
                        else 
                                current->parent->rightChild = replace;  
                }  
 
                return returnValue;  
        }  
 
 
        void replaceChild(AVL_Node<T> *current, AVL_Node<T> *replace)  
        {  
                replace->leftChild = current->leftChild;  
                if(replace->leftChild != null)  
                        replace->leftChild->parent = replace;  
 
                replace->rightChild = current->rightChild;  
                if(replace->rightChild != null)  
                        replace->rightChild->parent = replace;  
        }   
 
        bool leftRotation()   
        {   
                AVL_Node* child = leftChild, *grandChild = null;   
 
                if(child->balanceFactor == -1)    
                {   
                        //cout << "LR Rotation" << endl; 
                        grandChild = child->rightChild;   
 
                        child->rightChild = grandChild->leftChild;   
                        if(grandChild->leftChild != null)   
                                grandChild->leftChild->parent = child;   
 
                        this->leftChild = grandChild->rightChild;   
                        if(grandChild->rightChild != null)   
                                grandChild->rightChild->parent = this;   
 
                        replaceParent(this, grandChild);   
 
                        grandChild->leftChild = child;   
                        grandChild->rightChild = this;   
                        child->parent = grandChild;   
                        this->parent = grandChild;   
 
                        switch(grandChild->balanceFactor) 
                        { 
                        case -1: 
                                this->balanceFactor = 0; 
                                child->balanceFactor = 1; 
                                break; 
                        case 1: 
                                this->balanceFactor = -1; 
                                child->balanceFactor = 0; 
                                break; 
                        case 0: 
                                this->balanceFactor = 0; 
                                child->balanceFactor = 0; 
                                break; 
                        } 
                        grandChild->balanceFactor =0; 
                }   
                else 
                { 
                        //cout << "LL rotation" << endl; 
                        this->leftChild = child->rightChild;   
                        if(child->rightChild != null)   
                                child->rightChild->parent = this;   
 
                        child->rightChild = this;   
                        replaceParent(this, child);  
                        this->parent = child;   
                         
                        if(child->balanceFactor == 1)  
                        {    
                                this->balanceFactor = 0;   
                                child->balanceFactor = 0;   
                        }   
                        else if(child->balanceFactor == 0)    
                        { 
                                this->balanceFactor = 1;   
                                child->balanceFactor = -1;   
                                return false; 
                        } 
                } 
                 
                return true;  
        }   
 
        void rearrangeBF(AVL_Node* unbalance, bool isLeft)  
        {  
                if(unbalance == null)  
                        return;  
 
                bool bLoop = true;  
 
                do  
                {  
                        if(isLeft)  
                        {  
                                switch(unbalance->balanceFactor)  
                                {  
                                case 0:  
                                        unbalance->balanceFactor = -1;  
                                        bLoop = false;  
                                        break;  
                                case 1:  
                                        unbalance->balanceFactor = 0;  
                                        break;  
                                case -1:  
                                        bLoop = unbalance->rightRotation();  
                                        unbalance=unbalance->parent; // 회전후 가장 꼭대기로부터 다시 수행  
                                        break;  
                                }  
                        }  
                        else  
                        {  
                                switch(unbalance->balanceFactor)  
                                {  
                                case 0:  
                                        unbalance->balanceFactor = 1;  
                                        bLoop = false;  
                                        break;  
                                case -1:  
                                        unbalance->balanceFactor = 0;  
                                        break;  
                                case 1:  
                                        bLoop = unbalance->leftRotation();  
                                        unbalance=unbalance->parent;  
                                        break;  
                                }  
                        }  
 
                        if(unbalance->parent == null)  
                                return;  
                      
                        isLeft = (unbalance->parent->leftChild == unbalance);  
                        unbalance = unbalance->parent;  
                }   
                while(bLoop && unbalance != null);  
        }  
 
        bool InsertChild(AVL_Node<T> *n)    
        {    
                if(n == null)    
                        return false;    
 
                if(*value == *n->value)    
                        return false;    
 
                else if(*n->value < *value)    
                {    
                        if(leftChild == null)    
                        {   
                                leftChild = n;    
                                n->parent = this;    
                                return (++balanceFactor==0?false:true);   
                        }   
                        else if(leftChild->InsertChild(n) == true)   
                        {   
                                switch(this->balanceFactor)   
                                {   
                                case -1:   
                                        this->balanceFactor = 0;   
                                        return false;   
                                case 0:   
                                        this->balanceFactor = 1;   
                                        return true;   
                                case 1:   
                                        leftRotation();   
                                        return false;   
                                }   
                        }   
                }    
                else if(*n->value > *value)    
                {    
                        if(rightChild == null)    
                        {   
                                rightChild = n;    
                                n->parent = this;    
                                return (--balanceFactor==0?false:true);   
                        }   
                        else if(rightChild->InsertChild(n) == true)   
                        {   
                                switch(this->balanceFactor)   
                                {   
                                case 1:   
                                        this->balanceFactor = 0;   
                                        return false;   
                                case 0:   
                                        this->balanceFactor = -1;   
                                        return true;   
                                case -1:   
                                        rightRotation();   
                                        return false;   
                                }   
                        }   
                }    
 
                return false;   
        }    
 
        virtual AVL_Node<T>* Insert(Node<T> *n)    
        {    
                InsertChild(dynamic_cast<AVL_Node<T>*>(n));    
                return FindRoot();  
        }  
 
public:    
        AVL_Node(T* input) : Node(input), balanceFactor(0), parent(null), leftChild(null), rightChild(null)   
        {    
        }    
 
 
        virtual ~AVL_Node()    
        {    
        }  
 
 
        AVL_Node<T>* Insert(T &input)    
        {    
                return Insert(&input);  
        }  
 
        AVL_Node<T>* Insert(T *input)    
        {    
                AVL_Node<T>* root = FindRoot();  
                if(root->Search(input) == null)  
                        return root->Insert(new AVL_Node<T>(input));  
                else  
                        return root;  
        }  
 
        AVL_Node<T>* Search(T &input)  
        {  
                 return Search(&input);  
        }  
 
        virtual AVL_Node<T>* Search(T *input)    
        {  
                if(value == null || input == null)  
                        return null;  
 
                AVL_Node<T> *current = this; 
 
                do 
                { 
                        if(*current->value == *input)    
                                return current; 
                        else if(*input < *current->value)    
                                current = current->leftChild; 
                        else if(*input > *current->value)    
                                current = current->rightChild; 
                        else 
                                current = null; 
                }while(current != null); 
 
                return null; 
        }  
 
        AVL_Node<T>* FindRoot()    
        {    
                AVL_Node<T> *root=this;    
                while(root->parent != null)    
                        root = root->parent;    
                return root;    
        }    
 
          
        virtual AVL_Node<T>* Delete()    
        {    
                AVL_Node<T> *unbalance = null;    
                bool isLeft = false;  
 
                AVL_Node<T> *root = null;    
                AVL_Node<T> *replace = null;    
 
                
                if(this->balanceFactor != -1 && this->leftChild != null)    
                {    
                       
                        replace = this->leftChild;    
                        while(replace->rightChild != null)    
                                replace = replace->rightChild;    
 
                        
                        isLeft = replaceParent(replace, replace->leftChild);  
                }    
                else if(this->rightChild != null)    
                {    
                        replace = this->rightChild;    
                        while(replace->leftChild != null)    
                                replace = replace->leftChild;    
 
                        isLeft = replaceParent(replace, replace->rightChild);  
                }    
                else  
                {    
                        if(this->parent != null)   
                        {    
                                AVL_Node<T> *temp = this->parent;  
                                isLeft = replaceParent(this, null);  
                      
                                 
                                rearrangeBF(temp, isLeft);  
 
                                root = temp->FindRoot();    
                        }  
 
                        delete this;    
                        return root;    
                }    
 
                 
                replace->balanceFactor = this->balanceFactor;  
 
                
                if(replace->parent == this)  
                        unbalance = replace;  
                else  
                        unbalance = replace->parent;  
 
                 
                replaceParent(this, replace);  
                replaceChild(this, replace);  
 
                
                rearrangeBF(unbalance, isLeft);  
                root = replace->FindRoot();  
 
                delete this;  
                return root;  
        }  
 
 
        AVL_Node<T>* Delete(T &input)    
        {    
                return Delete(&input);  
        }   
 
        AVL_Node<T>* Delete(T *input)    
        {    
                AVL_Node<T> *temp = Search(input); 
 
                if(temp != null)    
                        return temp->Delete(); 
                return this->FindRoot(); 
        }    
 
        AVL_Node<T>* DeleteAll()    
        {  
                AVL_Node<T> *root = FindRoot();    
                while(root!=null)    
                        root = root->Delete();   
                return root;    
        }  
 
 
        virtual void PrintValue()  
        {    
                cout << *value << "(" << balanceFactor <<") ";    
        }  
 
        void InorderTraversal()    
        {    
                if(this->leftChild != null)    
                {   
                        //gotoline(1);  
                        cout << "L";  
                        this->leftChild->InorderTraversal();    
                        //gotoline(-1);  
                }  
              
                 
                this->PrintValue();    
 
                if(this->rightChild != null)    
                {   
                        //gotoline(1);  
                        cout << "R";  
                        this->rightChild->InorderTraversal();    
                        //gotoline(-1);  
                }  
        }  
 
        void PreorderTraversal()    
        {    
                this->PrintValue();    
 
                if(this->leftChild != null)    
                        this->leftChild->PreorderTraversal();    
 
                if(this->rightChild != null)    
                        this->rightChild->PreorderTraversal();    
        }  
 
        void PostorderTraversal()    
        {    
                if(this->leftChild != null)    
                        this->leftChild->PostorderTraversal();    
 
                if(this->rightChild != null)    
                        this->rightChild->PostorderTraversal();    
 
                this->PrintValue();    
        }  
};