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