//******************************************************************************************** //***說明：2叉排序樹遍歷是從小到大的順序，AVL樹也是bst，但是滿足所有的樹的左右高度相差不大于1 //***平衡2叉樹是1種特殊的2叉樹，滿足以上要求，主要是為了進1步的優化，提高操作的效力（O(log(n))） //***針對下面情況進行調劑 //***測試pat1066 http://www.patest.cn/contests/pat-a-practise/1066 //*********1*******************************1**********2*************************************** //**************************************************/*************************************** //***********2**************************************1***4************************************* //*******************------>**************************/************************************* //*************3**************************************3***5*********************************** //**************4***************************************************************************** //******************************************************************************************* //****************5*************************************************************************** // 其中主要的策略就是選擇，旋轉1共分為下面4種情況 //******** A ********** B ************** C ********************* D *************************** //******************************************************************************************** //***** 6 **** 6 ************2***********************2**************************** //***** / **** / ***********/**********************/**************************** //***** 3 7 **** 2 7 **********1***5*******************1***4************************** //***** / **** / *************/**********************/************************** //*****1 4 **** 1 4 ************3***6*******************3***6************************ //***** **** / **************************************/************************* //***** 2 **** 3 **************4***********************5************************** //******************************************************************************************** //******************************************************************************************** //******************************************************************************************** //******************************************************************************************** //******************************************************************************************** /********************************************************************************************* *A、6節點的左子樹3節點高度比右子樹7節點大2，左子樹3節點的左子樹1節點高度大于右子樹4節點，這類情況成為左左。 *B、6節點的左子樹2節點高度比右子樹7節點大2，左子樹2節點的左子樹1節點高度小于右子樹4節點，這類情況成為左右。 *C、2節點的左子樹1節點高度比右子樹5節點小2，右子樹5節點的左子樹3節點高度大于右子樹6節點，這類情況成為右左。 *D、2節點的左子樹1節點高度比右子樹4節點小2，右子樹4節點的左子樹3節點高度小于右子樹6節點，這類情況成為右右。 * *說明：2叉排序樹遍歷是從小到大的順序，AVL樹也是bst，但是滿足所有的樹的左右高度相差不大于1 */ #ifndef AVL_H #define AVL_H #include <iostream> using namespace std; /*AVL樹節點信息*/ template <typename T> class TreeNode { public : TreeNode():lchild(NULL),rchild(NULL),freq(1),hgt(0){} T data ;/*值*/ int hgt;/*以此節點為根的樹的高度*/ unsigned int freq;/*頻率*/ TreeNode * lchild,*rchild;/*左右孩子*/ }; /*AVL樹類的屬性和方法聲明*/ template <typename T> class AVLTree { private : TreeNode<T> *root; /*根節點*/ void InsertPri(TreeNode<T> * &node, T x); /*插入x*/ TreeNode <T>* FindPri(TreeNode<T> *node ,T x); /*查找x*/ void InSubTree(TreeNode<T> *node); /*中序遍歷*/ void DeletePri(TreeNode<T> * &node, T x); /*刪除*/ int height(TreeNode<T> *node); /*樹的高度*/ void SingRotateLeft(TreeNode<T> * &k2); /*左左情況下的旋轉*/ void SingRotateRight(TreeNode<T> * &k2); /*右右情況的旋轉*/ void DoubleRotateLR(TreeNode<T> * &k3); /*左右情況的旋轉*/ void DoubleRotateRL(TreeNode<T> * &k3); /*左右情況的旋轉*/ int Max(int cmpa,int cmpb); /*求最大值*/ public : AVLTree():root(NULL){} void insert(T x); /*插入接口*/ TreeNode<T> * Find(T x); /*查找接口*/ void Delete(T x); /*刪除接口*/ void Treversal(); /*遍歷接口*/ }; /*計算以節點為根的樹的高度*/ template <typename T> int AVLTree <T>::height(TreeNode<T>* node) { return node!=NULL? node->hgt:⑴; } /*求最大值*/ template <typename T> int AVLTree<T>::Max(int cmpa,int cmpb) { return cmpa>cmpb ? cmpa :cmpb; } /************************************************************************/ /* 單旋轉 單旋轉是針對左左和右右這兩種情況的解決方案，這兩種情況是 *對稱的，只要解決了左左這類情況，右右就很好辦了。圖3是左左情況的解決方案， *節點k2不滿足平衡特性，由于它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深 *的1層的是k1的左子樹X子樹，所以屬于左左情況 (左左情況下的選擇) */ /*為使樹恢復平衡，我們把k2變成這棵樹的根節點，由于k2大于k1，把k2置于k1的右 *子樹上，而本來在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既 *********************滿足了2叉查找樹的性質，又滿足了平衡2叉樹的性質。*/ /************************************************************************/ //****************k2******************************k1********************** //***************/******************************/*********************** //**************k1**z****--------->*************x***k2******************** //*************/**********************************/********************* //************x***y*******************************y***z******************* /*這樣的操作只需要1部份指針改變，結果我們得到另外1顆2叉查找樹，它是1棵AVL樹，由于X向 *上1移動了1層，Y還停留在原來的層面上，Z向下移動了1層。整棵樹的新高度和之前沒有在左子 *樹上插入的高度相同，插入操作使得X高度長高了。因此，由于這顆子樹高度沒有變化，所以通往根 *節點的路徑就不需要繼續旋轉了。***********************************************/ /*左左旋轉*/ template <typename T> void AVLTree<T>::SingRotateLeft(TreeNode<T> * &k2) { TreeNode<T> *k1; k1=k2->lchild; k2->lchild=k1->rchild; k1->rchild=k2; k2->hgt=Max(height(k2->lchild),height(k2->rchild))+1; k1->hgt=Max(height(k1->lchild),k2->hgt)+1; k2=k1;/*最后1定要更新根節點*/ } /*右右旋轉*/ template <typename T> void AVLTree<T>::SingRotateRight(TreeNode<T> * &k2) { TreeNode<T> *k1; k1=k2->rchild; k2->rchild=k1->lchild; k1->lchild=k2; k2->hgt=Max(height(k2->lchild),height(k2->rchild))+1; k1->hgt=Max(height(k1->rchild),k2->hgt)+1; k2=k1;/*最后1定要更新根節點*/ } /**************************雙旋轉(左右情況下的雙旋轉)************************/ //************************************************************************ //*************k3******************k3**********************k2************* //************/******************/**********************/************** //**********k1***d*---->********k2***d*****---->********k1****k3********** //*********/*******************/*********************/****/*********** //********a****k2*************k1***c******************a***b*c***d********* //************/*************/******************************************* //***********b***c**********a***b***************************************** //************************************************************************ //************************************************************************ //************************************************************************ /************************************************************************/ /* *左右旋轉 *為使樹恢復平衡，我們需要進行兩步，第1步，把k1作為根，進行1次右右旋轉，旋轉以后就變成 *了左左情況，所以第2步再進行1次左左旋轉，最后得到了1棵以k2為根的平衡2叉樹樹。 */ template <typename T> void AVLTree<T>::DoubleRotateLR(TreeNode<T> * &k3) { SingRotateRight(k3->lchild); SingRotateLeft(k3); } /*右左旋轉*/ template <typename T> void AVLTree<T>::DoubleRotateRL(TreeNode<T> * &k3) { SingRotateLeft(k3->rchild); SingRotateRight(k3); } /************************************************************************* *插入的方法和2叉查找樹基本1樣，區分是，插入完成后需要從插入的節點開始保護 *1個到根節點的路徑，每經過1個節點都要保持樹的平衡。 *保持樹的平衡要根據高度差的特點選擇不同的旋轉算法。 *insert *************************************************************************/ template <typename T> void AVLTree<T>::InsertPri(TreeNode<T>* &node, T x) { if(node==NULL)/*如果節點為空,就在此節點處加入x信息*/ { node =new TreeNode<T>(); node->data=x; return ; } if (node->data>x)/*如果X小于節點的值，就繼續再節點的左子樹中插入*/ { InsertPri(node->lchild,x); if (2==height(node->lchild)-height(node->rchild)) { if (x<node->lchild->data) { SingRotateLeft(node); } else DoubleRotateLR(node); } } else if (node->data<x)/*如果X大于節點的值，就繼續再節點的右子樹中插入*/ { InsertPri(node->rchild,x); if (2==height(node->rchild)-height(node->lchild)) { if (x>node->rchild->data) { SingRotateRight(node); } else DoubleRotateRL(node); } } else node->freq++;/*如果相等，頻率加1*/ node->hgt=Max(height(node->lchild),height(node->rchild))+1; } /************************************************************************/ /* 插入接口 */ /************************************************************************/ template <typename T> void AVLTree<T>::insert(T x) { InsertPri(root,x); } /************************************************************************/ /* 查找 */ /*和2叉查找樹相比，查找方法沒有變法，不過根據存儲的特性， *AVL樹能保持在1個O(logN)的穩定的時間，而2叉查找樹則相當不穩定。 /************************************************************************/ template<typename T> TreeNode<T>* AVLTree<T>::FindPri(TreeNode<T> *node ,T x) { if(node==NULL)/*如果節點為空說明沒找到,返回NULL*/ return NULL; if(node->data>x)/*如果x小于節點的值,就繼續在節點的左子樹中查找x*/ return FindPri(node->lchild,x); if (node->data<x)/*如果x大于節點的值,就繼續在節點的左子樹中查找x*/ return FindPri(node->rchild,x); return node;/*如果相等,就找到了此節點*/ } /*查找接口*/ template<typename T> TreeNode<T>* AVLTree<T>::Find(T x) { return FindPri(root,x); } /************************************************************************/ /* 刪除 */ /*刪除的方法也和2叉查找樹的1致，區分是，刪除完成后， *需要從刪除節點的父親開始向上保護樹的平衡1直到根節點。 /************************************************************************/ template<typename T> void AVLTree<T>::DeletePri(TreeNode<T> * &node, T x) { if(node==NULL)/*空*/ return ; if(x<node->data) {/*如果x小于節點的值,就繼續在節點的左子樹中刪除x，刪除完成后，需要調劑樹，使之保持平衡*/ DeletePri(node->lchild,x); if (2==height(node->rchild)-height(node->lchild)) { if(node->rchild->lchild!=NULL && (height(node->rchild->lchild)>height(node->rchild->rchild)) ) DoubleRotateRL(node); else SingRotateRight(node); } } else if (x>node->data) {/*如果大于節點的值,就繼續在節點的右子樹中刪除x，刪除完成后，需要調劑樹，使之保持平衡*/ DeletePri(node->rchild,x); if (2==height(node->lchild)-height(node->rchild)) { if(node->rchild->lchild!=NULL && (height(node->lchild->rchild)>height(node->lchild->lchild)) ) DoubleRotateLR(node); else SingRotateLeft(node); } } else/*相等，刪除，然后調劑，使之平衡*/ { if (node->lchild && node->rchild)/*此節點有兩個兒子*/ { TreeNode<T>* temp=node->rchild;/*temp指向節點的右兒子*/ while(temp->lchild!=NULL) temp=temp->lchild;/*找到中序遍歷的后繼節點，一定在最左側那個*/ node->data=temp->data;/*調劑節點數據信息*/ node->freq=temp->freq; DeletePri(node->rchild,temp->data);/*刪除邊沿節點*/ if (2==height(node->lchild)-height(node->rchild)) { if (node->lchild->rchild!=NULL && (height(node->lchild->rchild)>height(node->lchild->lchild)) ) DoubleRotateLR(node); else SingRotateLeft(node); } } else/*此節點有1個或0個兒子*/ { TreeNode<T> *temp=node; if(node->lchild==NULL)/*有右兒子或沒有兒子*/ node=node->rchild; else if(node->rchild==NULL)/*有左兒子*/ node=node->lchild; delete(temp); temp=NULL; } } if(node==NULL) return ; node->hgt=Max(height(node->lchild),height(node->rchild))+1; return ; } /*刪除接口*/ template<typename T> void AVLTree<T>::Delete(T x) { DeletePri(root,x); } /*中序遍歷函數*/ template<typename T> void AVLTree<T>::InSubTree(TreeNode<T> *node) { if(node==NULL) return ; InSubTree(node->lchild);/*先遍歷左子樹*/ cout<<node->data<<" ";/*輸出根節點*/ InSubTree(node->rchild);/*再遍歷右子樹*/ } /*中序遍歷接口*/ template<typename T> void AVLTree<T>::Treversal() { //cout<<root->data; InSubTree(root); } #endif//avl.h

#include "AVL.h" int arrs[7]={88,70,61,96,120,90,65}; int main(int argc,char** argv) { AVLTree<int> te; for (int i=0;i<7;i++) { te.insert(arrs[i]); } te.Treversal(); return 0; }