平衡二叉树AVL删除

平衡二叉树的插入过程: http://www.cnblogs.com/hujunzheng/p/4665451.html

对于二叉平衡树的删除采用的是二叉排序树删除的思路:

　　假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：
⑴ 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。
⑵ 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。
⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：
① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
② 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。

注：leftBalance_del 和 rightBalance_del方法是在删除节点时对左子树和右子树的平衡调整，leftBalance 和 rightBalance方法是在插入节点是对左右子树的平衡调整。 在具体调整的时候，和插入式调整时运用同样的分类方法，这里介绍一种情况，如下图所示（代码部分见代码中的提示）

#include<iostream> #include<cstring> #include<string> #include<queue> #include<map> #include<cstdio> #define LH 1 //左高 #define EH 0 //等高 #define RH -1 //右高 using namespace std; template <typename ElemType> class BSTNode{ public: ElemType data;//节点的数据 int bf;//节点的平衡因子 BSTNode *child[2]; BSTNode(){ child[0] = NULL; child[1] = NULL; } }; typedef BSTNode<string> BSTnode, *BSTree; template <typename ElemType> class AVL{ public: BSTNode<ElemType> *T; void buildT(); void outT(BSTNode<ElemType> *T); void deleteAVL(BSTNode<ElemType>* &T, ElemType key, bool &shorter); bool insertAVL(BSTNode<ElemType>* &T, ElemType key, bool &taller); private: void deleteNode(BSTNode<ElemType>* T, BSTNode<ElemType>* &s, BSTNode<ElemType>* p, bool flag, bool &shorter); void rotateT(BSTNode<ElemType>* &o, int x);//子树的左旋或者右旋 void leftBalance(BSTNode<ElemType>* &o); void rightBalance(BSTNode<ElemType>* &o); void leftBalance_del(BSTNode<ElemType>* &o); void rightBalance_del(BSTNode<ElemType>* &o); }; template <typename ElemType> void AVL<ElemType>::rotateT(BSTNode<ElemType>* &o, int x){ BSTNode<ElemType>* k = o->child[x^1]; o->child[x^1] = k->child[x]; k->child[x] = o; o = k; } template <typename ElemType> void AVL<ElemType>::outT(BSTNode<ElemType> *T){ if(!T) return; cout<<T->data<<" "; outT(T->child[0]); outT(T->child[1]); } template <typename ElemType> void AVL<ElemType>::buildT(){ T = NULL; ElemType key; while(cin>>key){ if(key==0) break; bool taller = false; insertAVL(T, key, taller); } } template <typename ElemType> void AVL<ElemType>::deleteNode(BSTNode<ElemType>* T, BSTNode<ElemType>* &s, BSTNode<ElemType>* p, bool flag, bool &shorter){ if(flag){ flag = false; deleteNode(T, s->child[0], s, flag, shorter); if(shorter){ switch(s->bf){ case LH: s->bf = EH; shorter = false; break; case EH: s->bf = RH; shorter = true; break; case RH: rightBalance_del(s); shorter = false; break; } } } else { if(s->child[1]==NULL){ T->data = s->data; BSTNode<ElemType>* ss = s; if(p != T){ p->child[1] = s->child[0]; } else { p->child[0] = s->child[0]; } delete ss;//s是引用类型，不能delete s shorter = true; return ; } deleteNode(T, s->child[1], s, flag, shorter); if(shorter){ switch(s->bf){ case LH://这是上面配图的情况 leftBalance_del(s); shorter = false; break; case EH: s->bf = LH; shorter = true; break; case RH: s->bf = EH; shorter = false; break; } } } } template <typename ElemType> bool AVL<ElemType>::insertAVL(BSTNode<ElemType>* &T, ElemType key, bool &taller){ if(!T){//插入新的节点，taller=true 那么树的高度增加 T = new BSTNode<ElemType>(); T->data = key; T->bf = EH; taller = true; } else { if(T->data == key){ taller = false; return false; } if(T->data > key){//向T的左子树进行搜索并插入 if(!insertAVL(T->child[0], key, taller)) return false; if(taller){// switch(T->bf){ case LH://此时左子树的高度高，左子树上又插入了一个节点，失衡，需要进行调整 leftBalance(T); taller = false;//调整之后高度平衡 break; case EH: T->bf = LH; taller = true; break; case RH: T->bf = EH; taller = false; break; } } } if(T->data < key) {//向T的右子树进行搜索并插入 if(!insertAVL(T->child[1], key, taller)) return false; switch(T->bf){ case LH: T->bf = EH; taller = false; break; case EH: T->bf = RH; taller = true; break; case RH: rightBalance(T); taller = false; break; } } } return true; } template <typename ElemType> void AVL<ElemType>::deleteAVL(BSTNode<ElemType>* &T, ElemType key, bool &shorter){ if(T->data == key){ BSTNode<ElemType>*q, s; if(!T->child[1]){//右子树为空，然后重接其左子树 q = T; T = T->child[0]; shorter = true;//树变矮了 delete q; } else if(!T->child[0]){//左子树为空，重接其右子树 q = T; T = T->child[1]; shorter = true;//树变矮了 delete q; } else {//左右子树都非空 ，也就是第三种情况 deleteNode(T, T, NULL, true, shorter); shorter = true; } } else if(T->data > key) {//左子树 deleteAVL(T->child[0], key, shorter); if(shorter){ switch(T->bf){ case LH: T->bf = EH; shorter = false; break; case RH: rightBalance_del(T); shorter = false; break; case EH: T->bf = RH; shorter = true; break; } } } else if(T->data < key){//右子树 deleteAVL(T->child[1], key, shorter); if(shorter){ switch(T->bf){ case LH://这是上面配图的情况 leftBalance_del(T); shorter = false; break; case RH: T->bf = EH; shorter = false; break; case EH: T->bf = LH; shorter = true; break; } } } } template <typename ElemType> void AVL<ElemType>::leftBalance(BSTNode<ElemType>* &T){ BSTNode<ElemType>* lchild = T->child[0]; switch(lchild->bf){//检查T的左子树的平衡度，并作相应的平衡处理 case LH://新节点 插入到 T的左孩子的左子树上，需要对T节点做单旋(右旋)处理 T->bf = lchild->bf = EH; rotateT(T, 1); break; case RH://新节点 插入到 T的左孩子的右子树上，需要做双旋处理 1.对lchild节点进行左旋，2.对T节点进行右旋 BSTNode<ElemType>* rdchild = lchild->child[1]; switch(rdchild->bf){//修改 T 及其左孩子的平衡因子 case LH: T->bf = RH; lchild->bf = EH; break; case EH: T->bf = lchild->bf = EH; break;//发生这种情况只能是 rdchild无孩子节点 case RH: T->bf = EH; lchild->bf = LH; break; } rdchild->bf = EH; rotateT(T->child[0], 0);//不要写成 rotateT(lc, 0);//这样的话T->lchild不会改变 rotateT(T, 1); break; } } template <typename ElemType> void AVL<ElemType>::rightBalance(BSTNode<ElemType>* &T){ BSTNode<ElemType>* rchild = T->child[1]; switch(rchild->bf){//检查T的左子树的平衡度，并作相应的平衡处理 case RH://新节点 插入到 T的右孩子的右子树上，需要对T节点做单旋(左旋)处理 T->bf = rchild->bf = EH; rotateT(T, 0); break; case LH://新节点 插入到 T的右孩子的左子树上，需要做双旋处理 1.对rchild节点进行右旋，2.对T节点进行左旋 BSTNode<ElemType>* ldchild = rchild->child[0]; switch(ldchild->bf){//修改 T 及其右孩子的平衡因子 case LH: T->bf = EH; rchild->bf = RH; break; case EH: T->bf = rchild->bf = EH; break;//发生这种情况只能是 ldchild无孩子节点 case RH: T->bf = LH; rchild->bf = EH; break; } ldchild->bf = EH; rotateT(T->child[1], 1); rotateT(T, 0); break; } } template <typename ElemType> void AVL<ElemType>::leftBalance_del(BSTNode<ElemType>* &T){ BSTNode<ElemType>* lchild = T->child[0]; switch(lchild->bf){ case LH: T->bf = EH; lchild->bf = EH; rotateT(T, 1); break; case EH: T->bf = LH; lchild->bf = EH; rotateT(T, 1); break; case RH://这是上面配图的情况 BSTNode<ElemType>* rdchild = lchild->child[1]; switch(rdchild->bf){ case LH: T->bf = RH; lchild->bf = rdchild->bf = EH; break; case EH: rdchild->bf = T->bf = lchild->bf = EH; break; case RH: T->bf = rdchild->bf = EH; lchild->bf = LH; break; } rotateT(T->child[0], 0); rotateT(T, 1); break; } } template <typename ElemType> void AVL<ElemType>::rightBalance_del(BSTNode<ElemType>* &T){ BSTNode<ElemType>* rchild = T->child[1]; BSTNode<ElemType>* ldchild = rchild->child[0]; switch(rchild->bf){ case LH: switch(ldchild->bf){ case LH: ldchild->bf = T->bf = EH; rchild->bf = RH; break; case EH: ldchild->bf = T->bf = rchild->bf = EH; break; case RH: rchild->bf = T->bf = EH; ldchild->bf = LH; break; } rotateT(T->child[1], 1); rotateT(T, 0); break; case EH: //outT(this->T);e EH: T->bf = RH; rchild->bf = EH; rotateT(T, 0); break; case RH: T->bf = EH; rchild->bf = EH; rotateT(T, 0); break; } } int main(){ AVL<int> avl; avl.buildT(); cout<<"平衡二叉树先序遍历如下:"<<endl; avl.outT(avl.T); cout<<endl; bool shorter = false; avl.deleteAVL(avl.T, 24, shorter); avl.outT(avl.T); return 0; } /* 24 37 90 53 0 24 37 90 53 12 26 0 */