AVL Tree example c++

An AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."

The balance factor of a node is the height of its right subtree minus the height of its left subtree and a node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. AVL trees perform better than red-black trees for lookup-intensive applications.The AVL tree balancing algorithm appears in many computer science curricula.

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

STL list iterator example c++

An example showing how to use STL list iterator. A STL list iterator is used to specify the location in the list where an items will be inserted or deleted. [STL list iterator]

#include <iostream.h>

#include <list>

void print(list <char> );// elsewhere

main()

{ list <char> l;

list <char>::iterator p;

l.push_back('o'); l.push_back('a'); l.push_back('t');

p=l.begin();

cout <<" "<< *p<<endl;  // p refers to the 'o' in ('o', 'a', 't')

print(l);

l.insert(p, 'c');

// l is now ('c', 'o', 'a', 't') and p still refers to 'o'

cout <<" "<< *p<<endl;

print(l);

l.erase(p);

cout <<" "<< *p<<endl; // p refers to an 'o' but it is not in l!

print(l);

l.erase(l.begin()); //removes front of l

print(l);

}

STL vector sorting example

Here's a simple STL vector sorting example code in c++. a vector container is sorted by using sort() from <algorithm>, . It just traverses the items in a given STL list container.
[STL vector sorting example]

//Sorting a vector with 9 integers

#include <iostream.h>

#include <vector>

#include <algorithm>

void print( vector<int> ) ;//utility function outputs a $container

int main()

{

vector<int> a;

// Place 9,8,7,6,5,4,3,2,1 into the vector

for(int i=0; i<9;++i)

a.push_back(9-i);// put new element after all the others

print(a); // elements of a are (9,8,7,6,5,4,3,2,1)

sort( a.begin(), a.end() ); //in the STL <algorithm> library

print(a); // elements are nor in order.

}

void print( vector<int> a)

{

for(vector<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)

cout << *ai << " ";

cout << endl;

cout << "----------------"<<endl;

}

STL list iterator example

Here's a simple STL list iterator example code in c++. It just traverses the items in a given STL list container. [STL list iterator example]

An Example of Iterating Through a List

void print( list<int> a)

{

for(list<int>::iterator ai=a.begin(); ai!=a.end(); ++ai)

cout << *ai << " ";

cout << endl;

cout << "----------------"<<endl;

}

STL list example

Here's a simple STL list example code in c++. It just shows how to add data into STL queue object and how to sort the list items. [STL list example]

//Using a list to sort a sequence of 9 numbers.

#include <iostream.h>

#include <list>

// #include <algorithm>

void print(list<int> a);//utility function print lists of ints

int main()

{

list<int> a;

//Put 9,8,7,6,5,4,3,2,1 onto the list

for(int i=0; i<9;++i)

a.push_back(9-i);// put new element after all the others

print(a); //here the list contains (9,8,7,6,5,4,3,2,1)

a.sort();//in the <list> library!

print(a); //here the list contains (1,2,3,4,5,6,7,8,9)

}

STL queue example

Here's a simple STL queue example code in c++. It just shows how to push and pop data in STL queue object. [STL queue example]

// A simple example of putting three items into a queue and

// then taking them off the queue.

#include <iostream.h>

#include <list>

#include <queue>

int main()

{

queue<char> q;

q.push('a');

q.push('b');

q.push('c');

cout << q.front();

q.pop();

cout << q.front();

q.pop();

cout << q.front();

q.pop();

}

STL stack example c++ objc

Here's a simple STL stack example code in c++. It just reverses a string using a STL stack object. [STL stack example]

void reverse(string & x)

//Afterwards x will have the same elements in the opposite order.

{

stack<char> s;

const int n = x.length();

//Put characters from x onto the stack

for(int i=0; i<n; ++i)

s.push(x[i]);

//take characters off of stack and put them back into x

for(int i=0; !s.empty(); ++i, s.pop())

x[i]=s.top();

}