【正文】 eturn(r)。}要刪除二叉排序樹中的 p結點，分三種情況：? p為葉子結點，只需修改 p雙親 f的指針 flchild=NULL frchild=NULL? p只有左子樹或右子樹–p只有左子樹，用 p的左孩子代替 p (1)(2)–p只有右子樹，用 p的右孩子代替 p (3)(4)? p左、右子樹均非空– 沿 p左子樹的根 C的右子樹分支找到 S， S的右子樹為空，將 S的左子樹成為 S的雙親 Q的右子樹，用 S取代 p (5)–若 C無右子樹，用 C取代 p (6)二叉排序樹的刪除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)。}查找性能的分析： 對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的 n個關鍵字構造所得的，不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大例如： 由關鍵字序列 1， 2， 3， 4， 5構造而得的二叉排序樹 ASL =（ 1+2+3+4+5） / 5 = 3 由關鍵字序列 3， 1， 2， 5， 4構造而得的二叉排序樹 ASL =（ 1+2+3+2+3） / 5 = 一般情況下，考慮含有 n個關鍵字可能出現(xiàn)的 n!種序列出現(xiàn)的可能性相等。 不失一般性，假設某個序列中有 k個關鍵字小于第一個關鍵字，即有 nk1個關鍵字大于第一個關鍵字，由它構造的二叉排序樹的平均查找長度是 n和k的函數(shù) P(n, k)(0≤k≤n1)則含 n個關鍵字的二叉排序樹的平均查找長度 而在等概率的情況下，由此可類似于解差分方程，此遞歸方程有解：從查找的角度看，希望由任意序列生成的二叉排序樹，其左、右子樹的深度近似相等，但實際上有 47%的情況生成的二叉排序樹非如此。 平衡二叉樹? 起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。 DGEDABCFEGBAC F? 平衡因子（平衡度）： 結點的平衡度是結點的左子樹的高度－右子樹的高度。? 平衡二叉樹： 每個結點的平衡因子都為 ＋ － 0 的二叉樹?；蛘哒f每個 結點的左右子樹的高度最多差一的二叉樹。? 平衡二叉排序樹的 Adelson 算法的本質特點：? 以插入為例： 在左圖所示的平衡二叉排序樹中插入數(shù)據(jù)場為 2的結點。 插入之后仍應保持平衡二叉排序樹的性質不變。1412539 286353605017187 30+1+11110000000 0平衡樹1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機結點如何用最簡單、最有效的辦法保持平衡二叉排序樹的性質不變？? 平衡二叉排序樹的 Adelson 算法的本質特點：? 以插入為例： 在左圖所示的平衡二叉排序樹中插入數(shù)據(jù)場為 2 的結點。 插入之后仍應保持平衡二叉排序樹的性質不變。原平衡度為 01412539 286353605017187 30+1+11110000000 02+1+1+2危機結點如何用最簡單、最有效的辦法保持平衡二叉排序樹的性質不變？解決方案：?不涉及到危機結點的父親結點，即以危機結點為根的子樹的高度應保持不變（左圖為 3 ）。?新結點插入后，找到第一個平衡度不為 0 的結點（如左圖結點 ）即可。新插入的結點和第一個平衡度不為 0 的結點（也可能是危機結點）之間的結點，其平衡度皆為 0?在調整中，僅調整那些在平衡度變化的路徑上的結點（如： ），其它結點不予調整。?仍應保持二叉樹排序樹的性質不變。93 5 9? 平衡二叉排序樹的 Adelson 算法的本質特點：? 以插入為例： 在左圖所示的平衡樹中 插入 數(shù)據(jù)場為 2 的結點。 插入之后仍應保持平衡二叉排序樹的性質不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機結點如何用最簡單、最有效的辦法保持平衡二叉排序樹的性質不變？2 3 5 97 1223597 12不可以以結點 為子樹的根結點??！雖然，對本例來說是可以行得通的。7? 平衡二叉排序樹的 Adelson 算法的本質特點：? 以插入為例： 在左圖所示的平衡二叉排序樹中插入數(shù)據(jù)場為 2 的結點。 插入之后仍應保持平衡二叉排序樹的性質不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機結點關鍵：將導致出現(xiàn) 危機結點的情況 全部分析清除，就可以使得平衡二叉排序樹的性質保持不變?。?49325 286353605017187 30+1+1 1110000000120 0? 左改組（新插入結點出現(xiàn)在危機結點的左子樹上進行的調整）的情況分析： LL 情況：（ LL： 表示新插入結點在危機結點的 左子樹 的 左子樹上 ）AB+1h10+2+1h h1h1 LL 改組BL BRARBA0h0h1h1BLBR AR危機結點改組前：高度為 h + 1 中序序列： ABBL BR AR改組后：高度為 h + 1 中序序列： ABBL BR AR注意：改組后 平衡度為 0AB? 左改組（新插入結點出現(xiàn)在危機結點的左子樹上進行的調整）的情況分析： LR 情況：（ LR： 表示新插入結點在危機結點的 左子樹 的 右子樹上 ） 情況 A：AB+1h10+21h1 LR 改組BLAR危機結點改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 0,0,1CBCCL CR h2h2h10+1CB0h1 h1BL ARACR h2CLh110ABBL ARCCL CR改組后： 高度為 h + 1 中序序列：ABBL ARCCL CRA? 左改組（新插入結點出現(xiàn)在危機結點的左子樹上進行的調整）的情況分析： LR 情況：（ LR： 表示新插入結點在危機結點的 左子樹 的 右子樹上 ） 情況 B：AB+1h10+21h1 LR 改組BLAR危機結點改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 +1,0,0CBCCRCL h1h2h201CB0h1 h1BL ARACR h1CLh2+1 0ABBL ARC CRCL改組后： 高度為 h + 1 中序序列：AABBL ARC CRCL? 左改組（新插入結點出現(xiàn)在危機結點的左子樹上進行的調整）的情況分析： LR 情況：（ LR： 表示新插入結點在危機結點的 左子樹 的 右子樹上 ） 情況 C：AB+10+21LR 改組危機結點改組前： 高度為 2 中序序列：注意：改組后 平衡度為 0,0,0CBC0AB CA新插入結點AB C改組后： 高度為 2 中序序列：CB0A0 0? 四種情況的區(qū)分： 如果 的平衡度為＋ 1 則為 LL型改組； 否則為 LR型改組：若 的平衡度為＋ － 1 、 0 ；則分別為 LRA、 LRB、 LRC型改組。BC? 右改組（新插入結點出現(xiàn)在危機結點的右子樹上進行的調整）的情況分析： RR 情況：（ RR： 表示新插入結點在危機結點的 右子樹 的 右子樹上 ） 處理圖形和 LL 鏡象相似