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