數(shù)據(jù)結(jié)構(gòu)a第07章搜索樹-文庫吧資料
2024-08-17 10:10本頁面
【正文】 bF=1） 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 switch(ubF){ case 1:sbF=1。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 情況一 若插入前，從根結(jié)點(diǎn)到新結(jié)點(diǎn) q的插入位置的路徑上，所有結(jié)點(diǎn)的平衡因子值均為 0，插入 q后，只需將根結(jié)點(diǎn)的平衡因子改為 1，并且 AVL樹的高度加 1，插入操作完成。 插入后 ， 該樹不再是二叉平衡樹 。 插入 44： 從根到 44的路徑上 ， 43和 56的平衡因子都不為 0， 其中 56是離 44最近的 ， 平衡因子值不為零的結(jié)點(diǎn) 。 插入后 ，該樹仍然是二叉平衡樹 。 插入新元素 25后 ， 這棵樹仍然是二叉平衡樹 ， 但整棵樹高度加 1。 ? }。s, bool amp。unBalanced)。 void LRotation(AVLNodeT* amp。 x,bool amp。 ResultCode Insert(AVLNodeT* amp。 x)。 x)。 x)const。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 templateclass T class AVLTree:public DynamicSetT { public: AVLTree(){root=NULL。 AVLNode* lChild,*rChild。 } T element。 lChild=rChild=NULL。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 二叉平衡樹類 templateclass T struct AVLNode { AVLNode(const Tamp。 AVL二叉搜索樹 既是二叉搜索樹又是 AVL樹 。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 二叉平衡樹 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 二叉平衡樹的定義 定義 二叉平衡樹又稱 AVL樹 它或者是一棵空二叉樹 ， 或者是具有下列性質(zhì)的二叉樹： （ 1） 其根的左 、 右子樹高度之差的絕對值不超過 1； （ 2） 其根的左 、 右子樹都是二叉平衡樹 。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 設(shè) p(n)是在一棵有 n個結(jié)點(diǎn)的二叉搜索樹上成功搜索一個關(guān)鍵字的平均比較次數(shù) 。由此序列構(gòu)成的二叉搜索樹，其左子樹上有 i個結(jié)點(diǎn)，而右子樹上有 ni1個結(jié)點(diǎn)。 最壞情況搜索時間為 O(n)。 return Success。 else qrChild=c。 if(p==root) root=c。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 if (plChild) c=plChild。 p=s。s=slChild。r=p。amp。 x=pelement。 else p=prChild。 pelement!=x){//搜索 q=p。 while (p amp。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 刪除 28 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 template class T ResultCode BSTreeT::Remove(Tamp。 若被刪除的結(jié)點(diǎn) *p是根結(jié)點(diǎn) ， 則刪除后 ， 結(jié)點(diǎn) *c成為新的根；若 *p是其雙親 *q的左孩子 ，則 *c也應(yīng)成為 *q的左孩子 ， 否則 *c成為 *q的右孩子 。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 二叉搜索樹的刪除 若結(jié)點(diǎn) *p有兩棵非空子樹 需搜索 *p的中序遍歷次序下的直接后繼（ 或直接前驅(qū) ） 結(jié)點(diǎn) ， 設(shè)為 *s， 將 *s的值復(fù)制到 *p中 ， 稱為 替代 ， 因?yàn)?*s最多只有一棵非空子樹 ， 這樣一來 ， 問題轉(zhuǎn)化為 “ 被刪除的結(jié)點(diǎn)最多只有一棵非空子樹 ” 的情形 。 else qrChild=p。 if(!root) root=p。return Duplicate。 else if(xpelement) p=prChild。 while (p){ q=p。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 二叉搜索樹的插入 template class T ResultCode BSTreeT::Insert(Tamp。 return Success。 else if(xpelement) p=prChild。 x)const { BTNodeT *p=root。return Success。 else i
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1