AVLTree
A. First Edition
This is first edition of my AVL Tree and I never expect it takes so long as almost one week to finish! Of course
it is partly because of Christmas when I was continually interrupt by the earthly issues such as visiting a
friend and wasting some meaningful time on meaningless matters.
To write AVL tree on template basis and try to keep as much as possible of original BST frame work
because the code by Mr. Shaffer is very concise and compact! And efficiency is also a very important
issue here. As AVLTree has to store extra information than a BST, it is expected that we need to
reduce as many "balancing operations" as possible.
By adding a little piece of code in "insert" method of BST, I actually try to do the keeping-balance
job along the "insert" operation from bottom-up which always keep each node up-to-date balanced. It
is believed by me the best solution to implement it. Unfortunately I have to keep the clue of the
path which leads to the newly-inserted node at leaf position. So, I was obliged to add one more
field in node---"inLeft" which is a boolean value indicating which side the path goes down to the
new leaf. Along with it is the "height" data which is the absolute height of a subtree rooted as
current node. I thought it is a cheating in pseudo code by using "balancing-factor" as instead of
using "real height" of each node. But after finishing the program with several big changes, I
realized I might do some stupid things on assuming that absolute height is necessary. Maybe in
second edition I should combine both "inLeft" and "height" together with "factor"----balancing
factor.
1. bool insert(const Elem& e)
Do you expect that I might start from here? But no, I didn't change anything here. And it is only
after I finished, I thought I can omit it even "inserthelp" is not virtual.
2. BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
This function is almost same as original BST except I try to update the height after each insertion
which will go up from the inserted new leaf along path. And before that insertion, I placed a road
sign "inLeaf" to indicate which side the path takes.
3. void updateHeight(BinNode<Elem>*& subroot);
This is the key part of program where you update height first and then try to examine the balance
and try to keep it. It is the tricky part as I change the code many times. Finally I realized that
there are two big cases: a) The first root which is also the first node with factor 2/-2; b) The node
whose son node has factor of 2/-2; There are some extra conditions to examine the "first" in a) to
make sure it is the "first".
4. int getTreeHeight(BinNode<Elem>* subroot);
I resist to use recursive method because the field "height" is a short-cut.
5. BinNode<Elem>* singleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
Don't forget to adjust balance after rotating and the sequence is important as you have to do it from
bottom-up.
6. BinNode<Elem>* doubleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
I made it look simple by adding the "doDouble" and quite satisfy with it.
E.Further improvement
F.File listing
1. AVLTree.h
2. BinNode.h
3. BST.h
4. dictionary.h
5. Elem.h
6. AVLTree.cpp (main)
file name: BinNode.h
// Binary tree node abstract class
template <class Elem> class BinNode {
public:
// Return the node's element
virtual Elem& val() = 0;
// Set the node's element
virtual void setVal(const Elem&) = 0;
// Return the node's left child
virtual BinNode* left() const = 0;
// Set the node's left child
virtual void setLeft(BinNode*) = 0;
// Return the node's right child
virtual BinNode* right() const = 0;
// Set the node's right child
virtual void setRight(BinNode*) = 0;
// Return true iff the node is a leaf
virtual bool isLeaf() = 0;
//my personal preference
virtual BinNode<Elem>* getSon(bool isLeft)const=0;
//my personal preference
virtual void setSon(BinNode<Elem>* son, bool isLeft)=0;
};
// Binary tree node class
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
// Two constructors -- with and without initial values
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e, BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
~BinNodePtr() {} // Destructor
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; }
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }
bool isLeaf() { return (lc == NULL) && (rc == NULL); }
BinNode<Elem>* getSon(bool isLeft)const {return isLeft?lc:rc;}
void setSon(BinNode<Elem>* son, bool isLeft)
{
isLeft?setLeft(son):setRight(son);
}
};
template <class Elem>
class AVLNodePtr : public BinNode<Elem>
{
protected:
Elem it; // The node's value
AVLNodePtr* lc; // Pointer to left child
AVLNodePtr* rc; // Pointer to right child
int height;
bool inLeft;
public:
// Two constructors -- with and without initial values
AVLNodePtr() { lc = rc = NULL; height=1; inLeft=true; }
AVLNodePtr(Elem e, AVLNodePtr<Elem>* l =NULL,
AVLNodePtr<Elem>* r =NULL, int newHeight=1)
{ it = e; lc = l; rc = r; height=newHeight; inLeft=true;}
~AVLNodePtr() {} // Destructor
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (AVLNodePtr*)b; }
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b) { rc = (AVLNodePtr*)b; }
bool isLeaf() { return (lc == NULL) && (rc == NULL); }
void setHeight(int newHeight){height=newHeight;}
int getHeight(){return height;}
BinNode<Elem>* getSon(bool isLeft)const {return isLeft?lc:rc;}
bool getSide() const {return inLeft;}
void setSide(bool isLeft){ inLeft=isLeft;}
void setSon(BinNode<Elem>* son, bool isLeft)
{
isLeft?setLeft(son):setRight(son);
}
};
file name: BST.h
// This file includes all of the pieces of the BST implementation
#include "dictionary.h"
#include "binnode.h"
// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary<Key, Elem, KEComp, EEComp> {
protected:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes in the BST
// Private "helper" functions
void clearhelp(BinNode<Elem>*);
BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
BinNode<Elem>*&);
bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
void printhelp(BinNode<Elem>*, int) const;
public:
BST() { root = NULL; nodecount = 0; } // Constructor
~BST() { clearhelp(root); } // Destructor
void clear()
{ clearhelp(root); root = NULL; nodecount = 0; }
bool insert(const Elem& e) {
root = inserthelp(root, e);
nodecount++;
return true;
}
bool remove(const Key& K, Elem& e) {
BinNode<Elem>* t = NULL;
root = removehelp(root, K, t);
if (t == NULL) return false; // Nothing found
e = t->val();
nodecount--;
delete t;
return true;
}
bool removeAny(Elem& e) { // Delete min value
if (root == NULL) return false; // Empty tree
BinNode<Elem>* t;
root = deletemin(root, t);
e = t->val();
delete t;
nodecount--;
return true;
}
bool find(const Key& K, Elem& e) const
{ return findhelp(root, K, e); }
int size() { return nodecount; }
void print() const {
if (root == NULL) cout << "The BST is empty.\n";
else printhelp(root, 0);
}
};
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
clearhelp(BinNode<Elem>* subroot) {
if (subroot == NULL) return;
clearhelp(subroot->left());
clearhelp(subroot->right());
delete subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
if (subroot == NULL) // Empty tree: create node
return (new BinNodePtr<Elem>(val, NULL, NULL));
if (EEComp::lt(val, subroot->val())) // Insert on left
subroot->setLeft(inserthelp(subroot->left(), val));
else subroot->setRight(inserthelp(subroot->right(), val));
return subroot; // Return subtree with node inserted
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
if (subroot->left() == NULL) { // Found min
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(deletemin(subroot->left(), min));
return subroot;
}
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
BinNode<Elem>*& t) {
if (subroot == NULL) return NULL; // Val is not in tree
else if (KEComp::lt(K, subroot->val())) // Check left
subroot->setLeft(removehelp(subroot->left(), K, t));
else if (KEComp::gt(K, subroot->val())) // Check right
subroot->setRight(removehelp(subroot->right(), K, t));
else { // Found it: remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL) // Only a right child
subroot = subroot->right(); // so point to right
else if (subroot->right() == NULL) // Only a left child
subroot = subroot->left(); // so point to left
else { // Both children are non-empty
subroot->setRight(deletemin(subroot->right(), temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
}
}
return subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return findhelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return findhelp(subroot->right(), K, e);
else { e = subroot->val(); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
if (subroot == NULL) return; // Empty tree
printhelp(subroot->left(), level+1); // Do left subtree
for (int i=0; i<level; i++) // Indent to level
cout << " ";
cout << subroot->val() << "\n"; // Print node value
printhelp(subroot->right(), level+1); // Do right subtree
}
file name: dictionary.h
// The Dictionary abstract class. KEComp compares a key
// and an element. EEComp compares two elements.
template <class Key, class Elem, class KEComp, class EEComp>
class Dictionary {
public:
// Reinitialize dictionary
virtual void clear() = 0;
// Insert an element. Return true if insert is
// successful, false otherwise.
virtual bool insert(const Elem&) = 0;
// Remove some element matching Key. Return true if such
// exists, false otherwise. If multiple entries match
// Key, an arbitrary one is removed.
virtual bool remove(const Key&, Elem&) = 0;
// Remove and return an arbitrary element from dictionary.
// Return true if some element is found, false otherwise.
virtual bool removeAny(Elem&) = 0;
// Return a copy of some Elem matching Key. Return true
// if such exists, false otherwise. If multiple elements
// match Key, return an arbitrary one.
virtual bool find(const Key&, Elem&) const = 0;
// Return the number of elements in the dictionary.
virtual int size() = 0;
};
file name: Elem.h
//This is the element of login system
class KEComp
{
public:
static bool lt(int key, int elem) {return key<elem;}
static bool eq(int key, int elem) {return key==elem;}
static bool gt(int key, int elem) {return key>elem;}
};
class EEComp
{
public:
static bool lt(int e1, int e2)
{ return e1<e2;}
static bool eq(int e1, int e2)
{ return e1==e2;}
static bool gt(int e1, int e2)
{ return e1>e2;}
};
file name: AVLTree.h
#include "BST.h"
template<class Elem>
struct Descriptor
{
BinNode<Elem>* parent;
bool isRoot;
bool isLeft;
bool isSingle;
bool left2right;
};
template<class Key, class Elem, class KEComp, class EEComp>
class AVL: public BST<Key, Elem, KEComp, EEComp>
{
protected:
// BinNode<Elem>* startPtr;
void clearhelp(BinNode<Elem>*);
BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
BinNode<Elem>*&);
bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
void printhelp(BinNode<Elem>*, int) const;
void updateHeight(BinNode<Elem>*& subroot);
int getFactor(BinNode<Elem>* subroot);
void adjust(BinNode<Elem>*& subroot, bool isRoot);
int getTreeHeight(BinNode<Elem>* subroot);
void adjustHeight(BinNode<Elem>* subroot);
BinNode<Elem>* singleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
BinNode<Elem>* doubleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);
void checkDir(BinNode<Elem>* subroot, bool& isSingle, bool& left2right);
BinNode<Elem>* doDouble(BinNode<Elem>* oldRoot, bool left2right);
public:
AVL() { root = NULL; nodecount = 0; } // Constructor
~AVL() { clearhelp(root); root=NULL; } // Destructor
bool insert(const Elem& e)
{
root = inserthelp(root, e);
nodecount++;
return true;
}
};
//do not use recursive!!!!!
template <class Key, class Elem, class KEComp, class EEComp>
int AVL<Key, Elem, KEComp, EEComp>::getTreeHeight(BinNode<Elem>* subroot)
{
AVLNodePtr<Elem>* ptr, *l, *r;
int newHeight, lHeight, rHeight;//, factor;//, sonFactor;
if (subroot==NULL)
{
return 0;
}
ptr=(AVLNodePtr<Elem>*)subroot;
l=(AVLNodePtr<Elem>*)ptr->left();
r=(AVLNodePtr<Elem>*)ptr->right();
if (l==NULL)
{
lHeight=0;
}
else
{
lHeight=l->getHeight();
}
if (r==NULL)
{
rHeight=0;
}
else
{
rHeight=r->getHeight();
}
newHeight=1+(lHeight>rHeight?lHeight:rHeight);
return newHeight;
}
template <class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::adjustHeight(BinNode<Elem>* subroot)
{
int height;
if (subroot==NULL)
{
return;
}
height=getTreeHeight(subroot);
((AVLNodePtr<Elem>*)(subroot))->setHeight(height);
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::doDouble(BinNode<Elem>* oldRoot,
bool left2right)
{
BinNode<Elem> *small, *mid, *big,*t1,*t2,*t3,*t4;
if (left2right)
{
big=oldRoot;//the root;
small=oldRoot->left();
mid=small->right();
t1=small->left();
t2=mid->left();
t3=mid->right();
t4=big->right();
}
else
{
small=oldRoot;
big=small->right();
mid=big->left();
t1=small->left();
t2=mid->left();
t3=mid->right();
t4=big->right();
}
mid->setLeft(small);
mid->setRight(big);
small->setLeft(t1);
small->setRight(t2);
big->setLeft(t3);
big->setRight(t4);
adjustHeight(small);
adjustHeight(big);
adjustHeight(mid);
return mid;
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::doubleRotate(BinNode<Elem>* parent,
bool isRoot, bool left2right)
{
BinNode<Elem>* oldRoot;
bool isLeft;
if (isRoot)
{
oldRoot=parent;
root=doDouble(oldRoot, left2right);
return root;//because we need parent return as real root
}
else
{
isLeft=((AVLNodePtr<Elem>*)parent)->getSide();
oldRoot=parent->getSon(isLeft);
parent->setSon(doDouble(oldRoot, left2right), isLeft);
adjustHeight(parent);
return parent;
}
}
//if isRoot, we don't need isLeft, it is useful when it is not root and
//we need to know which son it is in
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::singleRotate(BinNode<Elem>* parent,
bool isRoot, bool left2right)
{
BinNode<Elem>* oldRoot=parent, *son, *t1;
bool isLeft=((AVLNodePtr<Elem>*)parent)->getSide();
if (isRoot)
{
son=parent->getSon(isLeft);
t1=son->getSon(!left2right);
son->setSon(parent, !left2right);
parent->setSon(t1, left2right);
//because parent is at lower level now, we need adjust parent first!!!
adjustHeight(parent);//sequence is VERY IMPORTANT!
adjustHeight(son);//sequence is VERY IMPORTANT!
root=son;
return son;//because now, we need return son as parent;
}
else
{
//for non-root rotation, parent doesn't change!!!!!
//it is now very concise!!
oldRoot=parent->getSon(isLeft);
son=oldRoot->getSon(left2right);//this is the trick!
t1=son->getSon(!left2right);
parent->setSon(son, isLeft);
oldRoot->setSon(t1, left2right);
son->setSon(oldRoot, !left2right);
//sequence is very important!!!
adjustHeight(oldRoot);
adjustHeight(son);
adjustHeight(parent);//adjust sequence: from low to high!!!
return parent;
}
}
//check the direction of rotation by returning value in reference
template<class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::checkDir(BinNode<Elem>* subroot,
bool& isSingle, bool& left2right)
{
BinNode<Elem>* son;
int parentFactor, sonFactor;
bool isLeft;
isLeft=((AVLNodePtr<Elem>*)subroot)->getSide();
son=subroot->getSon(isLeft);
parentFactor=getFactor(subroot);
sonFactor=getFactor(son);
isSingle=parentFactor*sonFactor>0;//same sign
left2right=parentFactor>0;
}
//if isroot, isLeft will be ignored.
template <class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::adjust(BinNode<Elem>*& subroot, bool isRoot)
{
BinNode<Elem>* temp;
bool isSingle, left2right, isLeft;
if (isRoot)
{
temp=subroot;
}
else
{
//use its son to check
isLeft=((AVLNodePtr<Elem>*)subroot)->getSide();
temp=subroot->getSon(isLeft);
}
checkDir(temp, isSingle, left2right);
if (isSingle)
{
//it helps reading and for singleRotate isLeft is ignored when it is isRoot
subroot=singleRotate(subroot, isRoot, left2right);
}
else
{
subroot=doubleRotate(subroot, isRoot, left2right);
}
}
template <class Key, class Elem, class KEComp, class EEComp>
int AVL<Key, Elem, KEComp, EEComp>::getFactor(BinNode<Elem>* subroot)
{
int lHeight, rHeight;
AVLNodePtr<Elem>* ptr, *l, *r;
if (subroot==NULL)
{
return 0;
}
ptr=(AVLNodePtr<Elem>*)subroot;
l=(AVLNodePtr<Elem>*)(ptr->left());
r=(AVLNodePtr<Elem>*)(ptr->right());
if (l==NULL)
{
lHeight=0;
}
else
{
lHeight= l->getHeight();
}
if (r==NULL)
{
rHeight=0;
}
else
{
rHeight=r->getHeight();
}
return lHeight-rHeight;
}
template <class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::updateHeight(BinNode<Elem>*& subroot)
{
int factor, sonFactor;
bool isLeft;
BinNode<Elem> *son;
if (subroot==NULL)
{
return;
}
adjustHeight(subroot);
factor=getFactor(subroot);
isLeft=((AVLNodePtr<Elem>*)subroot)->getSide();
son=subroot->getSon(isLeft);
sonFactor=getFactor(son);
//first situation: the first 2/-2 we meet from bottom-up
if ((factor==2||factor==-2)&&subroot==root)
{
//a special case!!! as we search from bottom up
//we may wait to adjust until we reach its father
//the father happens to be root. But it is not a
//root adjustment!!!
if (sonFactor==1||sonFactor==-1)
{
adjust(subroot, true);
}
else
{
adjust(subroot, false);
}
}
else
{
if (sonFactor==2||sonFactor==-2)
{
adjust(subroot, false);
}
}
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* AVL<Key, Elem, KEComp, EEComp>::inserthelp(BinNode<Elem>* subroot,
const Elem& val)
{
if (subroot == NULL) // Empty tree: create node
{
return (new AVLNodePtr<Elem>(val, NULL, NULL, 1));
}
if (EEComp::lt(val, subroot->val())) // Insert on left
{
((AVLNodePtr<Elem>*)subroot)->setSide(true);
subroot->setLeft(inserthelp(subroot->left(), val));
updateHeight(subroot);
}
else
{
((AVLNodePtr<Elem>*)subroot)->setSide(false);
subroot->setRight(inserthelp(subroot->right(), val));
updateHeight(subroot);
}
return subroot; // Return subtree with node inserted
}
template <class Key, class Elem, class KEComp, class EEComp>
void AVL<Key, Elem, KEComp, EEComp>::clearhelp(BinNode<Elem>* subroot)
{
if (subroot == NULL)
{
return;
}
clearhelp(subroot->left());
clearhelp(subroot->right());
delete subroot;
}
file name: AVLTree.cpp (main)
#include <iostream>
#include <time.h>
#include "AVLTree.h"
#include "Elem.h"
using namespace std;
int main()
{
int num;
AVL<int, int, KEComp, EEComp> A;
//srand(time(0));
for (int i=0; i<25; i++)
{
cout<<"===================";
num=rand()%100+12;
cout<<"insert number "<<num<<endl;
A.insert(num);
A.print();
}
return 0;
}
Here is the result: Please note that there are
single rotating while inserting number 90, 93, 107,
double rotating while inserting number 36, 74,
===================insert number 53
53
===================insert number 79
53
79
===================insert number 46
46
53
79
===================insert number 12
12
46
53
79
===================insert number 81
12
46
53
79
81
===================insert number 36
12
36
46
53
79
81
===================insert number 90
12
36
46
53
79
81
90
===================insert number 70
12
36
46
53
70
79
81
90
===================insert number 74
12
36
46
53
70
74
79
81
90
===================insert number 76
12
36
46
53
70
74
76
79
81
90
===================insert number 17
12
17
36
46
53
70
74
76
79
81
90
===================insert number 57
12
17
36
46
53
57
70
74
76
79
81
90
===================insert number 93
12
17
36
46
53
57
70
74
76
79
81
90
93
===================insert number 39
12
17
36
39
46
53
57
70
74
76
79
81
90
93
===================insert number 73
12
17
36
39
46
53
57
70
73
74
76
79
81
90
93
===================insert number 103
12
17
36
39
46
53
57
70
73
74
76
79
81
90
93
103
===================insert number 107
12
17
36
39
46
53
57
70
73
74
76
79
81
90
93
103
107
===================insert number 54
12
17
36
39
46
53
54
57
70
73
74
76
79
81
90
93
103
107
===================insert number 39
12
17
36
39
39
46
53
54
57
70
73
74
76
79
81
90
93
103
107
===================insert number 48
12
17
36
39
39
46
48
53
54
57
70
73
74
76
79
81
90
93
103
107
Press any key to continue