AVL树的删除操作

#include "AVLTree.h" //AVL树的重载操作 >> template <class Type> istream & operator >> ( istream & in, AVLTree<Type> & Tree ) { Type item; cout << "构造AVL树 :\n"; cout << "输入数据(每次输入一个结点的值并按回车，不能重复，以" << Tree.RefValue << "结束): "; in >> item; while ( item != Tree.RefValue ) { Tree.Insert (item); cout << "输入数据(每次输入一个结点的值并按回车，不能重复，以" << Tree.RefValue << "结束): "; in >> item; } return in; }//end template <class Type> istream & operator >> ( istream & in, AVLTree<Type> & Tree ) //AVL树的重载操作<< template <class Type> ostream & operator << ( ostream & out, const AVLTree<Type> & Tree ) { out << "AVL树的中序遍历.\n"; Tree.Traverse ( Tree.root, out ); out << endl; return out; } //end template <class Type> ostream & operator << ( ostream & out, const AVLTree<Type> & Tree ) //AVL树中序遍历并输出数据 template <class Type> void AVLTree<Type>:: Traverse ( AVLNode *ptr, ostream & out ) const { if ( ptr != NULL ) { Traverse ( ptr->left, out ); out << ptr->data << ' '; Traverse ( ptr->right, out ); } } //end template <class Type> void AVLTree Type:: Traverse ( AVLNode *ptr, ostream & out ) const //左单旋转 template <class Type> void AVLTree<Type>:: RotateLeft ( AVLNode *Tree, AVLNode* &NewTree ) { NewTree = Tree->right; Tree->right = NewTree->left; NewTree->left = Tree; } //end template <class Type> void AVLTree<Type>:: RotateLeft ( AVLNode *Tree, AVLNode* &NewTree ) //右单旋转 template <class Type> void AVLTree<Type>:: RotateRight( AVLNode *Tree, AVLNode* &NewTree) { NewTree = Tree->left; Tree->left = NewTree->right; NewTree->right = Tree; }//end template <class Type> void AVLTree<Type>:: RotateRight( AVLNode *Tree, AVLNode* &NewTree) //左平衡化 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 << "树已经平衡化.\n"; break; case 1 : rightsub = leftsub->right; switch ( rightsub->balance ) { case -1: Tree->balance = 1; leftsub->balance = 0; break; case 0 : Tree->balance = 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; } } //end template <class Type> void AVLTree<Type>:: LeftBalance ( AVLNode * &Tree, int & taller ) //右平衡化 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 << "树已经平衡化.\n"; break; case -1 : leftsub = rightsub->left; switch ( leftsub->balance ) { case 1 : Tree->balance = -1; rightsub->balance = 0; break; case 0 : Tree->balance = 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; } } //end template <class Type> void AVLTree<Type>:: RightBalance ( AVLNode * &Tree, int & taller ) //AVL树的插入 template <class Type> int AVLTree<Type>:: Insert ( AVLNode* &tree, Type x, int &taller ) { //标记是否成功插入 int success; //如果是空树（找到了插入位置） if ( tree == NULL ) { //构造一棵AVL树，树根的值为插入值 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 ) //根据树的balance值 switch ( tree->balance ) { //左边子树较高则左平衡 case -1 : LeftBalance ( tree, taller ); break; //左右子树等高则标记此时左边子树较高（因为左子树高度增加） case 0 : tree->balance = -1; break; //右边子树较高则置0（已平衡） case 1 : tree->balance = 0; taller = 0; break; } } //如果插入值大于于树根的值 else if ( x > tree->data ) { //插入到树根的右子树 success = Insert ( tree->right, x, taller ); //如果树的右子数高度增加 if ( taller ) //根据树的balance值 switch ( tree->balance ) { //左边子树较高则置0（已平衡） case -1 : tree->balance = 0; taller = 0; break; //左右子树等高则标记此时右边子树较高（因为右子树高度增加） case 0 : tree->balance = 1; break; //右边子树较高则右平衡 case 1 : RightBalance ( tree, taller ); break; } } //返回插入是否成功 return success; } //end template <class Type> int AVLTree<Type>:: Insert ( AVLNode* &tree, Type x, int &taller ) //AVL的删除算法 template <typename Type> bool AVLTree<Type>::Delete(AVLNode * &tree, Type x, bool &shorter){ bool success; //搜索x节点 AVLNode *p=tree,*q=0; while(p && p->data!=x){ q=p; //q is p's father if(x<p->data){p=p->left;} else if (x>p->data){p=p->right;} } if(!p){ cerr<<"No element with key"<<x<<endl; return false; } x=p->data; //p指向待删除的节点,把data赋给x success=true; //有两个孩子的情况 if(p->left&&p->right){ //招p的直接后继 AVLNode *s=p->right,*r=p; while(s->left){ r=s; s=s->left; } p->data=s->data; p=s; q=r; } //只有一个孩子的情况 AVLNode *c ; //c point to the only child if(p->left){c=p->left;} else c=p->right; if (p==tree) tree=c; else if(p==q->left) q->left=c; else q->right=c; if(p->left){ while(shorter){ switch(tree->balance){ case -1: tree->balance=0; break; case 0: tree->balance=1; shorter=false; break; case 1: AVLNode *q=tree->right; switch(q->balance){ case 0: RotateLeft(tree,q); shorter=false; break; case 1:RotateLeft(tree,q); p->balance=q->balance=0; shorter=true; break; case -1: RotateRight(q,q); RotateLeft(tree,tree); tree->balance = 0; shorter = true; break; } break; } } }else if(p->right){ while(shorter){ switch(tree->balance){ case -1: { AVLNode *q=tree->left; switch(q->balance){ case 0: RotateRight(tree,q); shorter=false; break; case -1: RotateRight(tree,q); p->balance=q->balance=0; shorter=true; break; case 1: RotateLeft(q,q); RotateRight(tree,tree); tree->balance=0; shorter=true; break; } break; } case 0: { p->balance=-1; shorter=false; break; } case 1: { p->balance=0; break; } } } } }