基于樹的查找算法第九章主講：周翔二叉排序樹（二叉查找樹）二叉排序樹（BinarySortTree）又稱為二叉查找樹、二叉搜索樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）如果左子樹不為空，則左子樹上所有結(jié)點的值均小于它根結(jié)點的值；（2）如果右子樹不為空，則右子樹上所有結(jié)點的值均大于它根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；（4）樹中沒有值相同的結(jié)點；二叉排序樹（二叉查找樹）圖例二叉排序樹（二叉查找樹）結(jié)構(gòu)定義dataleftChildrightChild二叉排序樹（二叉查找樹）二叉排序樹的插入二叉排序樹的查找二叉排序樹的刪除二叉排序樹（二叉查找樹）二叉排序樹的插入已知一關(guān)鍵字值為key的結(jié)點S：若二叉樹是空樹，則S成為二叉排序樹的根；若二叉樹非空，則將S.key與二叉排序樹根結(jié)點的關(guān)鍵字進行比較：if(key的值等于根結(jié)點的值)，則停止插入；elseif(key的值小于根結(jié)點的值)，則將S插入左子樹；elseif(key的值大于根結(jié)點的值)，則將S插入右子樹。二叉排序樹（二叉查找樹）輸入數(shù)據(jù)，反復執(zhí)行二叉排序樹的插入過程輸入數(shù)據(jù){53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981二叉排序樹（二叉查找樹）新結(jié)點作為葉結(jié)點插入例如：插入新結(jié)點2835154550402510203028時間復雜度為：O(log2n)二叉排序樹（二叉查找樹）創(chuàng)建：創(chuàng)建過程實質(zhì)上就是反復執(zhí)行插入的過程輸入數(shù)據(jù){53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981時間復雜度為：O(nlog2n)二叉排序樹（二叉查找樹）n個結(jié)點，按不同的輸入順序組成二叉排序樹最短的二叉排序樹高度是？最長的二叉排序樹高度是？log2n(取下整數(shù))＋1n二叉排序樹（二叉查找樹）二叉排序樹的查找根據(jù)二叉排序樹的特點首先將待查關(guān)鍵字key與根結(jié)點關(guān)鍵字t進行比較，如果：key=t：則返回根結(jié)點地址；key<t：則進一步查左子樹；key>t：則進一步查右子樹。二叉排序樹（二叉查找樹）351545504025102030搜索28搜索45搜索失敗搜索成功圖例二叉排序樹（二叉查找樹）二叉排序樹的查找：平均查找長度（ASL）若查找成功，則是從根結(jié)點出發(fā)走了一條從根結(jié)點到待查結(jié)點的路徑若查找不成功，則是從根結(jié)點出發(fā)走了一條從根到某個葉子結(jié)點的路徑所以，二叉排序樹的查找與折半查找過程類似，查找長度與樹的高度有關(guān)?。。《媾判驑洌ǘ娌檎覙洌┒媾判驑涞牟檎遥鹤顗那闆r：二叉排序樹是把一個有序表的n個結(jié)點依次插入生成的，由此得到一棵深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，是二叉排序樹（二叉查找樹）二叉排序樹的查找：最好情況：得到的是一棵形態(tài)與二分查找的判定樹相似的二叉排序樹，此時它的平均查找長度大約是二叉排序樹（二叉查找樹）與折半查找的比較區(qū)別：折半查找對應(yīng)的判定樹是惟一的，而二叉排序樹卻不是?。?！折半查找采用順序存儲結(jié)構(gòu)，作插入、刪除時，需移動大量元素；而二叉排序樹則不需要。二叉排序樹（二叉查找樹）二叉排序樹的刪除：從二叉排序樹中刪除一個結(jié)點，不能把以該結(jié)點為根的子樹都刪去，只能刪掉該結(jié)點，并且保證刪除后所得的二叉樹仍然滿足二叉排序樹的性質(zhì)不變。二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：若刪除結(jié)點不在二叉排序樹中，則不做任何操作。否則，假設(shè)要刪除的結(jié)點為p，結(jié)點p的雙親結(jié)點為f，并假設(shè)結(jié)點p是結(jié)點f的左孩子（右孩子的情況類似），分三種情況討論：若p為葉結(jié)點若p只有左子樹（或只有右子樹）p既有左子樹，又有右子樹二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：若p為葉結(jié)點：則可直接刪除537865091787pf5378651787二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：若p只有左子樹（或只有右子樹），可將p的左子樹（或右子樹）直接改為其雙親結(jié)點f的左子樹只有左子樹：只有右子樹：537865091787pf5378650987二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：p既有左子樹，又有右子樹方法1：找到p結(jié)點在中序序列中的前驅(qū)結(jié)點s，將p的左子樹改為f的左子樹，將p的右子樹改為s的右子樹：二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：將p的左子樹改為f的左子樹將p的右子樹改為s的右子樹53786587sp173040091215055378650917873040121505二叉排序樹（二叉查找樹）二叉排序樹的刪除的算法思想：p既有左子樹，又有右子樹方法2：找到p結(jié)點在中序序列中的前驅(qū)結(jié)點s，用s的值替代p結(jié)點的值，將s刪除，原s的左子樹改為s的雙親結(jié)點q的右子樹。537865091787304012150515sfq5378650917873040121505psfqp12二叉排序樹（二叉查找樹）二叉排序樹（二叉查找樹）總結(jié)：二叉排序樹的查找與折半查找過程類似，查找長度與樹的高度有關(guān)??！因此，控制二叉排序樹的高度在比較低的狀態(tài)，對查找比較有利！平衡二叉排序樹（AV樹）1989奧斯卡是最佳短片獎--《Balance》世界需要平衡，破壞平衡的一方，也許會一時很強勢的稱霸，最終的結(jié)局逃不過孤立和落空平衡二叉排序樹（AV樹）定義：平衡二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：左子樹與右子樹的深度之差的絕對值小于等于1；左子樹和右子樹也是平衡二叉排序樹；平衡二叉排序樹（AV樹）性質(zhì)：

1：含有n個結(jié)點的AV樹的高度為O(log2n)；2：在含有n個結(jié)點的AV樹中搜索一個元素需要為O(log2n)時間；3：將一個新元素插入一棵n個結(jié)點的AV樹中，可得到一棵n+1個結(jié)點的AV樹，且插入所需的時間為O(log2n)；4：從一棵n個結(jié)點的AVL樹刪除一個元素，可得到一棵n-1個結(jié)點的AV樹，且刪除所需的時間為O(log2n)；平衡二叉排序樹（AV樹）結(jié)點的平衡因子——BF定義：結(jié)點左子樹深度與右子樹深度之差。AV樹任一結(jié)點平衡因子只能取-1,0,1如果一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉排序樹就失去了平衡，不再是AV樹。平衡二叉排序樹（AV樹）寫出以下二叉樹各結(jié)點的平衡因子值：左子樹的深度－右子樹的深度是平衡二叉排序樹0351545504025102030000-10001平衡二叉排序樹（AV樹）寫出以下二叉樹各結(jié)點的平衡因子值：不是平衡二叉搜索樹010-10-2000351545504025102030282平衡二叉排序樹（AV樹）以插入為例：如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)（LL旋轉(zhuǎn)和RR旋轉(zhuǎn)）雙旋轉(zhuǎn)（LR旋轉(zhuǎn)和RL旋轉(zhuǎn)）平衡二叉排序樹（AV樹）輸入關(guān)鍵碼序列為

{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下：平衡二叉排序樹（AV樹）160163100-12LR雙旋731600001-1731116012右單旋0-1-1-2-2163737112691673161190037169000-111000平衡二叉排序樹（AV樹）1-2RL雙旋011左單旋1816000732611900031609-171126-11837161426911118261673911平衡二叉排序樹（AV樹）LR雙旋18730011116150-12614915318162071491126-1從空樹開始的建平衡二叉排序樹的過程B樹B樹是為磁盤或其他外存設(shè)備而設(shè)計的一種多叉平衡查找樹，因此它也叫多路平衡查找樹，在讀取外存文件時許多數(shù)據(jù)庫系統(tǒng)都使用B樹或者B樹的各種變形結(jié)構(gòu)，如B+樹，B*樹。B樹一棵m階的B樹（注意m階的樹并不是簡單的有m個叉樹）或者是一棵空樹，或者在定義中要滿足以下要求：（1）樹中每個結(jié)點最多有m棵子樹（m>=2）；（2）根結(jié)點至少有兩個子結(jié)點；（空樹除外）（3）除根結(jié)點外，結(jié)點中關(guān)鍵字的個數(shù)取值范圍為(m/2)-1到m-1；（m/2向上取整）；（4）所有葉子結(jié)點都在同一層；（5）除根結(jié)點和葉子結(jié)點外，如果結(jié)點有k-1個關(guān)鍵字，那么這個結(jié)點就有k個子結(jié)點，關(guān)鍵字按遞增次序排列；B樹18331248233010152021243145475051B樹在B樹中查找數(shù)據(jù)主要分為兩步：（1）把根結(jié)點讀出來，在根結(jié)點所包含的關(guān)鍵字k1、k2….kj中查找給定的關(guān)鍵字值（當結(jié)點包含的關(guān)鍵字值不多時，可用順序查找；當結(jié)點包含的關(guān)鍵字數(shù)目較多時可用折半查找），找到則查找成功；（2）否則，確定要查找的關(guān)鍵字值的大小范圍，根據(jù)指針指向的子結(jié)點，在子結(jié)點中繼續(xù)查找。如果查找到葉子結(jié)點仍未找到，表示查找失敗。B樹在此B樹中查找值31：1833124823301015202124314547505118<31<33查找18~33范圍的子結(jié)點B樹在此B樹中查找值31：1833124823301015202124314547505118<31<33查找18~33范圍的子結(jié)點在子結(jié)點中31>30，查找最右邊的結(jié)點找到值31B樹在B樹中插入：在B樹中插入元素時，首先要確定此元素在B樹中是否存在，如果不存在則在合適位置插入，否則不能插入，因為B樹中不允許有重復值。在插入時，如果要插入的結(jié)點空間足夠，即結(jié)點中的關(guān)鍵字數(shù)量沒有達到最大，則可順利插入；B樹在此B樹中插入元素11：1833124823301015202124314547505111<1811<12且結(jié)點有足夠空間11B樹在此B樹中插入元素11：1833111248233010152021243145475051B樹在B樹中插入：如果要插入的結(jié)點空間不足，則將結(jié)點進行“分裂”，將一半數(shù)量的關(guān)鍵字分裂到新的相鄰右結(jié)點中，中間關(guān)鍵字則上移到父結(jié)點中（如果父結(jié)點空間也不足，需要繼續(xù)“分裂”），同時若結(jié)點中關(guān)鍵字向右移動，相關(guān)的指針也需要向右移動。B樹在此B樹中插入元素54：1833111248233010152021243145475051B樹在此B樹中插入元素54：183311124851233010152021243145475054B+樹和B*樹B+樹：B樹的一種變形，一棵m階的B+樹與一棵m階的B樹的差異在于：（1）有k個子結(jié)點的B+樹中含有