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();    
        }  
};      

AVL Tree example c c++

Following code is an 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]
source code : AVL_tree.cpp

#include <stdio.h> 
#include <stdlib.h> 

#define max(a,b)    (((a) > (b)) ? (a) : (b)) 

typedef struct AvlNode 
{ 
    int data; 
    AvlNode *left_child, *right_child; 
}AvlNode; 

AvlNode *root; 



AvlNode* rotate_LL(AvlNode *parent) 
{ 
    AvlNode *child = parent->left_child; 
    parent->left_child = child->right_child; 
    child->right_child = parent; 
    return child; 
} 


AvlNode* rotate_RR(AvlNode *parent) 
{ 
    AvlNode *child = parent->right_child; 
    parent->right_child = child->left_child; 
    child->left_child = parent; 
    return child; 
} 


AvlNode* rotate_RL(AvlNode *parent) 
{ 
    AvlNode *child = parent->right_child; 
    parent->right_child = rotate_LL(child); 
    return rotate_RR(parent); 
} 


AvlNode* rotate_LR(AvlNode *parent) 
{ 
    AvlNode *child = parent->left_child; 
    parent->left_child = rotate_RR(child); 
    return rotate_LL(parent); 
} 

int get_height(AvlNode *node) 
{ 
    int height=0; 
    if(node != NULL) 
        height = 1+max(get_height(node->left_child),get_height(node->right_child)); 
    return height; 
} 

 
int get_balance(AvlNode *node) 
{ 
    if(node == NULL) return 0; 
    return get_height(node->left_child) - get_height(node->right_child); 
} 

 
AvlNode* balance_tree(AvlNode **node) 
{ 
    int height_diff= get_balance(*node); 
     
    if(height_diff > 1) 

{ 
        if(get_balance((*node)->left_child) > 0) 
            *node = rotate_LL(*node); 
        else  
            *node = rotate_LR(*node); 
    } 
    else if(height_diff < -1)

{ 
        if(get_balance((*node)->right_child) < 0) 
            *node = rotate_RR(*node); 
        else 
            *node = rotate_RL(*node); 
    } 
    return *node; 
} 

AvlNode* avl_add(AvlNode **root,int key) 
{ 
    if(*root == NULL) 
    { 
        *root = (AvlNode*)malloc(sizeof(AvlNode)); 
        if(*root == NULL) 
        { 
            printf("fail: memory allocation\n"); 
            exit(-1); 
        } 

        (*root)->data = key;     
        (*root)->left_child = (*root)->right_child = NULL; 
    } 
    else if(key < (*root)->data) 
    { 
        (*root)->left_child = avl_add(&((*root)->left_child),key); 
        (*root) = balance_tree(root);  
    } 
    else if(key > (*root)->data) 
    { 
        (*root)->right_child = avl_add(&((*root)->right_child), key); 
        (*root) = balance_tree(root); 
    } 
    else 
    { 
        printf("fail! - duplicated key\n"); 
        exit(-1); 
    } 
    return *root; 
} 


AvlNode* avl_search(AvlNode *node, int key) 
{ 
    if(node == NULL) return NULL; 
     
    printf("%d->",node->data); 

    if(key == node->data)  
        return node; 
    else if(key < node->data) 
        avl_search(node->left_child,key); 
    else  
        avl_search(node->right_child,key); 
} 

int main() 
{ 
    avl_add(&root,8); 

avl_add(&root,9); 
    avl_add(&root,10); 
    avl_add(&root,2); 
    avl_add(&root,1); 
    avl_add(&root,5); 
    avl_add(&root,3); 
    avl_add(&root,6); 
    avl_add(&root,4); 
    avl_add(&root,7); 
    avl_add(&root,11); 
    avl_add(&root,12); 

    avl_search(root,12); 

    return 0; 
} 

merge sort example c/c++ - 2

Following code fragment is another merge sort example written in c++ language. Merge sort algorithm is very similar to quick sort algorithm. Both partition the input data into two parts and recursively apply sort algorithm on them.

#include <stdio.h>

#define LEN 9

void merge_sort(int num[],int start, int end); 

void merge(int num[], int start, int mid, int end);

void tracer(int num[],int len);

int main(void){

     

    int testArr[LEN] = {485,241,454,325,452,685,498,890,281};

    merge_sort(testArr, 0, LEN-1);

}

void merge_sort(int num[],int start, int end){

    int median = (start + end)/2; 

    if(start < end){ 

        merge_sort(num, start, median); 

        merge_sort(num, median+1, end); 

        merge(num, start, median, end); 

    }

}

void merge(int num[], int start, int median, int end){

    int i,j,k,m,n;

    int tempArr[LEN]; 

    i = start; 

    j = median+1; 

    k = start; 

    while (i <= median && j <= end){

        tempArr[k++] = (num[i] > num [j]) ? num [j++] : num [i++];

    }

     

    m = (i > median) ? j : i; 

    n = (i > median) ? end : median; 

    for (; m<=n; m++){ 

        tempArr[k++] = num[m];

    }

    for (m=start; m<=end; m++){

        num[m] = tempArr[m]; 

    }

    printf("Merging: %d ~ %d & %d ~ %d\n",start,median,median+1,end);

    tracer(num,LEN);

}

