平衡二叉樹的插入過程:?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; } /*13 24 37 90 53 013 24 37 90 53 12 26 0 */
?
)
)
