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