图解数据结构7-二叉查找树及平衡二叉查找树.doc

这篇将是最有难度和挑战性的一篇，做好心理准备！十、二叉查找树（BST）前一篇介绍了树，却未介绍树有什么用。但就算我不说，你也能想得到，看我们Windows的目录结构，其实就是树形的，一个典型的分类应用。当然除了分类，树还有别的作用，我们可以利用树建立一个非常便于查找取值又非常便于插入删除的数据结构，这就是马上要提到的二叉查找树（Binary Search Tree），这种二叉树有个特点：对任意节点而言，左子（当然了，存在的话）的值总是小于本身，而右子（存在的话）的值总是大于本身。这种特性使得我们要查找其中的某个值都很容易，从根开始，小的往左找，大的往右找，不大不小的就是这个节点了；插入一样的道理，从根开始，小的往左，大的往右，直到叶子，就插入，算法比较简单，不一一列了，它们的时间复杂度期望为(logn)。（为什么是“期望”，后面会讲）删除则稍微麻烦点，因为我们删的不一定是叶子，如果只是叶子，那就好办，如果不是呢？我们最通常的做法就是把这个节点往下挪，直到它变为叶子为止，看图。也许你要问，如果和左子树最大节点交换后，要删除的节点依然不是叶子，那怎么办呢？那继续呗，看图：那左子树不存在的情况下呢？你可以查找右子树的最小节点，和上面是类似的，图我就不画了。十一、平衡二叉查找树（AVL）前面说了，二叉查找树方便查找取值插入删除，其复杂度不过为(logn)，但这是个“期望值”，因为我们也有比较差的情况，比如下面这棵树：说是树，其实已经退化为链表了，但从概念上来说它依然是一棵二叉查找树，这棵树怎么形成的呢？很简单，我们只要按着1，2，3，4，5，6，7这样的顺序往一个空的二叉查找树里添加元素，就形成了。这样我们再添加8，9，10那真的就变成了一个链表结构，那插入的复杂度也就变成了(n)。导致这种糟糕的原因是这棵树非常不平衡，右树的重量远大于左树，所以我们提出了一种叫“平衡二叉查找树”的结构，平衡二叉查找树英文叫AVL，而不是我本来以为的什么Balance BST，AVL来自于人名，我这里就不追究了。平衡，顾名思义，就是两边看起来比较对称，但很多时候我们是做不到绝对的对称（绝对对称即对任意子树而言，左右节点的数量都相等），因为只有(2n-1)元素数目的二叉树才能做到绝对对称，所以我们使用了“高度”（height）这么个概念，某节点的高度指的是它离它的子树的叶子的最远距离：那么我再引申出两个概念，左高和右高：左高 = 左节点空 ? 0 : (左节点高+1)右高 = 右节点空 ? 0 : (右节点高+1)那我们就可以给AVL下个定义了，对AVL的任意节点而言：ABS(左高 - 右高) iHeightRight)?(iHeightLeft):(iHeightRight);returniHeight;intTreeNode:GetLeftHeight()if(pLeft!=0)returnpLeft-iHeight+1;elsereturn0;intTreeNode:GetRightHeight()if(pRight!=0)returnpRight-iHeight+1;elsereturn0;intTreeNode:GetDiff()intiHeightLeft=0;intiHeightRight=0;if(pLeft!=0)iHeightLeft=pLeft-iHeight+1;if(pRight!=0)iHeightRight=pRight-iHeight+1;returniHeightLeft-iHeightRight;/Stack/classStackpublic:Stack(intiAmount=10);Stack();/return1meanssucceeded,0Pop(TreeNode*&val);intPush(TreeNode*val);intTop(TreeNode*&val);/iteratorintGetTop(TreeNode*&val);intGetNext(TreeNode*&val);private:TreeNode*m_pData;intm_iCount;intm_iAmount;/iteratorintm_iCurr;Stack:Stack(intiAmount)m_pData=newTreeNode*iAmount;m_iCount=0;m_iAmount=iAmount;m_iCurr=0;Stack:Stack()deletem_pData;intStack:Pop(TreeNode*&val)if(m_iCount0)-m_iCount;val=m_pDatam_iCount;return1;return0;intStack:Push(TreeNode*val)if(m_iCount0&m_iCount0&m_iCount=m_iAmount)val=m_pDatam_iCount-1;m_iCurr=m_iCount-1;return1;return0;intStack:GetNext(TreeNode*&val)if(m_iCurr-1)=0)-m_iCurr;val=m_pDatam_iCurr;return1;return0;/TheQueue/classQueuepublic:Queue(intiAmount=10);Queue();/return0meansfailed,Enqueue(TreeNode*node);intDequeue(TreeNode*&node);private:intm_iAmount;intm_iCount;TreeNode*m_ppFixed;/Tm_iHead;intm_iTail;Queue:Queue(intiAmount)m_iCount=0;m_iAmount=iAmount;m_ppFixed=newTreeNode*iAmount;m_iHead=0;m_iTail=iAmount-1;Queue:Queue()deletem_ppFixed;intQueue:Enqueue(TreeNode*node)if(m_iCountm_iAmount-1)m_iTail=0;m_ppFixedm_iTail=node;+m_iCount;return1;elsereturn0;intQueue:Dequeue(TreeNode*&node)if(m_iCount0)node=m_ppFixedm_iHead;+m_iHead;if(m_iHeadm_iAmount-1)m_iHead=0;-m_iCount;return1;elsereturn0;/AVLTree/classCAVLTreepublic:CAVLTree();CAVLTree();TreeNode*Insert(intiVal);intDelete(intiVal);TreeNode*FindNode(intiVal);/thefindfunction,returns0meansnotfound.#ifdef_DEBUGvoidPrintTree();#endifprotected:/Updatetheheightafterinsertordelete./AndfindtheminimumunbalanceBST.intUpdateHeight(Stack&st,TreeNode*&pMinBST,TreeNode*&pMinBSTParent,int&iLeftRight);/RotatevoidDoBalance(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight);voidLLRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight);voidRRRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight);voidLRRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight,intiSpecialFlag=0);voidRLRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight,intiSpecialFlag=0);voidSwapTwoNodes(TreeNode*pNode1,TreeNode*pNode2);/Swaptheirvalueonly.TreeNode*m_pRoot;CAVLTree:CAVLTree()m_pRoot=NULL;CAVLTree:CAVLTree()Stackst(40);/240mustbeenough./Postordertraversethetreetoreleaseallnodes.TreeNode*pNode=m_pRoot;TreeNode*pTemp;if(pNode=0)return;while(1)if(pNode-pLeft!=0)st.Push(pNode);pTemp=pNode;pNode=pNode-pLeft;pTemp-pLeft=0;continue;if(pNode-pRight!=0)st.Push(pNode);pTemp=pNode;pNode=pNode-pRight;pTemp-pRight=0;continue;deletepNode;if(0=st.Pop(pNode)break;TreeNode*CAVLTree:Insert(intiVal)Stackst(40);/Torecordthepath.TreeNode*pNode=m_pRoot;TreeNode*pIns;intiLeftOrRight;/0meansleft,1meansright.while(1)if(pNode=0)/InsertatthispositionTreeNode*pNew=newTreeNode(iVal);TreeNode*pPrev;if(0!=st.Top(pPrev)if(0=iLeftOrRight)pPrev-pLeft=pNew;elsepPrev-pRight=pNew;else/Therootm_pRoot=pNew;returnm_pRoot;pIns=pNew;if(0=iLeftOrRight&pPrev-pRight!=0|1=iLeftOrRight&pPrev-pLeft!=0)/Neednottochange.returnpIns;break;if(iValiData)st.Push(pNode);pNode=pNode-pLeft;iLeftOrRight=0;elseif(iValpNode-iData)st.Push(pNode);pNode=pNode-pRight;iLeftOrRight=1;elsereturnpNode;TreeNode*pMinBST;TreeNode*pMinBSTParent;intiLRParent;UpdateHeight(st,pMinBST,pMinBSTParent,iLRParent);if(pMinBST!=0)/Itexists.needbalance.DoBalance(pMinBST,pMinBSTParent,iLRParent);returnpIns;/UCAVLTree:UpdateHeight(Stack&st,TreeNode*&pMinBST,TreeNode*&pMinBSTParent,int&iLRParent)TreeNode*pNode;pMinBST=0;pMinBSTParent=0;if(0=st.GetTop(pNode)return0;while(1)pNode-UpdateHeight();intiDiff=pNode-GetDiff();if(iDiff1|iDiffpLeft=pMinBST)iLRParent=0;/leftelseiLRParent=1;/rightreturn0;if(0=st.GetNext(pNode)break;return0;voidCAVLTree:DoBalance(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight)if(pNode-GetLeftHeight()GetRightHeight()if(pNode-pRight-GetLeftHeight()pRight-GetRightHeight()RRRotate(pNode,pMinBSTParent,iLeftRight);elseif(pNode-pRight-GetLeftHeight()pNode-pRight-GetRightHeight()RLRotate(pNode,pMinBSTParent,iLeftRight);elseRLRotate(pNode,pMinBSTParent,iLeftRight,1);elseif(pNode-pLeft-GetLeftHeight()pNode-pLeft-GetRightHeight()LLRotate(pNode,pMinBSTParent,iLeftRight);elseif(pNode-pLeft-GetLeftHeight()pLeft-GetRightHeight()LRRotate(pNode,pMinBSTParent,iLeftRight);elseLRRotate(pNode,pMinBSTParent,iLeftRight,1);/BA/ABR=ALB/+/ALARARBR/+voidCAVLTree:LLRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight)/B,AandALmustbeexist.BRandARmaybenull.TreeNode*pNodeB=pNode;TreeNode*pNodeA=pNodeB-pLeft;TreeNode*pNodeAR=pNodeA-pRight;pNodeA-pRight=pNodeB;pNodeB-pLeft=pNodeAR;/HandletheheightpNodeB-iHeight-=2;if(pMinBSTParent=0)/rootm_pRoot=pNodeA;elseif(iLeftRight=0)/leftpMinBSTParent-pLeft=pNodeA;elsepMinBSTParent-pRight=pNodeA;/AB/ALB=ABR/+/BLBRALBL/+voidCAVLTree:RRRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight)TreeNode*pNodeA=pNode;TreeNode*pNodeB=pNodeA-pRight;TreeNode*pNodeBL=pNodeB-pLeft;pNodeB-pLeft=pNodeA;pNodeA-pRight=pNodeBL;/HandletheheightpNodeA-iHeight-=2;if(pMinBSTParent=0)/rootm_pRoot=pNodeB;elseif(iLeftRight=0)/leftpMinBSTParent-pLeft=pNodeB;elsepMinBSTParent-pRight=pNodeB;/CB/ACRAC/=/ALBALBLBRCR/+/BLBR/+/Specialflagisusedforsomekindofdeleteoperation,forexample:/43/25(-)=24/131voidCAVLTree:LRRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight,intiSpecialFlag)TreeNode*pNodeC=pNode;TreeNode*pNodeA=pNodeC-pLeft;TreeNode*pNodeB=pNodeA-pRight;TreeNode*pNodeBL=pNodeB-pLeft;TreeNode*pNodeBR=pNodeB-pRight;pNodeB-pLeft=pNodeA;pNodeB-pRight=pNodeC;pNodeA-pRight=pNodeBL;pNodeC-pLeft=pNodeBR;/Handletheheightif(iSpecialFlag=0)pNodeA-iHeight-=1;pNodeB-iHeight+=1;elsepNodeB-iHeight+=2;pNodeC-iHeight-=2;if(pMinBSTParent=0)/rootm_pRoot=pNodeB;elseif(iLeftRight=0)/leftpMinBSTParent-pLeft=pNodeB;elsepMinBSTParent-pRight=pNodeB;/BA/BLCBC/=/ACRBLALARCR/+/ALAR/+/Specialflagisusedforsomekindofdeleteoperation,forexample:/34/(-)25=35/466voidCAVLTree:RLRotate(TreeNode*pNode,TreeNode*pMinBSTParent,intiLeftRight,intiSpecialFlag)TreeNode*pNodeB=pNode;TreeNode*pNodeC=pNodeB-pRight;TreeNode*pNodeA=pNodeC-pLeft;TreeNode*pNodeAL=pNodeA-pLeft;TreeNode*pNodeAR=pNodeA-pRight;pNodeA-pLeft=pNodeB;pNodeA-pRight=pNodeC;pNodeC-pLeft=pNodeAR;pNodeB-pRight=pNodeAL;/Handletheheightif(iSpecialFlag=0)pNodeC-iHeight-=1;pNodeA-iHeight+=1;elsepNodeA-iHeight+=2;pNodeB-iHeight-=2;if(pMinBSTParent=0)/rootm_pRoot=pNodeA;elseif(iLeftRight=0)/leftpMinBSTParent-pLeft=pNodeA;elsepMinBSTParent-pRight=pNodeA;intCAVLTree:Delete(intiVal)if(m_pRoot=0)return0;Stackst(40);/Torecordthepath.TreeNode*pNode=m_pRoot;TreeNode*pPrev;intiLeftOrRight;/0meansleft,1meansright.while(1)if(pNode-iData=iVal)/Yes,itis.st.Push(pNode);break;if(iValiData)st.Push(pNode);if(pNode-pLeft!=0)pNode=pNode-pLeft;elsereturn0;iLeftOrRight=0;else/iValpNode-iDatast.Push(pNode);if(pNode-pRight!=0)pNode=pNode-pRight;elsereturn0;iLeftOrRight=1;intiLeafLeftRight;if(pNode-iHeight=0)/Itistheleafnode.if(0!=st.GetTop(pPrev)iLeafLeftRight=iLeftOrRight;else/Theroot,thistreeisgoingtobenull.deletem_pRoot;m_pRoot=0;return0;elseif(pNode-pLeft!=NULL)iLeafLeftRight=0;/Movethisnodetothebottom.TreeNode*pBiggestLeft=pNode-pLeft;st.Push(pBiggestLeft);while(pBiggestLeft-pRight!=NULL)pBiggestLeft=pBiggestLeft-pRight;st.Push(pBiggestLeft);iLeafLeftRight=1;SwapTwoNodes(pBiggestLeft,pNode);if(pBiggestLeft-pLeft!=NULL)SwapTwoNodes(pBiggestLeft,pBiggestLeft-pLeft);st.Push(pBiggestLeft-pLeft);iLeafLeftRight=0;else/pNode-pRight!=NULLiLeafLeftRight=1;/Movethisnodetothebottom.TreeNode*pLeastRight=pNode-pRight;st.Push(pLeastRight);while(pLeastRight-pLeft!=NULL)pLeastRight=pLeastRight-pLeft;st.Push(pLeastRight);iLeafLeftRight=0;SwapTwoNodes(pLeastRight,pNode);if(pLeastRight-pRight!=NULL)SwapTwoNodes(pLeastRight,pLeastRight-pRight);st.Push(pLeastRight-pRight);iLeafLeftRight=1;/Deletetheleaf.TreeNode*pToDel;st.Pop(pToDel);deletepToDel;TreeNode*pToChange;st.GetTop(pToChange);if(iLeafLeftRight=0)pToChange-pLeft=0;elsepToChange-pRight=0;TreeNode*pM