數(shù)據(jù)結(jié)構(gòu)a第07章搜索樹(存儲版)
【正文】 AVLTree:public DynamicSetT { public: AVLTree(){root=NULL。 ResultCode Insert(AVLNodeT* amp。s, bool amp。 插入 44： 從根到 44的路徑上 ， 43和 56的平衡因子都不為 0， 其中 56是離 44最近的 ， 平衡因子值不為零的結(jié)點 。break。 if (rbF==1){ // LL 旋轉(zhuǎn) slChild=rrChild。 urChild=s。 } s=u。unBalanced=true。 } } else if (x==pelement){ //有重復(fù)元素 unBalanced=false。break。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 （ 3） 若插入新元素 （ 和一個指針后 ） ， 結(jié)點 *q已溢出 ， 則必須進(jìn)行結(jié)點的分裂操作 ， 將結(jié)點一分為三 。 如果搜索成功 ， 且被刪除的元素在葉子結(jié)點中 ， 則從該葉子結(jié)點中刪除該元素；如果被刪除的元素不在葉子結(jié)點中 ，那么由它的右側(cè)子樹上的最小元素取代之 （ 必定在葉結(jié)點中 ） ， 然后從葉子結(jié)點中刪除該替代元素 。 應(yīng)按“ （ 2） ， （ 3） ， （ 4） ” 所述方法處理從雙親結(jié)點中刪除元素的問題 。連接是將兩個結(jié)點中的元素 ， 連同它們的雙親結(jié)點中用來分割它們的元素組合成一個結(jié)點 ， 另一個結(jié)點將撤消 。 只要從根結(jié)點到新元素插入結(jié)點的路徑上至少有一個結(jié)點未滿 ， B樹不會長高 。 設(shè) n是非失敗結(jié)點數(shù) ， t 是指針總數(shù) t =N+n＝ s+n1 定理 有 N個元素的 m階 B樹的高度是 因： N+1?2*（ ?m/2?） h1 ? ? )21N(l o g1hm / 2???南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 B樹的搜索 磁盤訪問的次數(shù)最多是 1＋ log?m/2? ((N+1)/2) 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 B樹的插入 B樹插入新元素的方法 （ 1） 在 B－樹中搜索給定關(guān)鍵字值的元素 ， 如果搜索成功 ， 表示有重復(fù)元素 ， 插入運算失敗終止 ，否則將新元素和一個空指針插入搜索失敗處的葉結(jié)點中 。break。break。unBalanced) { ResultCode result=Success。 case 1:sbF=0。 ulChild=r。s, bool amp。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 情況三 : 插在較高的子樹上（ sbF=+1） LL旋轉(zhuǎn)（ rbF=+1） 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 LR旋轉(zhuǎn)（ rbF=1） 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 switch(ubF){ case 1:sbF=1。 插入后 ，該樹仍然是二叉平衡樹 。unBalanced)。 x)。 AVLNode* lChild,*rChild。 AVL二叉搜索樹 既是二叉搜索樹又是 AVL樹 。 最壞情況搜索時間為 O(n)。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 if (plChild) c=plChild。amp。 while (p amp。 else qrChild=p。 while (p){ q=p。 x)const { BTNodeT *p=root。 x)const { return Search(root,x)。 x)。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 性質(zhì) 若以中序遍歷一棵二叉搜索樹 ， 將得到一個以關(guān)鍵字值遞增排列的有序序列 。 ? protected: BTNodeT* root。 else if (xpelement) return Search(plChild,x)。 else { x=pelement。 else { x=pelement。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 若結(jié)點 *p 只有一棵非空子樹或 *p是葉子 以 *p的惟一孩子 （ 設(shè)為 *c） 或空子樹 （ c＝NULL） 取代 *p， 鏈接至 *p的雙親結(jié)點
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1