數(shù)據(jù)結(jié)構(gòu)主講人：石云常州信息職業(yè)技術(shù)學(xué)院7.3動態(tài)查找動態(tài)查找是指在查找過程中，還會對查找表進(jìn)行添加或刪除數(shù)據(jù)元素等操作。若查找表采用線性存儲結(jié)構(gòu)，無論是順序存儲還是鏈?zhǔn)酱鎯Γ瑒討B(tài)查找時其效率都不高。若要獲得高效率的動態(tài)查找，可采用幾種特殊的二叉樹作為查找表的組織形式，在此將它們統(tǒng)稱為樹表。本節(jié)將討論在這些樹表上進(jìn)行查找和修改操作的方法。引言IntroductionPart01二叉排序樹二叉排序樹的定義二叉排序樹若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值。若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。左、右子樹也分別是一棵二叉排序樹。二叉排序樹（BinarySortTree）也稱為二叉查找樹，它或者是一棵空樹，或具有以下性質(zhì)的二叉樹：二叉排序樹的定義二叉排序樹16862619332393010312右邊的二叉排序樹中序遍歷后，其結(jié)果是？答：36891012161923263033小結(jié)二叉排序樹的一個重要性質(zhì)：若中序遍歷一棵二叉樹，可以得到一個結(jié)點(diǎn)值遞增的有序序列。二叉排序樹的定義二叉排序樹以二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)，二叉鏈表結(jié)點(diǎn)的類型定義如下：public

