avltree.h

AVL均衡二叉树的的C++模板实现。带有册除功能

#ifndef AVLTREE_H
#define AVLTREE_H

#include < iostream >
#include < iomanip >
using namespace std;

template < class Type > class AVLTree {
public:
struct AVLNode {
   Type data; 
   AVLNode *left, *right; 
   int balance;

   AVLNode():left(NULL), right(NULL),balance(0){}
   AVLNode(Type d, AVLNode *l = NULL, AVLNode *r = NULL):
   data(d), left(l), right(r), balance(0){}
};

protected:
Type RefValue;
AVLNode *root;
int Insert(AVLNode *&tree, Type x, int &taller);
int Delete(AVLNode *&tree, Type x, int &shorter);
void RotateLeft(AVLNode *Tree, AVLNode *&NewTree);
void RotateRight(AVLNode *Tree, AVLNode *&NewTree);
void LeftBalance(AVLNode *&Tree, int &taller);
void RightBalance(AVLNode *&Tree, int &taller);
void LeftBalance_(AVLNode *&Tree, int &taller);
void RightBalance_(AVLNode *&Tree, int &taller);

void Traverse_graph(AVLNode *ptr, ostream &out, int &level, bool &bEnd, int *bFlag, bool &bLR)const;
void Traverse_layer(AVLNode *ptr, ostream &out, int layer)const;
//int Height(AVLNode *t)const;
public:
AVLTree():root(NULL){}
AVLTree(Type Ref): RefValue(Ref), root(NULL){}
int Insert(Type x){int taller; return Insert(root, x, taller);}
int Delete(Type x); //{int shorter; return Delete(root, x, shorter);}

friend istream& operator >> (istream &in, AVLTree <Type> &Tree);
friend ostream& operator << (ostream &out, AVLTree <Type> &Tree);

void Traverse(AVLNode *ptr, ostream &out)const;
void Traverse_graph(AVLNode *ptr, ostream &out)const;
void Traverse_layer(AVLNode *ptr, ostream &out)const;
//int Height()const;
};

template < class Type >
void AVLTree < Type >::RotateLeft(AVLNode *Tree, AVLNode *&NewTree) {
NewTree = Tree->right;
Tree->right = NewTree->left;
NewTree->left = Tree;
}

template < class Type >
void AVLTree < Type >::RotateRight(AVLNode *Tree, AVLNode *&NewTree) {
NewTree = Tree->left;
Tree->left = NewTree->right;
NewTree->right = Tree;
}

/*
* 以下操作只适用于插入时的调整
*/

template < class Type >
void AVLTree < Type >::LeftBalance(AVLNode *&Tree, int &taller) {
AVLNode *leftsub = Tree->left, *rightsub;
switch(leftsub->balance) {
   case -1:
    Tree->balance = leftsub->balance = 0;
    RotateRight(Tree, Tree); taller = 0; break;
   case 0:
    cout<<"LeftBalance error: Tree already balanced: \n"; break;
   case 1:
    rightsub = leftsub->right;
    switch(rightsub->balance) {
     case -1:
      Tree->balance = 1; leftsub->balance = 0; break;
     case 0:
      Tree->balance = 0; leftsub->balance = 0; break;
     case 1:
      Tree->balance = 0; leftsub->balance = -1; break;
    }
    rightsub->balance = 0;
    RotateLeft(leftsub, Tree->left);
    RotateRight(Tree, Tree); taller = 0;
}
}

template < class Type >
void AVLTree < Type >::RightBalance(AVLNode *&Tree, int &taller) {
AVLNode *rightsub = Tree->right, *leftsub;
switch(rightsub->balance) {
   case 1:
    Tree->balance = rightsub->balance = 0;
    RotateLeft(Tree, Tree); taller = 0; break;
   case 0:
    cout<<"RightBalance error: Tree already balanced. \n"; break;
   case -1:
    leftsub = rightsub->left;
    switch(leftsub->balance) {
     case 1:
      Tree->balance = -1; rightsub->balance = 0; break;
     case 0:
      Tree->balance =0; rightsub->balance = 0; break;
     case -1:
      Tree->balance = 0; rightsub->balance = 1; break;
    }
    leftsub->balance = 0;
    RotateRight(rightsub, Tree->right);
    RotateLeft(Tree, Tree); taller = 0;
}
}

