业余时间没事自己实现了个avl树的C++模板类，留着平时用。在这里公开，供大家参考。
断断续续的写了挺长时间，主要是自己动力不足。
/*
*AVL_TREE
*完成了添加、删除、查找节点功能。
*author：lysde
*date：2010-9-9
*Email:
*参考资料：
*免责：作者不对代码做任何担保。遵循apache授权许可。
*/
#include
/* Instruction
* The tree's base level is 1.
* When inserting a node to the tree,if the node value
* is already in the tree then return true and do nothing.
* 中序遍历树需要回调函数
*
*/
template
class avl_tree
{
public:
struct node
{
node(T d) {data = d; lc = rc = prnt = NULL; LL = RL = L = 0;}
T data;
int LL,RL,L; // left level,right level,self level.
node *lc,*rc,*prnt;
};
public:
avl_tree()
{
root = NULL;
size = 0;
}
~avl_tree()
{
if(root)
{
//delete all the nodes.
del_subtree(root);
}
}
//Any question please send email:
//If there exists the node return true,else return false.
node * search(T data)
{
bool flag = false;
node *ntmp = NULL;
if(!root)
return false;
ntmp = root;
while(ntmp != NULL && !flag)
{
if(data == ntmp->data)
{
flag=true;
}
else if(data < ntmp->data)
{
ntmp = ntmp->lc;
}
else
{
ntmp = ntmp->rc;
}
}
if(flag)
return ntmp;
else
return NULL;
}
//If insert the node successfully return true,else return false.
bool insert(T data)
{
if(!root)
{
root = new node(data);
root->LL = root->RL = 0;
root->L = 1;
size++;
return true;
}
//There is a data in the tree.
// if(search(data)) return true;
node *n, *parent=NULL, *ntmp, *child;
//Find a position to insert the data in the tree.
ntmp = root;
bool flag = false;
while(ntmp != NULL && !flag)
{
if(data == ntmp->data)
{
flag=true;
}
else if(data < ntmp->data)
{
parent = ntmp;
ntmp = ntmp->lc;
}
else
{
parent = ntmp;
ntmp = ntmp->rc;
}
}
if(flag)
{
//size++;
return true;
}
//Inssert the node.
if(ntmp == NULL)
{
n = new node(data);
if(data < parent->data)
{
parent->lc = n;
n->prnt = parent;
n->L = parent->L + 1;
}
else
{
parent->rc = n;
n->prnt = parent;
n->L = parent->L + 1;
}
}
//Modify all notes' level info.
adjust_gene_up(n);
//Find what model this is.
//Ajust the tree to keep it balance.
node *subroot = NULL;
ntmp = n->prnt;
child = n;
while(ntmp->prnt != NULL)
{
if(ntmp->prnt->LL - ntmp->prnt->RL >= 2 ) // left level - right level > 2
{
//LL or LR
if(ntmp->lc == child)
{
//LL
subroot = balancell(child);
}
else
{
//LR
subroot = balancelr(child);
}
break;
}
else if(ntmp->prnt->LL - ntmp->prnt->RL <= -2)
{
//RL or RR
if(ntmp->lc == child)
{
//RL
subroot = balancerl(child);
}
else
{
//RR
subroot = balancerr(child);
}
break;
}
child = ntmp;
ntmp = ntmp->prnt;
}
//下面调整最小不平衡树的level信息 及 与该最小不平衡树相关的节点的level 信息。
// Adjust the level information.
if(subroot)
{
if(subroot == root)
adjust_level_previous(subroot,0);
else
adjust_level_previous(subroot,subroot->prnt->L);
adjust_gene_down(subroot);
adjust_gene_up(subroot);
}
size++;
return true;
}
//If delete the node successfully return true,else return false.
bool del(T data)
{
//删除后，使用左侧最大值（或右侧最小值）代替被删除值的位置。我们采用左侧最大值。
//然后调整该子树的平衡及整棵树的平衡。
node * n, *np = NULL, *nn, *nnp = NULL;
if( (n = search(data)) == NULL)
return false;
//
if(root == n) //被删结点为root。
{
if(n->lc == NULL) //左子树不存在
{
root = n->rc;
if(n->rc != NULL)
{
root->prnt = NULL;
}
//nnp = nn = root;
nnp = NULL;
}
else //存在左子树
{
//找到左子树中的最大值
nnp = n;
nn = nnp->lc;
while(nn->rc != NULL)
{
nnp = nn;
nn = nnp->rc;
}
if(nnp == n)
{
root = nn;
root->prnt = NULL;
root->rc = n->rc;
if(n->rc != NULL)
n->rc->prnt = nn;
nnp = root;
}
else
{
//Left subtree.
root = nn;
root->prnt = NULL;
nnp->rc = nn->lc;
if(nn->lc != NULL)
nn->lc->prnt = nnp;
nn->lc = n->lc;
n->lc->prnt = nn;
nn->rc = n->rc;
if(n->rc != NULL)
n->rc->prnt = nn;
}
}
}
else //被删结点为非root。
{
np = n->prnt;
if(n->lc == NULL) //左子树不存在
{
if(np->lc == n)
{
np->lc = n->rc;
}
else
{
np->rc = n->rc;
}
if(n->rc != NULL)
n->rc->prnt = np;
nnp = np;
}
else //存在左子树
{
//找到左子树中的最大值
nnp = n;
nn = nnp->lc;
while(nn->rc != NULL)
{
nnp = nn;
nn = nnp->rc;
}
if(nnp == n)
{
//Left subtree.
if(np->lc == n)
{
np->lc = nn;
}
else //Right subtree.
{
np->rc = nn;
}
nn->prnt = np;
nn->rc = n->rc;
if(n->rc != NULL)
n->rc->prnt = nn;
nnp = nn;
}
else
{
//Left subtree.
if(np->lc == n)
{
np->lc = nn;
}
else //Right subtree.
{
np->rc = nn;
}
nn->prnt = np;
nnp->rc = nn->lc;
if(nn->lc != NULL)
nn->lc->prnt = nnp;
nn->lc = n->lc;
n->lc->prnt = nn;
nn->rc = n->rc;
if(n->rc != NULL)
n->rc->prnt = nn;
}
}
}
delete n;
size--;
//调整树的平衡及各结点的level信息
node * subroot;
while(nnp != NULL)
{
adjust_level_previous(root,0);
adjust_gene_down(root);
adjust_gene_up(root);
if(nnp->LL - nnp->RL >= 2)
{
//LL or LR
if(nnp->lc->LL - nnp->lc->RL >= 0)
{
//LL
//subroot = balancell(nnp->lc->lc);
nnp = balancell(nnp->lc->lc);
}
else
{
//LR
nnp = balancelr(nnp->lc->rc);
}
}
else if(nnp->LL - nnp->RL <= -2)
{
//RR or RL
if(nnp->rc->LL - nnp->rc->RL <= 0)
{
//RR
nnp = balancerr(nnp->rc->rc);
}
else
{
//RL
nnp = balancerl(nnp->rc->lc);
}
}
if(nnp!= NULL)
nnp = nnp->prnt;
}
adjust_level_previous(root,0);
adjust_gene_down(root);
adjust_gene_up(root);
return true;
}
typedef void (*outfunc)(const node *);
void mt(outfunc fnc) {midorder_travel(root,fnc);}
long height() const
{
long high;
high = root->LL >= root->RL? root->LL : root->RL;
high ++;
return high;
}
int get_size() { return size;}
node * search(const node *n) { return search(n->data);};
node *get_root_data() { return root; }
node *min_node()
{
node * t,*tp = NULL;
t = root;
while(t)
{
tp = t;
t = t->lc;
}
return tp;
}
node *max_node()
{
node * t,*tp = NULL;
t = root;
while(t)
{
tp = t;
t = t->rc;
}
return tp;
}
protected:
avl_tree(const avl_tree &);
avl_tree & operator=(const avl_tree&);
node * balancell(node *n) //Return the root of the subtree.
{
node * np,*npp,*nppp,*mr;
//LL
if(!n)
return NULL;
np = n ->prnt;
npp = np->prnt;
nppp = np->prnt->prnt;
//旋转
//Rotate
np->prnt = nppp;
if(nppp != NULL)
{
if(nppp->lc == npp)
{
nppp->lc = np;
}
else
{
nppp->rc = np;
}
}
else
{
root = np;
}
mr = np;
if(np->rc == NULL)
{
np->rc = npp;
np->prnt = npp->prnt;
npp->prnt = np;
npp->lc = NULL;
}
else
{
npp->lc = np->rc;
np->prnt = npp->prnt;
np->rc->prnt = npp;
np->rc = npp;
npp->prnt = np;
}
return mr;
}
node * balancelr(node *n) //Return the root of the subtree.
{
if(!n)
return NULL;
node * np,*npp,*nppp;
//LR
np = n ->prnt;
npp = np->prnt;
nppp = np->prnt->prnt;
//旋转
//Rotate
n->prnt = npp;
if(n->lc != NULL)
{
n->lc->prnt = np;
np->rc = n->lc;
}
else
np->rc = NULL;
n->lc = np;
np->prnt = n;
npp->lc = n;
return balancell(n->lc);
}
node * balancerr(node *n) //Return the root of the subtree.
{
if(!n)
return NULL;
node * np,*npp,*nppp,*mr;
//RR
np = n ->prnt;
npp = np->prnt;
nppp = np->prnt->prnt;
//旋转
//Rotate
np->prnt = nppp;
if(nppp != NULL)
{
if(nppp->rc == npp)
{
nppp->rc = np;
}
else
{
nppp->lc = np;
}
}
else
{
root = np;
}
mr = np;
if(np->lc == NULL)
{
np->lc = npp;
np->prnt = npp->prnt;
npp->prnt = np;
npp->rc = NULL;
}
else
{
npp->rc = np->lc;
np->prnt = npp->prnt;
np->lc->prnt = npp;
np->lc = npp;
npp->prnt = np;
}
return mr;
}
node * balancerl(node *n) //Return the root of the subtree.
{
if(!n)
return NULL;
node * np,*npp,*nppp;
//LR
np = n ->prnt;
npp = np->prnt;
nppp = np->prnt->prnt;
//旋转
//Rotate
n->prnt = npp;
if(n->rc != NULL)
{
n->rc->prnt = np;
np->lc = n->rc;
}
else
np->lc = NULL;
n->rc = np;
np->prnt = n;
npp->rc = n;
return balancerr(n->rc);
}
//n is the leaf that is just inserted or the subtree root.
void adjust_gene_up(node *n) //Adjuest the tree level info from the new tree leaf.
{
if(!n)
return;
node *ntmp = n;
while(ntmp != NULL && ntmp->prnt != NULL)
{
if(ntmp->data < ntmp->prnt->data)
{
ntmp->prnt->LL = ntmp->LL >= ntmp->RL?ntmp->LL:ntmp->RL;
ntmp->prnt->LL+=1;
}
else
{
ntmp->prnt->RL = ntmp->LL >= ntmp->RL?ntmp->LL:ntmp->RL;
ntmp->prnt->RL+=1;
}
ntmp = ntmp->prnt;
}
}
void adjust_level_previous(node *n,int prnt_level)
{
if(!n)
return;
n->L = prnt_level + 1;
if(n->lc != NULL)
{
adjust_level_previous(n->lc,n->L);
}
//else if(n->rc != NULL)
if(n->rc != NULL)
{
adjust_level_previous(n->rc,n->L);
}
}
void adjust_gene_down(node *n)
{
if(!n)
return;
if(n->lc != NULL)
{
adjust_gene_down(n->lc);
}
if(n->rc != NULL)
{
adjust_gene_down(n->rc);
}
if(n->lc == NULL)
{
n->LL = 0;
}
else
{
n->LL = n->lc->LL >= n->lc->RL ? n->lc->LL : n->lc->RL;
n->LL+=1;
}
if(n->rc == NULL)
{
n->RL = 0;
}
else
{
n->RL = n->rc->LL >= n->rc->RL?n->rc->LL:n->rc->RL;
n->RL+=1;
}
}
void del_subtree(node *n)
{
if(!n)
return;
if(n->lc != NULL)
{
del_subtree(n->lc);
}
if(n->rc != NULL)
{
del_subtree(n->rc);
}
delete n;
}
void midorder_travel(const node *n,outfunc fun)const
{
if(!n)
return;
if(n->lc != NULL)
{
midorder_travel(n->lc,fun);
}
(*fun)(n);
if(n->rc != NULL)
{
midorder_travel(n->rc,fun);
}
}
node *root;
int size;
};
//用法：
//编译方法: g++ test_avl_tree.cpp -o avl
//linux、solaris 验证通过
#include "avl_tree_normal.hpp"
#include
#include
#include
#include
#include
#define RANGE 4096
#define DELRANGE 2048
using namespace std;
void print_value(const avl_tree::node * tn)
{
static int counter = 0;
cout << tn->data << "(" << tn->LL - tn->RL << ") ";
if(counter%4 == 0)
cout << endl;
counter ++;
}
int main()
{
avl_tree tree;
avl_tree::node * tn;
srand(time(NULL));
for(int i = 0; i < RANGE * 2; i++)
{
int t = rand()%RANGE;
tree.insert(t);
}
tree.mt(print_value);
cout << endl;
cout << "tree height: " << tree.height() << endl;
cout << "Tree size: " << tree.get_size() << endl;
tn = tree.get_root_data();
if(tn)
cout << "root data: " << tn->data << endl;
else
cout << "root data: " << -99 << endl;
cout << endl;
sleep(3);
cout << "delete list:" << endl;
for(int i = 0; i < DELRANGE; i++)
{
int t = rand()%RANGE;
cout << t << " ";
tree.del(t);
}
cout << endl;
cout << "tree height: " << tree.height() << endl;
cout << "Tree size: " << tree.get_size() << endl;
tn = tree.get_root_data();
if(tn)
cout << "root data: " << tn->data << endl;
else
cout << "root data: " << -99 << endl;
tree.mt(print_value);
cout << endl;
cout << "tree height: " << tree.height() << endl;
cout << "Tree size: " << tree.get_size() << endl;
tn = tree.get_root_data();
if(tn)
cout << "root data: " << tn->data << endl;
else
cout << "root data: " << -99 << endl;
tn = tree.min_node();
if(tn)
cout << "Minimum data: " << tn->data << endl;
else
cout << "Minimum data: " << -99 << endl;
tn = tree.max_node();
if(tn)
cout << "Maximum data: " << tn->data << endl;
else
cout << "Maximum data: " << -99 << endl;
}