classBiTNode<RecT>{publicRecTdata;//結(jié)點(diǎn)的數(shù)據(jù)元素publicBiTNode<RecT>lchild,rchild;//結(jié)點(diǎn)的左右孩子//構(gòu)造函數(shù)publicBiTNode(RecTdata,BiTNode<RecT>lchild,BiTNode<RecT>rchild){this.data=data;this.lchild=lchild;this.rchild=rchild;}}若二叉排序樹為空，則查找失敗。若二叉排序樹非空，將給定關(guān)鍵字kx與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：若相等，則查找成功，結(jié)束查找；若給定關(guān)鍵字kx小于根結(jié)點(diǎn)的關(guān)鍵字，則遞歸查找左子樹；若給定關(guān)鍵字kx大于根結(jié)點(diǎn)的關(guān)鍵字，則遞歸查找右子樹。二叉排序樹的查找算法思想二叉排序樹二叉排序樹的遞歸查找算法描述二叉排序樹/***在二叉排序樹中查找關(guān)鍵字為kx的結(jié)點(diǎn)*如果找到返回結(jié)點(diǎn)，否則返回null*/public

staticBiTNode<RecT>searchNode(BiTNode<RecT>t,Tkx){//若子樹是空子樹或子樹根結(jié)點(diǎn)的關(guān)鍵字等于kx,返回tif(t==null||t.data.key.equals(kx)){ return

t;}else

if(kx.compareTo(t.data.key)<0){//關(guān)鍵字小于當(dāng)前子樹的根結(jié)點(diǎn)的關(guān)鍵字return

searchNode(t.lchild,kx);//在左子樹繼續(xù)查找}else{return

searchNode(t.rchild,kx);//在右子樹繼續(xù)查找}}二叉排序樹的查找算法分析二叉排序樹二叉排序樹的平均查找長度與樹的形態(tài)有關(guān)。最好的情況是二叉排序樹形態(tài)比較對稱，此時它與折半查找相似，算法的時間復(fù)雜度約為O(log2n)；最壞的情況是二叉排序樹是一棵單支樹（只有左子樹或只有右子樹）,其算法的時間復(fù)雜度是O(n)。小結(jié)查找過程中和關(guān)鍵字比較的次數(shù)不超過樹的深度。16862619332393010312示例：查找關(guān)鍵字10、35的數(shù)據(jù)元素過程10查找失敗若二叉排序樹為空，則為待插入的結(jié)點(diǎn)創(chuàng)建一個新結(jié)點(diǎn)，并使其為根結(jié)點(diǎn)。若二叉排序樹不為空，則將待插入結(jié)點(diǎn)關(guān)鍵字kx與當(dāng)前子樹的根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較。關(guān)鍵字kx小于根結(jié)點(diǎn)的關(guān)鍵字，則將待插入結(jié)點(diǎn)插入到左子樹中；關(guān)鍵字kx大于根結(jié)點(diǎn)的關(guān)鍵字，則將待插入結(jié)點(diǎn)插入到右子樹中；關(guān)鍵字kx等于根結(jié)點(diǎn)的關(guān)鍵字，則說明樹中已有此關(guān)鍵字，無需再插入。子樹中的插入與上述過程一樣，如此遞歸下去，直到待插入結(jié)點(diǎn)作為一個新的葉子結(jié)點(diǎn)插入到樹中或發(fā)現(xiàn)樹中有此關(guān)鍵字為止。二叉排序樹的插入算法思想二叉排序樹二叉排序樹示例：假設(shè)待查關(guān)鍵字序列(45,24,53,45,12,24,90)已存在已存在4524125390二叉排序樹的插入算法描述二叉排序樹//在二叉排序樹t中插入關(guān)鍵字為kx的結(jié)點(diǎn)public

staticBiTNode<RecT>insertNode(BiTNode<RecT>t,Tkx){if(t==null){//空樹的場合,返回根結(jié)點(diǎn) t=createNode(kx);}else{if(kx.compareTo(t.data.key)<0){//添加的結(jié)點(diǎn)關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字if(t.lchild==null){//當(dāng)前根結(jié)點(diǎn)的左子樹是null t.lchild=createNode(kx);}else{ insertNode(t.lchild,kx);//遞歸的向左子樹}}else

if(kx.compareTo(t.data.key)>0){//添加的結(jié)點(diǎn)關(guān)鍵字大于根結(jié)點(diǎn)的關(guān)鍵字if(t.rchild==null){//當(dāng)前根結(jié)點(diǎn)的右子樹是null t.rchild=createNode(kx);}else{ insertNode(t.rchild,kx);//遞歸的向右子樹添加}}else

{//添加的結(jié)點(diǎn)關(guān)鍵字在二叉樹中已存在，無需插入 System.out.println("kx已存在無需插入");}}return

t;}//創(chuàng)建關(guān)鍵字為kx的結(jié)點(diǎn)public

staticBiTNode<RecT>createNode(Tkx){RecTdata=newRecT();data.key=kx;BiTNode<RecT>node=newBiTNode<RecT>(data,null,null);return

node;}在二叉排序樹中刪除一個結(jié)點(diǎn)，首先要找到該結(jié)點(diǎn)。若查找失敗，則無法刪除。查找成功時，為了保證刪除結(jié)點(diǎn)后，繼續(xù)保持二叉排序樹的特性。根據(jù)結(jié)點(diǎn)所在的位置，刪除操作可分為以下三種情況。（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)；（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。二叉排序樹的刪除算法思想二叉排序樹二叉排序樹的刪除算法思想二叉排序樹刪除葉子結(jié)點(diǎn)16862619332393010312父結(jié)點(diǎn)10的lchild=null刪除葉子結(jié)點(diǎn)，其過程如下：找到要刪除的結(jié)點(diǎn)targetNode;找到targetNode的父結(jié)點(diǎn)parent；確定targetNode是parent的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)，若是左子結(jié)點(diǎn)，則parent.lchild=null;否則，parent.rchild=null。二叉排序樹的刪除算法思想二叉排序樹刪除只有一棵左子樹的結(jié)點(diǎn)1686261933233010312父結(jié)點(diǎn)8的lchild指向結(jié)點(diǎn)3父結(jié)點(diǎn)26的rchild指向結(jié)點(diǎn)30刪除只有左子樹的結(jié)點(diǎn)，其過程如下：找到要刪除的結(jié)點(diǎn)targetNode;找到targetNode的父結(jié)點(diǎn)parent；如果targetNode是parent的左子結(jié)點(diǎn)，parent.lchild=targetNode.lchild，否則，parent.rchild=targetNode.lchild。二叉排序樹的刪除算法思想二叉排序樹刪除只有一棵右子樹的結(jié)點(diǎn)1683261930231012父結(jié)點(diǎn)8的rchild指向結(jié)點(diǎn)12父結(jié)點(diǎn)26的lchild指向結(jié)點(diǎn)23刪除只有右子樹的結(jié)點(diǎn)，其過程如下：找到要刪除的結(jié)點(diǎn)targetNode;找到targetNode的父結(jié)點(diǎn)parent；如果targetNode是parent的左子結(jié)點(diǎn)，parent.lchild=targetNode.rchild，否則，parent.rchild=targetNode.rchild。二叉排序樹的刪除算法思想二叉排序樹刪除有兩棵子樹的結(jié)點(diǎn)168326233012結(jié)點(diǎn)12替換結(jié)點(diǎn)8，并刪除結(jié)點(diǎn)12刪除有兩棵子樹的結(jié)點(diǎn)，其過程如下：找到要刪除的結(jié)點(diǎn)targetNode;找到targetNode的父結(jié)點(diǎn)parent；targetNode右子樹中最小的結(jié)點(diǎn)替換targetNode，并刪除該結(jié)點(diǎn)。12二叉排序樹的刪除算法描述二叉排序樹//在二叉排序樹t中刪除關(guān)鍵字為kx的結(jié)點(diǎn)，返回刪除結(jié)點(diǎn)后的樹public

staticBiTNode<RecT>deleteNode(BiTNode<RecT>t,Tkx){if(t==null){//空樹的場合，返回null return

null;}else{//1.找到要刪除的結(jié)點(diǎn)targetNodeBiTNode<RecT>targetNode=searchNode(t,kx);//如果沒有找到要刪除的結(jié)點(diǎn)，返回tif(targetNode==null){ System.out.println("沒有找到要刪除的結(jié)點(diǎn)"); return

t;}//2.找到targetNode的父結(jié)點(diǎn)parentBiTNode<RecT>parent=searchParent(t,kx);//在二叉排序樹中查找關(guān)鍵字為kx的父結(jié)點(diǎn),//如果沒有找到，返回null,否則返回父結(jié)點(diǎn)public

staticBiTNode<RecT>searchParent(BiTNode<RecT>t,Tkx){BiTNode<RecT>p=t;//p存放要查找的結(jié)點(diǎn)BiTNode<RecT>f=null;//

要查找的結(jié)點(diǎn)的父結(jié)點(diǎn)while(p!=null&&!p.data.key.equals(kx)){f=p;if(kx.compareTo(p.data.key)<0){

p=p.lchild;}else{ p=p.rchild;}}if(p==null){//沒有找到關(guān)鍵字kx，返回null return

null;}else{ return

f;//找到了關(guān)鍵字kx，返回父結(jié)點(diǎn)}}二叉排序樹的刪除算法描述二叉排序樹//3.1刪除葉子結(jié)點(diǎn)if(targetNode.lchild==null&&targetNode.rchild==null){if(parent!=null){//targetNode有父結(jié)點(diǎn)的場合 //判斷targetNode是父結(jié)點(diǎn)的左子結(jié)點(diǎn)，還是右子結(jié)點(diǎn) if(parent.lchild!=null&&parent.lchild.data.key.equals(kx)){ //左子結(jié)點(diǎn) parent.lchild=null; }else

if(parent.rchild!=null&&parent.rchild.data.key.equals(kx)){ //右子結(jié)點(diǎn) parent.rchild=null; }}else{//targetNode是根結(jié)點(diǎn)的場合 t=null; return

t;}}二叉排序樹的刪除算法描述二叉排序樹else

if(targetNode.lchild!=null&&targetNode.rchild!=null){//3.2刪除有兩棵子樹的結(jié)點(diǎn)//targetNode右子樹中最小的結(jié)點(diǎn)替換targetNode，并刪除該結(jié)點(diǎn)。t=delRightTreeMin(t,targetNode);}public

staticBiTNode<RecT>delRightTreeMin(BiTNode<RecT>t,BiTNode<RecT>targetNode){BiTNode<RecT>p=targetNode.rchild;//P存放targetNode右子樹while(p.lchild!=null){//P存放targetNode右子樹最小結(jié)點(diǎn) p=p.lchild;}Tmin=p.data.key;t=deleteNode(t,min);//刪除targetNode右子樹最小結(jié)點(diǎn)targetNode.data.key=min;//targetNode結(jié)點(diǎn)關(guān)鍵字替換為最小值return

t;}二叉排序樹的刪除算法描述二叉排序樹}else

{//3.3刪除只有一棵子樹的結(jié)點(diǎn)if(targetNode.lchild!=null){//targetNode有左子樹的場合 if(parent!=null){//targetNode有父結(jié)點(diǎn)的場合 if(parent.lchild!=null&&parent.lchild.data.key.equals(kx)){//targetNode是

parent的左子結(jié)點(diǎn)

parent.lchild=targetNode.lchild;}else{//targetNode是

parent的右子結(jié)點(diǎn) parent.rchild=targetNode.lchild;}}else{//targetNode是根結(jié)點(diǎn)的場合 t=targetNode.lchild;}}else{//targetNode有右子樹的場合if(parent!=null){//targetNode有父結(jié)點(diǎn)的場合if(parent.lchild!=null&&parent.lchild.data.key.equals(kx)){//targetNode是

parent的左子結(jié)點(diǎn) parent.lchild=targetNode.rchild;}else{//targetNode是

parent的右子結(jié)點(diǎn) parent.rchild=targetNode.rchild;} }else{//targetNode是根結(jié)點(diǎn)的場合 t=targetNode.rchild;}}}}return

t;}Part02平衡二叉樹平衡二叉樹的定義平衡二叉樹根結(jié)點(diǎn)的平衡因子絕對值不超過1；左子樹和右子樹也是平衡二叉樹。平衡二叉樹（BalancedBdzinaryTree）也稱為AVL樹，它或者是一棵空樹，或具有以下性質(zhì)的二叉樹：結(jié)點(diǎn)的平衡因子是指該結(jié)點(diǎn)的左子樹高度與右子樹高度之差。平衡二叉樹的定義平衡二叉樹下面兩棵樹，是否為平衡二叉樹？16832612100008056238566772-11000平衡二叉樹非平衡二叉樹平衡二叉樹的定義平衡二叉樹以二叉鏈表作為平衡二叉樹的存儲結(jié)構(gòu)，二叉鏈表結(jié)點(diǎn)的類型定義如下：public

classAVLNode<RecT>{publicRecTdata;//節(jié)點(diǎn)的數(shù)據(jù)元素publicAVLNode<RecT>lchild,rchild;//節(jié)點(diǎn)的左右孩子int

bf;//平衡因子publicAVLNode(RecTdata,AVLNode<RecT>lchild,AVLNode<RecT>rchild,int

bf){this.data=data;this.lchild=lchild;this.rchild=rchild;this.bf=bf;}}平衡二叉樹的查找和二叉排序樹相同，查找過程中和關(guān)鍵字比較的次數(shù)不超過樹的深度。又因為AVL樹上任何結(jié)點(diǎn)的左右子樹的深度之差都不超過1，則可以證明它的深度和log2n是同數(shù)量級的（其中n為結(jié)點(diǎn)個數(shù)）。因此，其查找的時間復(fù)雜度是O(log2n)。平衡二叉樹的查找平衡二叉樹平衡二叉樹在插入或刪除結(jié)點(diǎn)后,可能變成不平衡,需要調(diào)整。其調(diào)整方法如下：平衡二叉樹的平衡調(diào)整平衡二叉樹找到離插入或刪除結(jié)點(diǎn)最近且平衡因子絕對值超過1的祖先結(jié)點(diǎn)，以該結(jié)點(diǎn)為根的子樹稱為最小不平衡子樹，對該子樹進(jìn)行平衡調(diào)整。按照其調(diào)整規(guī)律可歸納為以下四種情況。平衡二叉樹的平衡調(diào)整-LL型平衡二叉樹AB21h-1h-1hARBRBLXABh-1h-1hARBRBLXh-100BAARh-1BRhBLXLL型調(diào)整過程：結(jié)點(diǎn)B的右子樹BR作為結(jié)點(diǎn)A的左子樹；根結(jié)點(diǎn)為A的子樹作為結(jié)點(diǎn)B的右子樹；結(jié)點(diǎn)B作為新的根結(jié)點(diǎn)。平衡二叉樹的平衡調(diào)整-LL型平衡二叉樹6410（a）插入前BL、BR、AR均為空樹641210146000示例10-1：LL型調(diào)整平衡二叉樹的平衡調(diào)整-LL型平衡二叉樹示例10-2：LL型調(diào)整1683261210000168326122101001183160100120260（b）插入前BL、BR、AR均為非空樹168326122101001平衡二叉樹的LL型調(diào)整算法描述平衡二叉樹AB21h-1h-1hARBRBLXlpph-1BAARh-1BRhBLXlppp00平衡二叉樹的平衡調(diào)整-RR型平衡二叉樹RR型調(diào)整過程：結(jié)點(diǎn)B的左子樹BL作為結(jié)點(diǎn)A的右子樹；根結(jié)點(diǎn)為A的子樹作為結(jié)點(diǎn)B的左子樹；結(jié)點(diǎn)B作為新的根結(jié)點(diǎn)。BA00hh-1h-1BRBLALXh-2-1ABBRh-1BLh-1ALXh-2-1ABBRh-1BLh-1ALX平衡二叉樹的平衡調(diào)整-RR型平衡二叉樹（a）插入前AL、BL、BR均為空樹示例11-1：RR型調(diào)整5-108-20-1589800950平衡二叉樹的平衡調(diào)整-RR型平衡二叉樹示例11-2：RR型調(diào)整（b）插入前AL、BL、BR均為非空樹35-126048436200035-2260484362-10-166048356200-104306602635-2260484362-10-1660平衡二叉樹的RR型調(diào)整算法描述平衡二叉樹prph-2-1ABBRh-1BLh-1ALXBAhh-1h-1BRBLALXprpp00平衡二叉樹的平衡調(diào)整-LR型平衡二叉樹LR型調(diào)整過程：先對以B為根的子樹進(jìn)行RR型調(diào)整；再對以A為根的子樹進(jìn)行LL型調(diào)整。AB2-1h-1ARh-1BLh-21CCRh-1CLXA2h-1ARB0h-1BLC2h-2CRh-1CLXCB0Ah-1BLCLXh-1ARh-1CRh-20-1平衡二叉樹的平衡調(diào)整-LR型平衡二叉樹示例12-1：LR型調(diào)整74107462-10467000764平衡二叉樹的平衡調(diào)整-LR型平衡二叉樹示例12-2：LR型調(diào)整1683261210000168326122-1001010316261281003128160-10260100平衡二叉樹的平衡調(diào)整-LR型平衡二叉樹示例12-3：LR型調(diào)整16