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
   上一页 [1] [2] [3] [4] 下一页 |
热门搜索: 
