【正文】 eturn(r)。}要?jiǎng)h除二叉排序樹(shù)中的 p結(jié)點(diǎn)，分三種情況：? p為葉子結(jié)點(diǎn)，只需修改 p雙親 f的指針 flchild=NULL frchild=NULL? p只有左子樹(shù)或右子樹(shù)–p只有左子樹(shù)，用 p的左孩子代替 p (1)(2)–p只有右子樹(shù)，用 p的右孩子代替 p (3)(4)? p左、右子樹(shù)均非空– 沿 p左子樹(shù)的根 C的右子樹(shù)分支找到 S， S的右子樹(shù)為空，將 S的左子樹(shù)成為 S的雙親 Q的右子樹(shù)，用 S取代 p (5)–若 C無(wú)右子樹(shù)，用 C取代 p (6)二叉排序樹(shù)的刪除SQPLP中序遍歷： Q S PL PSQ PL中序遍歷： Q S PL(2)SPPLQ中序遍歷： PL P S QSPL Q中序遍歷： PL S Q(1)中序遍歷： P PR S QSPR Q中序遍歷： PR S Q(3)SPPRQ中序遍歷： Q S P PRSQ PR中序遍歷： Q S PR(4)SQPRPFPC PRCL L SSL中序遍歷： CL C ……Q L Q SL S P PR FFSC PRCL L SL中序遍歷： CL C ……Q L Q SL S PR F(5)FPC PRCL中序遍歷： CL C P PR FFCPRCL中序遍歷： CL C PR F(6)例 8050 12060 110 15055 7053刪除 508060 120110 15055 7053刪除 608055 120110 15053 70104 258 1354刪除 1084 255 134刪除 584 254 13刪除算法JD *delnode(JD *r,JD *p,JD *f){ JD *q,*s。 int flag=0。 if(plchild==NULL) s=prchild。 else if(prchild==NULL) s=plchild。 else{ ……… } 刪除算法 : q=p。 s=plchild。 while(srchild!=NULL) { q=s。 s=srchild。 } pdata=sdata。 if(q==p) qlchild=slchild。 else qrchild=slchild。 free(s)。 flag=1。FPC PRCL L SSLFPC PRCLif(flag==0) { if(f==NULL) r=s。 else if(flchild==p) flchild=s。 else frchild=s。 free(p)。 } return(r)。}查找性能的分析： 對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它的ASL值，顯然，由值相同的 n個(gè)關(guān)鍵字構(gòu)造所得的，不同形態(tài)的各棵二叉排序樹(shù)的平均查找長(zhǎng)度的值不同，甚至可能差別很大例如： 由關(guān)鍵字序列 1， 2， 3， 4， 5構(gòu)造而得的二叉排序樹(shù) ASL =（ 1+2+3+4+5） / 5 = 3 由關(guān)鍵字序列 3， 1， 2， 5， 4構(gòu)造而得的二叉排序樹(shù) ASL =（ 1+2+3+2+3） / 5 = 一般情況下，考慮含有 n個(gè)關(guān)鍵字可能出現(xiàn)的 n!種序列出現(xiàn)的可能性相等。 不失一般性，假設(shè)某個(gè)序列中有 k個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，即有 nk1個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字，由它構(gòu)造的二叉排序樹(shù)的平均查找長(zhǎng)度是 n和k的函數(shù) P(n, k)(0≤k≤n1)則含 n個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度 而在等概率的情況下，由此可類(lèi)似于解差分方程，此遞歸方程有解：從查找的角度看，希望由任意序列生成的二叉排序樹(shù)，其左、右子樹(shù)的深度近似相等，但實(shí)際上有 47%的情況生成的二叉排序樹(shù)非如此。 平衡二叉樹(shù)? 起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。 DGEDABCFEGBAC F? 平衡因子（平衡度）： 結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹(shù)的高度－右子樹(shù)的高度。? 平衡二叉樹(shù)： 每個(gè)結(jié)點(diǎn)的平衡因子都為 ＋ － 0 的二叉樹(shù)?；蛘哒f(shuō)每個(gè) 結(jié)點(diǎn)的左右子樹(shù)的高度最多差一的二叉樹(shù)。? 平衡二叉排序樹(shù)的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡二叉排序樹(shù)中插入數(shù)據(jù)場(chǎng)為 2的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡二叉排序樹(shù)的性質(zhì)不變。1412539 286353605017187 30+1+11110000000 0平衡樹(shù)1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹(shù)的性質(zhì)不變？? 平衡二叉排序樹(shù)的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡二叉排序樹(shù)中插入數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡二叉排序樹(shù)的性質(zhì)不變。原平衡度為 01412539 286353605017187 30+1+11110000000 02+1+1+2危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹(shù)的性質(zhì)不變？解決方案：?不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹(shù)的高度應(yīng)保持不變（左圖為 3 ）。?新結(jié)點(diǎn)插入后，找到第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（如左圖結(jié)點(diǎn) ）即可。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為 0?在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如： ），其它結(jié)點(diǎn)不予調(diào)整。?仍應(yīng)保持二叉樹(shù)排序樹(shù)的性質(zhì)不變。93 5 9? 平衡二叉排序樹(shù)的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡樹(shù)中 插入 數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡二叉排序樹(shù)的性質(zhì)不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹(shù)的性質(zhì)不變？2 3 5 97 1223597 12不可以以結(jié)點(diǎn) 為子樹(shù)的根結(jié)點(diǎn)??！雖然，對(duì)本例來(lái)說(shuō)是可以行得通的。7? 平衡二叉排序樹(shù)的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡二叉排序樹(shù)中插入數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡二叉排序樹(shù)的性質(zhì)不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)關(guān)鍵：將導(dǎo)致出現(xiàn) 危機(jī)結(jié)點(diǎn)的情況 全部分析清除，就可以使得平衡二叉排序樹(shù)的性質(zhì)保持不變！！149325 286353605017187 30+1+1 1110000000120 0? 左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析： LL 情況：（ LL： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 左子樹(shù) 的 左子樹(shù)上 ）AB+1h10+2+1h h1h1 LL 改組BL BRARBA0h0h1h1BLBR AR危機(jī)結(jié)點(diǎn)改組前：高度為 h + 1 中序序列： ABBL BR AR改組后：高度為 h + 1 中序序列： ABBL BR AR注意：改組后 平衡度為 0AB? 左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 左子樹(shù) 的 右子樹(shù)上 ） 情況 A：AB+1h10+21h1 LR 改組BLAR危機(jī)結(jié)點(diǎn)改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 0,0,1CBCCL CR h2h2h10+1CB0h1 h1BL ARACR h2CLh110ABBL ARCCL CR改組后： 高度為 h + 1 中序序列：ABBL ARCCL CRA? 左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 左子樹(shù) 的 右子樹(shù)上 ） 情況 B：AB+1h10+21h1 LR 改組BLAR危機(jī)結(jié)點(diǎn)改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 +1,0,0CBCCRCL h1h2h201CB0h1 h1BL ARACR h1CLh2+1 0ABBL ARC CRCL改組后： 高度為 h + 1 中序序列：AABBL ARC CRCL? 左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹(shù)上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 左子樹(shù) 的 右子樹(shù)上 ） 情況 C：AB+10+21LR 改組危機(jī)結(jié)點(diǎn)改組前： 高度為 2 中序序列：注意：改組后 平衡度為 0,0,0CBC0AB CA新插入結(jié)點(diǎn)AB C改組后： 高度為 2 中序序列：CB0A0 0? 四種情況的區(qū)分： 如果 的平衡度為＋ 1 則為 LL型改組； 否則為 LR型改組：若 的平衡度為＋ － 1 、 0 ；則分別為 LRA、 LRB、 LRC型改組。BC? 右改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的右子樹(shù)上進(jìn)行的調(diào)整）的情況分析： RR 情況：（ RR： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 右子樹(shù) 的 右子樹(shù)上 ） 處理圖形和 LL 鏡象相似