template < class Type >
int AVLTree < Type >::Insert(AVLNode *&tree, Type x, int &taller) {
int success;
if(tree == NULL) {
   tree = new AVLNode(x);
   success = tree != NULL ? 1 : 0;
   if(success) taller = 1;
}
else if(x < tree->data) {
   success = Insert(tree->left, x, taller);
   if(taller)
    switch(tree->balance) {
     case -1: LeftBalance(tree, taller); break;
     case 0: tree->balance = -1; break;
     case 1: tree->balance = 0; taller = 0; break;
    }
}
else if(x > tree->data) {
   success = Insert(tree->right, x, taller);
   if(taller)
    switch(tree->balance) {
     case -1: tree->balance = 0; taller = 0; break;
     case 0: tree->balance = 1; break;
     case 1: RightBalance(tree, taller); break;
    }
}
return success;
}

/*
* 以下平衡操作只适用于删除时的调整
*/
template < class Type >
void AVLTree < Type >::LeftBalance_(AVLNode *&Tree, int &shorter) {
AVLNode *leftsub = Tree->left, *rightsub;
switch(leftsub->balance) {
   case -1:
    Tree->balance = leftsub->balance = 0;
    RotateRight(Tree, Tree); break;
   case 0:
    Tree->balance = -1; leftsub->balance = 1;
    RotateRight(Tree, Tree); shorter = 0; break;
   case 1:
    rightsub = leftsub->right;
    switch(rightsub->balance) {
     case -1:
      Tree->balance = 1; leftsub->balance = 0; break;
     case 0:
      Tree->balance = 0; leftsub->balance = 0; break;
     case 1:
      Tree->balance = 0; leftsub->balance = -1; break;
    }
    rightsub->balance = 0;
    RotateLeft(leftsub, Tree->left);
    RotateRight(Tree, Tree);
}
}

template < class Type >
void AVLTree < Type >::RightBalance_(AVLNode *&Tree, int &shorter) {
AVLNode *rightsub = Tree->right, *leftsub;
switch(rightsub->balance) {
   case 1:
    Tree->balance = rightsub->balance = 0;
    RotateLeft(Tree, Tree); break;
   case 0:
    Tree->balance = 1; rightsub->balance = -1;
    RotateLeft(Tree, Tree); shorter = 0; break;
   case -1:
    leftsub = rightsub->left;
    switch(leftsub->balance) {
     case 1:
      Tree->balance = -1; rightsub->balance = 0; break;
     case 0:
      Tree->balance =0; rightsub->balance = 0; break;
     case -1:
      Tree->balance = 0; rightsub->balance = 1; break;
    }
    leftsub->balance = 0;
    RotateRight(rightsub, Tree->right);
    RotateLeft(Tree, Tree);
}
}

template < class Type >
int AVLTree < Type >::Delete(Type x) {
int shorter;
return Delete(root, x, shorter);
}

template < class Type >
int AVLTree < Type >::Delete(AVLNode *&tree, Type x, int &shorter) {
int success = 0;
if(tree != NULL) {
   if(x == tree->data) {
    if(tree->left != NULL && tree->right != NULL) {
     // 这个分支必须放在这里!且只会被执行一次
     // 先将数据与其直接前驱交换
     AVLNode *q = tree->left;
     AVLNode *r = q;
     while(q != NULL) {
      r = q;
      q = q->right;
     }
     Type temp = tree->data;
     tree->data = r->data;
     r->data = temp;
     // 然后在其左子树上删除结果
     success = Delete(tree->left, x, shorter);
     if(shorter) {
      switch(tree->balance) {
       case -1: tree->balance = 0; break;
       case 0: tree->balance = 1; shorter = 0; break;
       case 1: RightBalance_(tree, shorter); break;
      }
     }
    }
    else {
     AVLNode *p = tree;
     tree = tree->left != NULL ? tree->left : tree->right;
     delete p;
     success = 1;
     shorter = 1;
    }
   }
   else if(x < tree->data) {
    success = Delete(tree->left, x, shorter);
    if(shorter) {
     switch(tree->balance) {
      case -1: tree->balance = 0; break;
      case 0: tree->balance = 1; shorter = 0; break;
      case 1: RightBalance_(tree, shorter); break;
     }
    }
   }
   else if(x > tree->data) {
    success = Delete(tree->right, x, shorter);
    if(shorter) {
     switch(tree->balance) {
      case -1: LeftBalance_(tree, shorter); break;
      case 0: tree->balance = -1; shorter = 0; break;
      case 1: tree->balance = 0; break;
     }
    }
   }
}
return success;
}