void tracer(int num[],int len){

    int i;

    for(i=0;i<len;i++){

        printf("%d\t",num[i]);

    }

    printf("\n\n");

}

merge sort example c/c++

Following code fragment is a merge sort example written in c/c++ language. Merge sort algorithm is very similar to quick sort algorithm. Both partition the input data into two parts and recursively apply sort algorithm on them.

void MergeSort(int *naData, int nLen)

{

     int i = 0, nFHIdx = 0, nSHIdx = 0;    

     int nHalf = nLen / 2;              

     int *naFirstHalf, *naSecondHalf;

     if(nLen == 1)

          return;

  

     naFirstHalf = (int *)malloc(sizeof(int) * nHalf);

     naSecondHalf = (int *)malloc(sizeof(int) * nLen-nHalf);

    

     memcpy(naFirstHalf, naData, sizeof(int) * nHalf);

     memcpy(naSecondHalf, naData+nHalf, sizeof(int) * nLen-nHalf);

  

     MergeSort(naFirstHalf, nHalf);

     MergeSort(naSecondHalf, nLen-nHalf);

     while(nFHIdx < nHalf || nSHIdx < nLen-nHalf)      

     {

          if(nFHIdx == nHalf)

          {

                naData[i++] = naSecondHalf[nSHIdx++];

          }else if(nSHIdx == nLen-nHalf)

          {

               naData[i++] = naFirstHalf[nFHIdx++];

          }else if(naFirstHalf[nFHIdx] >= naSecondHalf[nSHIdx])

          {

               naData[i++] = naSecondHalf[nSHIdx++];

          }else

          {

               naData[i++] = naFirstHalf[nFHIdx++];

          }

     }

 

     free(naFirstHalf);

     free(naSecondHalf);

}

binary search tree c/c++ - 2

Following example code is another implementation of binary search tree in C++ language. Binary search tree is a data structure that shows log(n) search time.

1. tree node data structure.

typedef struct BTREE {
     char data;
     struct BTREE *left, *right;
} BTREE;

2. traversals for preorder, inorder, postorder.

int preorder(BTREE *t)
{
     if ( t != NULL) {
         printf("%c", t->data);
         preorder(t->left);
         preorder(t->right);
     }
}

int inorder(BTREE *t)
{
     if ( t != NULL) {
         inorder(t->left);
         printf("%c", t->data);
         inorder(t->right);
     }
}

int postorder(BTREE *t)
{
     if ( t != NULL) {
         postorder(t->left);
         postorder(t->right);
         printf("%c", t->data);
     }
}

3. swap_tree routine.

int swap_tree(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = swap_tree(t->right);
        p->right = swap_tree(t->left);
        p->data = t->data;
        return p;
    }
}

4. tree copy

int tree_copy(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = tree_copy(t->left);
        p->right = tree_copy(t->right);
        p->data = t->data;
        return p;
    }
}

5. getting max depth of the tree.

int max_depth(BTREE *t)
{
    int max = 0, depth;

    if( t == NULL)
        return 0;
    else {
         depth = max_depth(t->left) + 1;
         if( depth > max)
              max = depth;
         depth = max_depth(t->right) + 1;
         if( depth > max)
              max = depth;
         return max;
    }


}

binary search tree c/c++

Following example code is an implementation of binary search tree in C++ language.
Binary search tree is a data structure that shows log(n) search time.


// tree node.
typedef struct _tree
{
     int data;
     struct _tree *left, *right;
}tree


// Search function.
//
tree *search(tree *root, int key)
{
     while(root != NULL)
     {
          if( key == root->key ) return root;
          else if( key < root->key) root=root->left;
          else root=root->right;
     }
     return NULL;
}

// Insert function.
void insert_tree(tree **root, int key)
{
     tree p, t;                              //p for parent, t for temp node
     tree n;                                 //n for new node

     p=NULL;
     t=*root;

     while(t!=NULL)
     {
          if(key==t->key) return;    
          if(key < t->key)             
               t=t->left;
          else
               t=t->right;
     }

     n=(tree*)malloc(sizeof(tree));        
     n->key=key;                            
     n->left=n->right=NULL;           

     if(p!=NULL)                          
     {
          if(key < p->key)            
               p->left=n;
          else                            
               p->right=n;
     }else *root=n;                
}

srand() code example c c++ objc

A simple random number generator based on rand() and srand() functions.
srand() function is used to initialize seed for random number.

Example - srand()

#include<stdlib.h>

// Create random number between 0 and 100.
int n = rand() % 100;

// Create random character between '0' and '9' in ASCII code.
srand(time(NULL));
 for(i=0;i<100;i++)  
 {
   char ch = rand() % (57-48+1)+48;
   putc(ch);
 }