Data structures: Binary search tree (AVL-tree)

#ifndef AVL_TREE 
#define AVL_TREE

int const UNBALANCED_LEFT=-1;
int const UNBALANCED_RIGHT=1;
int const BALANCED=0;

template<class ItemType>

typedef struct avl_tree
{
    ItemType Item;
    avl_tree *rightChild;
    avl_tree *leftChild;

    int balance_factor; // recreate to enumerator

    avl_tree()
    {
        rightChild=NULL;
        leftChild=NULL;
        balance_factor=BALANCED;
    };

} *avl_tree_node;

void single_right_rotation(avl_tree_node &current_tree)
{
    avl_tree_node lc;   
    
    lc=current_tree->leftChild;
    
    lc->balance_factor=BALANCED;
    current_tree->balance_factor=BALANCED;

    current_tree->leftChild=lc->rightChild;
    lc->rightChild=current_tree;
    
    current_tree=lc;
};   

void double_right_rotation(avl_tree_node &current_tree)
{
   avl_tree_node lc;
   avl_tree_node rg;
    
   lc=current_tree->leftChild;
   rg=lc->rightChild;
    
   if (rg->balance_factor==UNBALANCED_RIGHT)
   {
      current_tree->balance_factor = BALANCED;
      lc->balance_factor=UNBALANCED_LEFT;
   }
   else if (rg->balance_factor==BALANCED)
   {
      current_tree->balance_factor=BALANCED;  
      lc->balance_factor=BALANCED;
   }
   else
   {
      current_tree->balance_factor=UNBALANCED_RIGHT;  
      lc->balance_factor=BALANCED;
   }

   rg->balance_factor=BALANCED;
   
   lc->rightChild=rg->leftChild;
   rg->leftChild=lc;
   current_tree->leftChild=rg->rightChild;
   rg->rightChild=current_tree;

   current_tree=rg;
 };

void single_left_rotation(avl_tree_node &current_tree)
{
    avl_tree_node rc=current_tree->rightChild;

    rc->balance_factor=BALANCED;
    current_tree->balance_factor=BALANCED;

    current_tree->rightChild=rc->leftChild;
    rc->leftChild=current_tree;

    current_tree=rc;
};

void double_left_rotation(avl_tree_node &current_tree)
{
    avl_tree_node rc;
    avl_tree_node lg;

    rc=current_tree->rightChild;
    lg=rc->leftChild;

    if (lg->balance_factor==UNBALANCED_LEFT)
    {
        current_tree->balance_factor=BALANCED;
        rc->balance_factor=UNBALANCED_RIGHT;
    }
    else if (lg->balance_factor==BALANCED)
    {
        current_tree->balance_factor=BALANCED;
        rc->balance_factor=BALANCED;
    }
    else
    {
        current_tree->balance_factor=UNBALANCED_LEFT;
        rc->balance_factor=BALANCED;
    };

    lg->balance_factor=BALANCED;

    current_tree->rightChild=lg->leftChild;
    rc->leftChild=lg->rightChild;
    lg->leftChild=current_tree;
    lg->rightChild=rc;

    current_tree=lg;
};

void left_tree_update(avl_tree_node &current_tree, bool &review_flag)
{
    avl_tree_node lc;

    lc=current_tree->leftChild;

    if (lc->balance_factor==UNBALANCED_LEFT)
    {
        single_right_rotation(current_tree);
        review_flag=false;
    }
    else if (lc->balance_factor==UNBALANCED_RIGHT)
    {
        double_right_rotation(current_tree);
        review_flag=false;
    };
};

void right_tree_update(avl_tree_node &current_tree, bool &review_flag)
{
    avl_tree_node rc;

    rc=current_tree->rightChild;

    if (rc->balance_factor==UNBALANCED_RIGHT)
    {
        single_left_rotation(current_tree);
        review_flag=false;
    }
    else if (rc->balance_factor==UNBALANCED_LEFT)
    {
        double_left_rotation(current_tree);
        review_flag=false;
    };
}; 