template<class Type>
istream& operator >> (istream &in, AVLTree <Type> &Tree) {
Type item;
cout<<"Construct AVL tree:\n";
cout<<"Input data(end with "<<Tree.RefValue<<"): ";
in>>item;
while(item != Tree.RefValue) {
   Tree.Insert(item);
   //cout<<Tree;
   cout<<"Input Data(end with "<<Tree.RefValue<<"): ";
   in>>item;
}
return in;
}
template<class Type>
ostream &operator << (ostream &out, AVLTree < Type > &Tree) {
Tree.Traverse_graph(Tree.root, out);
Tree.Traverse_layer(Tree.root, out);
out<<endl;
return out;
}

/*
* How can we output the tree as the following format?
* Note: Following format comes from Linux Kernel 2.4.0 Mmap_av.c:117
*/
/*                                                        */
/*                *                     n+2               */
/*              /   \                 /     \             */
/*           n+2      n      -->    n+1     n+1           */
/*           / \                    / \     / \           */
/*          n n+1                 n   L   R   n          */
/*             / \                                        */
/*            L   R                                       */
/*                                                        */
template < class Type >
void AVLTree < Type >::Traverse(AVLNode *ptr, ostream &out)const {
static int count = 4;
if(ptr != NULL) {
   --count;
   Traverse(ptr->left, out);
   ++count;

   out<<setw(3)<<left<<ptr->data;//<<"("<<count<<") ";

   ++count;
   Traverse(ptr->right, out);
   --count;
}
}

template < class Type >
void AVLTree < Type >::Traverse_layer(AVLNode *ptr, ostream &out)const {
if( ptr == NULL ) return;
int layer = 0;
Traverse_layer(ptr, out, layer);
}

template < class Type >
void AVLTree < Type >::Traverse_layer(AVLNode *ptr, ostream &out, int layer)const {
if( ptr == NULL ) return;
if( ptr->right ) {
   Traverse_layer(ptr->right, out, layer + 1);
}
for( int i = 0; i < layer; i++ ) {
   //printf(".   ");
   out<<".   ";
}
//printf("%d\n", ptr->data);
out<<ptr->data<<endl;
if( ptr->left ) {
   Traverse_layer(ptr->left, out, layer + 1);
}
}

template < class Type >
void AVLTree < Type >::Traverse_graph(AVLNode *ptr, ostream &out)const {
int level = -1;
bool bEnd = true;
int *bFlag = new int[100];
bool bLR = false;

Traverse_graph(ptr, out, level, bEnd, bFlag, bLR);
delete []bFlag;
}

template < class Type >
void AVLTree < Type >::Traverse_graph(AVLNode *ptr, ostream &out, int &level, bool &bEnd, int *bFlag, bool &bLR)const {
/*
static int level = -1;
static bool bEnd = true; //如果是最后一个结点
static int *bFlag = new int[100];
static bool bLR = false; // false means: Left, true means: Right
*/
++level;
//bFlag[level] = 1;

if(ptr != NULL) {
   for(int i = 0; i < level; ++i) {
    if(bFlag[i])
     //printf("│ ");
     out<<"│ ";
    else
     //printf("    ");
     out<<"    ";
   }

   if(bEnd){
    if(!bLR)
     //printf("└─L:%d B:%d\n", ptr->data, ptr->balance);
     out<<"└─L:"<<ptr->data<<" B:"<<ptr->balance<<endl;
    else
     //printf("└─R:%d B:%d\n", ptr->data, ptr->balance);
     out<<"└─R:"<<ptr->data<<" B:"<<ptr->balance<<endl;
   }
   else {
    if(!bLR)
     //printf("├─L:%d B:%d\n", ptr->data, ptr->balance);
     out<<"├─L:"<<ptr->data<<" B:"<<ptr->balance<<endl;
    else
     //printf("├─R:%d B:%d\n", ptr->data, ptr->balance);
     out<<"├─R:"<<ptr->data<<" B:"<<ptr->balance<<endl;
   }

   if((ptr->left == NULL && ptr->right == NULL) || bEnd)
    bFlag[level] = 0;
   else
    bFlag[level] = 1;

   if(ptr->right == NULL)
    bEnd = true;
   else
    bEnd = false;

   bLR = false;
   Traverse_graph(ptr->left, out, level, bEnd, bFlag, bLR);

   bEnd = true;
   bLR = true;
   Traverse_graph(ptr->right, out, level, bEnd, bFlag, bLR);
}

//delete bFlag[level];
--level;
//bEnd = false;
}

#endif