void insert_node(avl_tree_node &current_tree, int newValue, 
                 bool &balance_review_flag)
{
    bool need_balance_review;

    if(current_tree == NULL)
        {
            current_tree = new avl_tree();

            current_tree->Item=newValue;
                    
            balance_review_flag=true;

            return;
        }

        else
        {
            if (newValue < current_tree->Item)
            {
                insert_node(current_tree->leftChild, newValue, 
                            need_balance_review);

                if (need_balance_review)
                {
                    if(current_tree->balance_factor==UNBALANCED_LEFT)
                    {
                     left_tree_update(current_tree, balance_review_flag);
                    }
                    else if (current_tree->balance_factor==BALANCED)
                    {
                     current_tree->balance_factor=UNBALANCED_LEFT;
                     need_balance_review=true;
                    }
                    else
                    {
                     current_tree->balance_factor=BALANCED;
                     need_balance_review=false;
                    };
                }
                else
                {
                    balance_review_flag=false;
                };
            }
            else
            {
                insert_node(current_tree->rightChild, newValue, 
                            need_balance_review);
                
                if (need_balance_review)
                {
                    if(current_tree->balance_factor==UNBALANCED_RIGHT)
                    {
                       right_tree_update(current_tree, 
                                         balance_review_flag);
                    }
                    else if (current_tree->balance_factor==BALANCED)
                    {
                        current_tree->balance_factor=UNBALANCED_RIGHT;
                        need_balance_review=false;
                    }
                    else
                    {
                        current_tree->balance_factor=BALANCED;
                        need_balance_review=false;
                    };
                }
                else
                {
                    balance_review_flag=false;
                };
            };
        };
}; 

void add_node(avl_tree_node &current_tree, int newValue)
{
    bool review_flag=false;
    insert_node(current_tree, newValue, review_flag);
};

void traverse_avl_tree(avl_tree_node current_tree)
{
    if (current_tree!=NULL)
    {
        traverse_avl_tree(current_tree->leftChild);
        std::cout << current_tree->Item << std::endl;
        traverse_avl_tree(current_tree->rightChild);
    };
}; 

avl_tree_node node_by_value(avl_tree_node &current_tree, ItemType key)
{
    if (current_tree==NULL) return(NULL);

    if (current_tree->Item==key)
        {
            return current_tree;             
        };
    
    if(key < current_tree->Item)
        {
            node_by_value(current_tree->leftChild, key);
        }
        else
        {
            node_by_value(current_tree->rightChild, key);
        };
}; 

avl_tree_node get_min(avl_tree_node current_tree) // Find minimum in tree
{
    avl_tree_node min = current_tree;  

    if (min==NULL) return (NULL);
    
    while (min->leftChild!=NULL)
    {
        min=min->leftChild;
    };
    
    return min;
};

avl_tree_node get_parent(avl_tree_node current_tree, avl_tree_node key_node)
{
    if (current_tree==NULL) return (NULL);
    
    if ( ((current_tree->leftChild!=NULL) && (current_tree->leftChild->Item==key_node->Item) ) || ((current_tree->rightChild!=NULL) && (current_tree->rightChild->Item==key_node->Item)) ) return current_tree;
    
    
    if (key_node->Item < current_tree->Item)
    {
        get_parent(current_tree->leftChild, key_node);     
    }
    else
    {
        get_parent(current_tree->rightChild, key_node);
    }
};

void delete_node(avl_tree_node &current_tree, int del_value)
{
    avl_tree_node deleted_node;

    deleted_node=node_by_value(current_tree,del_value);

    if (deleted_node==NULL) return;





    // Case 1: Deleted node has two child

    if ( (deleted_node->leftChild && deleted_node->rightChild)!=NULL)           
    {
        avl_tree_node min_node;
        avl_tree_node parent;

        min_node=get_min(deleted_node->rightChild);
        
        deleted_node->Item=min_node->Item;
 




        // if minimal left node has a right child
    
        if (min_node->rightChild!=NULL)                                       
        {
            min_node->Item=min_node->rightChild->Item;
            min_node->balance_factor=BALANCED;
            min_node->rightChild=NULL;
        }
        else
        {
            parent=get_parent(current_tree, get_min(deleted_node->rightChild));
            parent->leftChild=NULL;

            if (parent->balance_factor==BALANCED)
            {
                parent->balance_factor=UNBALANCED_RIGHT;
            }  
            else
            {
                parent->balance_factor=BALANCED;
            };
            
        };
    }




    // Case 2: Deleted node has only one child
    
    else if ((deleted_node->leftChild || deleted_node->rightChild)!=NULL)    
    {
        if (deleted_node->leftChild!=NULL)
        {
            deleted_node->Item=deleted_node->leftChild->Item;
            deleted_node->leftChild=NULL;
        }
        else
        {
            deleted_node->Item=deleted_node->rightChild->Item;
            deleted_node->rightChild=NULL;
        }
    }




    // Case 3: Deleted node has no children   


    else if ((deleted_node->leftChild || deleted_node->rightChild)==NULL)      
    {
        if (get_parent(current_tree, deleted_node)->leftChild==deleted_node)
        {
            get_parent(current_tree, deleted_node)->leftChild=NULL;
        }
        else
        {
            get_parent(current_tree, deleted_node)->rightChild=NULL;
        };
    };
};

int get_balance_factor(avl_tree_node current_tree)
{
    return current_tree->balance_factor;
};



#endif