浙江工業(yè)大學(xué)《項(xiàng)目評(píng)估》第3章

1、1 1第七章 搜索結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)電子教案數(shù)據(jù)結(jié)構(gòu)電子教案殷人昆殷人昆 王王 宏宏2 2第七章第七章 搜索結(jié)構(gòu)搜索結(jié)構(gòu)3 3搜索搜索(Search)(Search)的概念的概念靜態(tài)搜索表靜態(tài)搜索表n所謂所謂搜索搜索，就是在數(shù)據(jù)集合中尋找滿足某種，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。條件的數(shù)據(jù)對(duì)象。n搜索的結(jié)果通常有兩種可能：搜索的結(jié)果通常有兩種可能：搜索成功搜索成功，即找到滿足條件的數(shù)據(jù)對(duì)象。，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中 的位置的位置, 還可給出該對(duì)象中的具體信息。還可給出該對(duì)象中的具體信息。搜索不成功搜索不成功，或搜

2、索失敗。作為結(jié)果，應(yīng)，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息報(bào)告一些信息, 如失敗標(biāo)志、位置等。如失敗標(biāo)志、位置等。4 4n通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象是由同一數(shù)據(jù)類型的對(duì)象(或記錄或記錄)組成。組成。n在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的

3、搜索方法，但搜索結(jié)果可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。可能不唯一。n實(shí)施搜索時(shí)有兩種不同的環(huán)境。實(shí)施搜索時(shí)有兩種不同的環(huán)境。u靜態(tài)環(huán)境靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。的前后不發(fā)生改變。 靜態(tài)搜索表靜態(tài)搜索表 5 5u動(dòng)態(tài)環(huán)境動(dòng)態(tài)環(huán)境，為保持較高的搜索效率，為保持較高的搜索效率, , 搜索搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 動(dòng)態(tài)搜索表動(dòng)態(tài)搜索表n在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元

4、素的下標(biāo)作為數(shù)據(jù)元素的存放地利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值址。搜索算法根據(jù)給定值 k，在數(shù)組中進(jìn)行，在數(shù)組中進(jìn)行搜索。直到找到搜索。直到找到 k 在數(shù)組中的存放位置或可在數(shù)組中的存放位置或可確定在數(shù)組中找不到確定在數(shù)組中找不到 k 為止。為止。 靜態(tài)搜索表靜態(tài)搜索表6 6數(shù)據(jù)表與搜索表的類定義數(shù)據(jù)表與搜索表的類定義 #include #include const int defaultSize = 100;template class dataList;/數(shù)據(jù)表類的前視定義template class dataNode /數(shù)據(jù)表中結(jié)點(diǎn)類的定義friend clas

5、s dataList; /聲明其友元類為dataListpublic:7 7 dataNode (const K x) : key(x) /構(gòu)造函數(shù) K getKey() const return key; /讀取關(guān)鍵碼 void setKey (K x) key = x; /修改關(guān)鍵碼private: K key;/關(guān)鍵碼域 E other; /其他域（視問題而定）; template class dataList /數(shù)據(jù)表類定義public:8 8 dataList (int sz = defaultSize) : ArraySize(sz), CuurentSize(0) Element

6、 = new dataNodesz; assert (Element != NULL); dataList (dataList& R); /復(fù)制構(gòu)造函數(shù) virtual dataList() delete Element; /析構(gòu)函數(shù) virtual int Length() return CurrentSize; /求表的長度 virtual K getKey (int i) const /提取第 i（1開始）元素值 9 9 assert (i 0 | i 0 | i = CurrentSize); Elementi-1.key = x; virtual int SeqSearch (con

7、st K x) const; /搜索 virtual bool Insert (E& e1); /插入 virtual bool Remove (K x, E& e1); /刪除friend ostream& operator (ostream& out, const dataList& OutList); /輸出1010friend istream& operator (istream& in, dataList& InList); /輸入protected: dataNode *Element; /數(shù)據(jù)表存儲(chǔ)數(shù)組 int ArraySize, CurrentSize; /數(shù)組最大長度和當(dāng)前

8、長度;template bool dataList:Insert (E& e1) /在dataList的尾部插入新元素, 若插入失敗函數(shù)返/回false, 否則返回true.11 11 if (CurrentSize = ArraySize) return false; ElementCurrentSize = e1;/插入在尾端 CurrentSize+; return true;template bool dataList:Remove (K x, E& e1) /在dataList中刪除關(guān)鍵碼為x的元素, 通過e1返回。/用尾元素填補(bǔ)被刪除元素。 if (CurrentSize = 0)

9、 return false; for (int i = 0; i CurrentSize & Elementi != x; i+); /在表中順序?qū)ふ?212 if (i = CurrentSize) return false; /未找到 e1 = Elementi.other; /找到,保存被刪元素的值 Elementi = ElementCurrentSize-1; /填補(bǔ) CurrentSize-; return true;template ostream& operator (ostream& out, const dataList& OutList) out “存儲(chǔ)數(shù)組大小存儲(chǔ)數(shù)組大

10、小” endl;數(shù)據(jù)表類的友元函數(shù)數(shù)據(jù)表類的友元函數(shù) 1313 for (int i = 1; i = OutList.CurrentSize; i+) out OutList.Elementi-1 ;out endl; /輸出表的所有表項(xiàng)到out out “數(shù)組當(dāng)前長度數(shù)組當(dāng)前長度 : ” OutList.CurrentSize endl; /輸出表的當(dāng)前長度到outreturn out;template istream& operator (istream& in, dataList& InList) 1414 cout InList.CurrentSize; /從in輸入表的當(dāng)前長度 c

11、out “輸入數(shù)組元素的值輸入數(shù)組元素的值 : n”; for (int i = 1; i = InList.CurrentSize; i+) /從in輸入表的全部表項(xiàng) cout “元素元素 ” i InList.Elementi-1; return in;1515n順序搜索主要用于在線性表中搜索。順序搜索主要用于在線性表中搜索。n設(shè)若表中有設(shè)若表中有 CurrentSize 個(gè)元素，則順序搜個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值與給定值 x 進(jìn)行比較進(jìn)行比較n若找到與其值相等的元素，則搜索成功，給若找到與其值相等的元素，則搜索成功

12、，給出該元素在表中的位置。出該元素在表中的位置。n若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與 x 相相等的元素，則搜索失敗。給出失敗信息。等的元素，則搜索失敗。給出失敗信息。順序搜索（順序搜索（Sequential SearchSequential Search） 1616n一般的順序搜索算法在第二章已經(jīng)討論過，一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用本章介紹一種使用“監(jiān)視哨監(jiān)視哨”的順序搜索方的順序搜索方法。法。n設(shè)在設(shè)在數(shù)據(jù)表數(shù)據(jù)表 dataList 中順序搜索關(guān)鍵碼與中順序搜索關(guān)鍵碼與 給定值給定值 x 相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在相等的數(shù)據(jù)元素

13、，要求數(shù)據(jù)元素在表中從下標(biāo)表中從下標(biāo) 0 開始存放開始存放, 下標(biāo)為下標(biāo)為 CurrentSize 的元素作為控制搜索過程自動(dòng)結(jié)束的的元素作為控制搜索過程自動(dòng)結(jié)束的“監(jiān)視監(jiān)視哨哨”使用。使用。n若搜索成功，則函數(shù)返回該元素在表中序號(hào)若搜索成功，則函數(shù)返回該元素在表中序號(hào) Location（比下標(biāo)大（比下標(biāo)大 1）, 若搜索失敗，則函若搜索失敗，則函數(shù)返回?cái)?shù)返回 CurrentSize+1。 1717使用監(jiān)視哨的順序搜索算法使用監(jiān)視哨的順序搜索算法 template int dataList:SeqSearch (const K x) const ElementCurrentSize.key =

14、 x; int i = 0; /將x設(shè)置為監(jiān)視哨 while (Elementi.key != x) i+; /從前向后順序搜索 return i+1;const int Size = 10;main () 1818 dataList L1 (Size);/定義int型搜索表L1 int Target; int Loc; cin L1; cout L1;/輸入L1 cout Target;/輸入要搜索的數(shù)據(jù) if ( (Location = L1.Seqsearch(Target) != L1.Length() ) cout “找到待查元素位置在：找到待查元素位置在：” Loc+1 endl;

15、/搜索成功 else cout “ 沒有找到待查元素沒有找到待查元素n”; /搜索不成功;1919n設(shè)數(shù)據(jù)表中有設(shè)數(shù)據(jù)表中有 n 個(gè)元素，搜索第個(gè)元素，搜索第 i 個(gè)元素的個(gè)元素的概率為概率為 pi，搜索到第，搜索到第 i 個(gè)元素所需比較次數(shù)個(gè)元素所需比較次數(shù)為為 ci，則搜索成功的平均搜索長度，則搜索成功的平均搜索長度:n在順序搜索并設(shè)置在順序搜索并設(shè)置“監(jiān)視哨監(jiān)視哨”情形：情形： ci = i +1, i = 0, 1, , n-1，因此，因此1010niiniiisuccpcpASL) 1 ( .)(110ipASL-niisucc順序搜索的平均搜索長度順序搜索的平均搜索長度2020n一

16、般表中各個(gè)元素的搜索概率不同，如果按一般表中各個(gè)元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順?biāo)阉鞲怕实母叩团帕斜碇械脑兀瑥挠行蝽樞虮淼那闆r可知，能夠得到高的平均搜索長序表的情況可知，能夠得到高的平均搜索長度。度。n在等概率情形，在等概率情形，pi = 1/n, i = 1, 2, , n。搜索。搜索成功的平均搜索程度為：成功的平均搜索程度為：n在搜索不成功情形，在搜索不成功情形，ASLunsucc = n+1。.)()(1-nisuccnnnninASL021211112121n采用遞歸方法搜索值為采用遞歸方法搜索值為 x 的元素，每遞歸一的元素，每遞歸一層就向待查元素逼

17、近一個(gè)位置，直到到達(dá)該層就向待查元素逼近一個(gè)位置，直到到達(dá)該元素。假設(shè)待查元素在第元素。假設(shè)待查元素在第 i（1in）個(gè)位置，）個(gè)位置，則算法遞歸深度達(dá)則算法遞歸深度達(dá) i（1i）。）。10 20 30 40 50 60i = 1搜索搜索 3010 20 30 40 50 60i = 210 20 30 40 50 60i = 3遞遞歸歸順序搜索的遞歸算法順序搜索的遞歸算法2222順序搜索的遞歸算法順序搜索的遞歸算法template int dataList:SeqSearch (const K x, int loc) const /在數(shù)據(jù)表 Element1.n 中搜索其關(guān)鍵碼與給定值/匹配

18、的對(duì)象, 函數(shù)返回其表中位置。參數(shù) loc 是在/表中開始搜索位置 if (loc CurrentSize) return 0; /搜索失敗 else if (Elementloc-1.key = x) return loc; /搜索成功 else return Search (x, loc+1); /遞歸搜索;2323二叉搜索樹二叉搜索樹 ( Binary Search Tree )( Binary Search Tree )n定義定義 二叉搜索樹或者是一棵空樹，或者是具二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：有下列性質(zhì)的二叉樹： 每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵每個(gè)結(jié)點(diǎn)都有

19、一個(gè)作為搜索依據(jù)的關(guān)鍵碼碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。 左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。 右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。 左子樹和右子樹也是二叉搜索樹。左子樹和右子樹也是二叉搜索樹。2424351545504025102030二叉搜索樹例二叉搜索樹例n結(jié)點(diǎn)左子樹上所結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼；點(diǎn)關(guān)鍵碼；n右子樹上所有關(guān)右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼；

20、鍵碼；n注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。的結(jié)點(diǎn)的關(guān)鍵碼。2525n如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。來，所以也稱二叉搜索樹為二叉排序樹。n二叉搜索樹的類定義二叉搜索樹的類定義#include #include template struct BSTNode /二叉樹結(jié)點(diǎn)類 E data; /數(shù)據(jù)域 BST

21、Node *left, *right; /左子女和右子女2626 BSTNode() left = NULL; right = NULL; /構(gòu)造函數(shù) BSTNode (const E d, BSTNode *L = NULL, BSTNode *R = NULL) data = d; left = L; right = R; /構(gòu)造函數(shù) BSTNode() /析構(gòu)函數(shù) void setData (E d) data = d; /修改 E getData() return data; /提取 bool operator (const E& x) /重載：判小于 return data.key

22、(const E& x) /重載：判大于 return data.key x.key; bool operator = (const E& x) /重載：判等于 return data.key = x.key; ;template class BST /二叉搜索樹類定義public: BST() root = NULL; /構(gòu)造函數(shù) BST(K value); /構(gòu)造函數(shù) BST() ; /析構(gòu)函數(shù)2828 bool Search (const K x) const/搜索 return Search(x,root) != NULL; BST& operator = (const BST& R)

23、; /重載：賦值 void makeEmpty() /置空 makeEmpty (root); root = NULL; void PrintTree() const PrintTree (root); /輸出 E Min() return Min(root)-data; /求最小E Max() return Max(root)-data; /求最大bool Insert (const E& e1) /插入新元素 return Insert(e1, root);2929 bool Remove (const K x) return Remove(x, root); /刪除含x的結(jié)點(diǎn)privat

24、e: BSTNode *root;/根指針 K RefValue; /輸入停止標(biāo)志 BSTNode * /遞歸：搜索 Search (const K x, BSTNode *ptr); void makeEmpty (BSTNode *& ptr);/遞歸：置空 void PrintTree (BSTNode *ptr) const;/遞歸：打印 BSTNode */遞歸：復(fù)制 Copy (const BSTNode *ptr);3030 BSTNode* Min (BSTNode* ptr);/遞歸：求最小 BSTNode* Max (BSTNode* ptr);/遞歸：求最大 bool I

25、nsert (const E& e1, BSTNode*& ptr);/遞歸：插入 bool Remove (const K x, BSTNode*& ptr);/遞歸：刪除;n二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)表示，許多操作的實(shí)現(xiàn)與二叉樹類似。表示，許多操作的實(shí)現(xiàn)與二叉樹類似。3131二叉搜索樹的搜索算法二叉搜索樹的搜索算法n在二叉搜索樹上進(jìn)行搜索，是一個(gè)在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開從根結(jié)點(diǎn)開始始，沿某一個(gè)分支逐層向下沿某一個(gè)分支逐層向下進(jìn)行比較判等的過進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。程。它可以是一個(gè)遞歸的過程。n假設(shè)想要

26、在二叉搜索樹中搜索關(guān)鍵碼為假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x 的元的元素，搜索過程從根結(jié)點(diǎn)開始。素，搜索過程從根結(jié)點(diǎn)開始。n如果如果根指針為根指針為NULL，則，則搜索不成功搜索不成功；否則用；否則用給定值給定值 x 與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若若給定值等于根結(jié)點(diǎn)關(guān)鍵碼給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則，則搜索成功搜索成功，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。3232 若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；遞歸搜索根結(jié)點(diǎn)的左子樹； 否則。遞歸搜索根結(jié)點(diǎn)的右子樹。否則。遞歸搜索根結(jié)

27、點(diǎn)的右子樹。搜索搜索45搜索成功搜索成功搜索搜索28搜索失敗搜索失敗3515455040251020303333templateBSTNode* BST:Search (const K x, BSTNode *ptr) /私有遞歸函數(shù)：在以ptr為根的二叉搜索樹中搜/索含x的結(jié)點(diǎn)。若找到，則函數(shù)返回該結(jié)點(diǎn)的/地址，否則函數(shù)返回NULL值。 if (ptr = NULL) return NULL; else if (x data) return Search(x, ptr-left); else if (x ptr-data) return Search(x, ptr-right); else

28、return ptr;/搜索成功;3434templateBSTNode* BST:Search (const K x, BSTNode *ptr) /非遞歸函數(shù)：作為對(duì)比，在當(dāng)前以ptr為根的二/叉搜索樹中搜索含x的結(jié)點(diǎn)。若找到，則函數(shù)返/回該結(jié)點(diǎn)的地址，否則函數(shù)返回NULL值。 if (ptr = NULL) return NULL; BSTNode* temp = ptr; while (temp != NULL) if (x = temp-data) return temp; if (x data) temp = temp-left;3535 else temp = temp-righ

29、t; return NULL;n搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自上而下逐層比較判等的過程。上而下逐層比較判等的過程。n搜索成功，搜索指針將停留在樹上某個(gè)結(jié)搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。個(gè)結(jié)點(diǎn)的空子樹。n設(shè)樹的高度為設(shè)樹的高度為h，最多比較次數(shù)不超過，最多比較次數(shù)不超過h。3636二叉搜索樹的插入算法二叉搜索樹的插入算法n為了向二叉搜索樹中插入一個(gè)新元素，必須為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在先檢查這個(gè)元素是否在樹中已經(jīng)存在。n

30、在插入之前，先使用搜索算法在樹中檢查要在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。操作停止的地方。 373735154550402510203028插入新結(jié)點(diǎn)插入新結(jié)點(diǎn)28二叉搜索樹的插入二叉搜索樹的插入n每次結(jié)點(diǎn)的插入，都要每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作位置

31、，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。為葉結(jié)點(diǎn)插入。3838二叉搜索樹的插入算法二叉搜索樹的插入算法template bool BST:Insert (const E& e1, BSTNode *& ptr) /私有函數(shù)：在以ptr為根的二叉搜索樹中插入值為/e1的結(jié)點(diǎn)。若在樹中已有含e1的結(jié)點(diǎn)則不插入 if (ptr = NULL) /新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入 ptr = new BstNode(e1); /創(chuàng)建新結(jié)點(diǎn) if (ptr = NULL) cerr Out of space endl; exit(1); return true;3939 else if (e1 data) Insert (e

32、1, ptr-left); /左子樹插入 else if (e1 ptr-data) Insert (e1, ptr-right);/右子樹插入 else return false; /x已在樹中,不再插入;n注意參數(shù)表中引用型指針參數(shù)注意參數(shù)表中引用型指針參數(shù)ptr的使用。的使用。n利用二叉搜索樹的插入算法，可以很方便地利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。建立二叉搜索樹。 4040輸入數(shù)據(jù)輸入數(shù)據(jù) 53, 78, 65, 17, 87, 09, 81, 15 5353785378655378651753786587175378650917875378658117870953

33、786515178709814141template BST:BST (K value) /輸入一個(gè)元素序列, 建立一棵二叉搜索樹 E x; root = NULL; RefValue = value; /置空樹 cin x; /輸入數(shù)據(jù) while ( x.key != RefValue) /RefValue是一個(gè)輸入結(jié)束標(biāo)志 Insert (x, root); cin x; /插入，再輸入數(shù)據(jù) ;4242二叉搜索樹的刪除算法二叉搜索樹的刪除算法n在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接

34、起來，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。n為保證在刪除后樹的搜索性能不至于降低，為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。還需要防止重新鏈接后樹的高度增加。刪除葉結(jié)點(diǎn)刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。指針清零，再釋放它即可。被刪結(jié)點(diǎn)右子樹為空被刪結(jié)點(diǎn)右子樹為空，可以拿它的左子女，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。結(jié)點(diǎn)頂替它的位置，再釋放它。4343被刪結(jié)點(diǎn)左子樹為空被刪結(jié)點(diǎn)左子樹為空，可以拿它的右子女結(jié)，可以拿它的右子女結(jié)點(diǎn)點(diǎn)頂替它的位置，再釋放它。頂替它的位置，再釋放

35、它。被刪結(jié)點(diǎn)左、右子樹都不為空被刪結(jié)點(diǎn)左、右子樹都不為空，可以在它的，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)( (關(guān)鍵碼關(guān)鍵碼最小最小),),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。理這個(gè)結(jié)點(diǎn)的刪除問題。5378651787092345刪除45右子樹空, 用左子女頂替5378651787092344448853788817940923刪除78左子樹空, 用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)23655381881794094523654545二叉搜索樹

36、的刪除算法二叉搜索樹的刪除算法template bool BST:Remove (const K x, BstNode *& ptr) /在以 ptr 為根的二叉搜索樹中刪除含 x 的結(jié)點(diǎn) BstNode *temp; if (ptr != NULL) if (x data) Remove (x, ptr-left); /在左子樹中執(zhí)行刪除 else if (x ptr-data) Remove (x, ptr-right); /在右子樹中執(zhí)行刪除4646 else if (ptr-left != NULL & ptr-right != NULL) /ptr指示關(guān)鍵碼為x的結(jié)點(diǎn)，它有兩個(gè)子女

37、temp = ptr-right; /到右子樹搜尋中序下第一個(gè)結(jié)點(diǎn) while (temp-left != NULL) temp = temp-left; ptr-data = temp-data; /用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù) Remove (ptr-data, ptr-right); else /ptr指示關(guān)鍵碼為x的結(jié)點(diǎn)有一個(gè)子女4747 temp = ptr; if (ptr-left = NULL) ptr = ptr-right; else ptr = ptr-left; delete temp; return true; return false; n注意在刪除算法參數(shù)表引用型指

38、針參數(shù)的使用。注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。4848 二叉搜索樹性能分析二叉搜索樹性能分析n對(duì)于有對(duì)于有 n 個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有 n! 種種不同排列，可構(gòu)成不同二叉搜索樹有不同排列，可構(gòu)成不同二叉搜索樹有 (棵棵)Cnnn2112, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 11231111322233234949n同樣同樣 3 個(gè)數(shù)據(jù)個(gè)數(shù)據(jù) 1, 2, 3 ，輸入順序不同，建立，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。到二

39、叉搜索樹的搜索性能。n如果輸入序列選得不好，會(huì)建立起一棵單支樹，如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。使得二叉搜索樹的高度達(dá)到最大。n用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。n為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。中已有的數(shù)據(jù)。n這樣的判定樹即為這樣的判定樹即為擴(kuò)充的二叉搜索樹擴(kuò)充的二叉搜索樹。5050n舉例說明。已知關(guān)鍵碼集合舉例說明。已知關(guān)鍵碼集合 a1, a2, a3 = do, if,

40、to，對(duì)應(yīng)搜索概率，對(duì)應(yīng)搜索概率p1, p2, p3, 在各搜索不成功在各搜索不成功間隔內(nèi)搜索概率分別為間隔內(nèi)搜索概率分別為q0, q1, q2, q3。可能的二?？赡艿亩嫠阉鳂淙缦滤?。叉搜索樹如下所示。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)5151判定樹判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)5252.*i lipASLnisucc1n在判定樹中在判定樹中u 表示表示內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合中的，包含了關(guān)鍵碼集合中的某一個(gè)

41、關(guān)鍵碼；某一個(gè)關(guān)鍵碼；u 表示表示外部結(jié)點(diǎn)外部結(jié)點(diǎn)，代表各關(guān)鍵碼間隔中的，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。不在關(guān)鍵碼集合中的關(guān)鍵碼。n在每兩個(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn)在每兩個(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn)。n一棵判定樹上的搜索成功的平均搜索長度一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率索概率pi與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)次數(shù)ci (= li, 即結(jié)點(diǎn)所在層次即結(jié)點(diǎn)所在層次) 乘積之和：乘積之和：5353n設(shè)各關(guān)鍵碼的搜索概率相等：設(shè)各關(guān)鍵碼的搜索概率相等：pi =

42、 1/nn搜索不成功的平均搜索長度搜索不成功的平均搜索長度ASLunsucc為樹中所為樹中所有外部結(jié)點(diǎn)上搜索概率有外部結(jié)點(diǎn)上搜索概率qj與到達(dá)外部結(jié)點(diǎn)所與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)需關(guān)鍵碼比較次數(shù)cj(= lj)乘積之和：乘積之和：n設(shè)外部結(jié)點(diǎn)搜索概率相等：設(shè)外部結(jié)點(diǎn)搜索概率相等：qj = 1/(n+1)：. nisucci lnASL11njunsuccjljqASL0).1 (*njunsuccjlnASL0(11).15454n設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等： pi = 1/3, 1i3, qj = 1/4, 0 j3 圖圖(a): A

43、SLsucc = 1/3*3+1/3*2+1/3*1 = 6/3, ASLunsucc = 1/4*3*2+1/4*2+1/4*1 = 9/4。 圖圖(b): ASLsucc = 1/3*2*2+1/3*1 = 5/3, ASLunsucc = 1/4*2*4 = 8/4。 圖圖(c): ASLsucc = 1/3*1+1/3*2+1/3*3 = 6/3, ASLunsucc = 1/4*1+1/4*2+1/4*3*2 = 9/4。 圖圖(d): ASLsucc = 1/3*2+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。(

44、1) 相等搜索概率的情形相等搜索概率的情形5555圖圖(e): ASLsucc = 1/3*1+1/3*3+1/3*2 = 6/3, ASLunsucc = 1/4*1+1/4*3*2+1/4*2 = 9/4。n圖圖(b)的情形所得的平均搜索長度最小。的情形所得的平均搜索長度最小。n一般把平均搜索長度達(dá)到最小的擴(kuò)充的二叉搜一般把平均搜索長度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。索樹稱作最優(yōu)二叉搜索樹。n在在相等搜索概率相等搜索概率的情形下，所有內(nèi)部、外部結(jié)的情形下，所有內(nèi)部、外部結(jié)點(diǎn)的搜索概率都相等，視它們的權(quán)值都為點(diǎn)的搜索概率都相等，視它們的權(quán)值都為 1。同時(shí)，第同時(shí)，第 k 層有層

45、有 2k-1個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，k = 1, 2, 。則。則有有 n 個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉搜索樹的內(nèi)部路徑個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉搜索樹的內(nèi)部路徑長度長度 I 至少等于序列至少等于序列 56560, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 的前的前 n 項(xiàng)的和。項(xiàng)的和。n因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長度和搜索不成功的平均搜索長度分別為長度和搜索不成功的平均搜索長度分別為:.112log2nniunsucciASL.nisucciASL121log5757n設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率

46、設(shè)二叉搜索樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率互不相等?；ゲ幌嗟取?p1 = 0.5, p2 = 0.1, p3 = 0.05 q0 = 0.15, q1 = 0.1, q2 = 0.05, q3 = 0.05n分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹的搜索性分別計(jì)算各個(gè)可能的擴(kuò)充二叉搜索樹的搜索性能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長度能，判斷哪些擴(kuò)充二叉搜索樹的平均搜索長度最小。最小。(2) 不相等搜索概率的情形不相等搜索概率的情形5858doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15 q1=0.1 q2=0.05q3=

47、 0.05p1=0.5p2=0.1p3=0.05(a)(b)圖圖(a): ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75， ASLunsucc = 0.15*3+0.1*3+0.05*2+ 0.05*1 = 0.9。圖圖(b): ASLsucc = 0.5*2+0.1*1+0.05*2 = 1.2， ASLunsucc = (0.15+0.1+0.05+0.05)*2 = 0.7。5959doifto q0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q

48、3=0.05p3=0.05(d)(c)圖圖(c): ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85, ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75.圖圖(d) : ASLsucc = 0.5*2+0.1*3+0.05*1 = 1.35, ASLunsucc = 0.15*2+0.1*3+0.05*3+0.05*1 = 0.86060n由此可知，圖由此可知，圖(c)和圖和圖(e)的情形下樹的平均搜索的情形下樹的平均搜索長度達(dá)到最小，因此，圖長度達(dá)到最小，因此，圖(c)和圖和圖(e)的情形是最的情形是最優(yōu)二叉搜索樹。優(yōu)二叉搜索樹

49、。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e) 圖圖(e) : ASLsucc = 0.5*1+ 0.1*3+0.05*2 = 0.9; ASLunsucc = 0.15*1+ 0.1*3+0.05*3+0.05*2 = 0.7;6161最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹n在相等搜索概率的情形下，因?yàn)樗袃?nèi)、外部在相等搜索概率的情形下，因?yàn)樗袃?nèi)、外部結(jié)點(diǎn)的搜索概率都相等，把它們的權(quán)值都視為結(jié)點(diǎn)的搜索概率都相等，把它們的權(quán)值都視為1。有。有 n 個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹應(yīng)為完個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹應(yīng)為完全二叉樹或理想平衡樹。全二

50、叉樹或理想平衡樹。n不相等搜索概率情形下的最優(yōu)二叉搜索樹可能不相等搜索概率情形下的最優(yōu)二叉搜索樹可能不同于完全二叉樹的形態(tài)。考慮在不相等搜索不同于完全二叉樹的形態(tài)?？紤]在不相等搜索概率情形下如何構(gòu)造最優(yōu)二叉搜索樹。概率情形下如何構(gòu)造最優(yōu)二叉搜索樹。n假設(shè)關(guān)鍵碼集合放在一個(gè)假設(shè)關(guān)鍵碼集合放在一個(gè)有序的順序表有序的順序表中中 key1, key2, key3,keyn 6262n設(shè)最優(yōu)二叉搜索樹為設(shè)最優(yōu)二叉搜索樹為T0n，其平均搜索長，其平均搜索長度為：度為：nl i是內(nèi)部結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn) ai 所在層次，所在層次，lj 是外部結(jié)是外部結(jié)點(diǎn)點(diǎn) j 所在的層次。所在的層次。C0n 是樹的代價(jià)。為計(jì)是樹

51、的代價(jià)。為計(jì)算方便，將算方便，將 pi 與與 qj 化為整數(shù)?；癁檎麛?shù)。n假定：假定：njninCjljqilipASL010) 1 (*ninjjqip1016363n對(duì)于任一棵子樹對(duì)于任一棵子樹 Tij, 它由它由 keyi+1, keyi+2, keyj 組成，其內(nèi)、外部結(jié)點(diǎn)的權(quán)值分別為組成，其內(nèi)、外部結(jié)點(diǎn)的權(quán)值分別為 pi+1, pi+2, pj qi, qi+1, qi+2, qj 6464n使用數(shù)組使用數(shù)組Wij來存放它的累計(jì)權(quán)值和：來存放它的累計(jì)權(quán)值和： Wij = qi + pi+1 + qi+1 + pi+2 + + qi+2+ pj + qj. 0 i j nn計(jì)算計(jì)算Wi

52、j可以用遞推公式可以用遞推公式: Wii = qi 不是二叉樹, 只有一個(gè)外部結(jié)點(diǎn) Wii+1 = qi + pi+1 + qi+1 = Wii + pi+1 + qi+1有一個(gè)內(nèi)部結(jié)點(diǎn)及兩個(gè)外部結(jié)點(diǎn)的二叉樹Wii+2 = Wii+1 + pi+2 + qi+2/加一個(gè)內(nèi)部結(jié)點(diǎn)和一個(gè)外部結(jié)點(diǎn)的二叉樹6565n一般地，一般地， Wij = Wij-1 + pj + qj /再加一個(gè)內(nèi)部結(jié)點(diǎn)和一個(gè)外部結(jié)點(diǎn)n對(duì)于一棵包括關(guān)鍵碼對(duì)于一棵包括關(guān)鍵碼 keyi+1, , keyk-1, keyk, keyk+1, , keyj 的子樹的子樹Tij, 若設(shè)它的根結(jié)點(diǎn)為若設(shè)它的根結(jié)點(diǎn)為k，i k j，q0 p

53、1 q1 qi pi+1 qi+1 pi+2 qi+2 WiiWii+1Wii+26666它的代價(jià)它的代價(jià)Cij為：為： Cik-1+Wik-1+pk+ Ckj+WkjnCik-1是其包含關(guān)鍵碼是其包含關(guān)鍵碼 keyi+1, keyi+2, keyk-1 的左子樹的左子樹Tik-1的代價(jià)的代價(jià)nCik-1+Wik-1等于把左子樹每個(gè)結(jié)點(diǎn)的等于把左子樹每個(gè)結(jié)點(diǎn)的路徑長度加路徑長度加 1 而計(jì)算出的代價(jià)而計(jì)算出的代價(jià)nCkj是包含關(guān)鍵碼是包含關(guān)鍵碼 keyk+1, keyk+2, keyj 的右子樹的右子樹Tkj的代價(jià)的代價(jià)nCkj+Wkj是把右子樹每個(gè)結(jié)點(diǎn)的路徑長是把右子樹每個(gè)結(jié)點(diǎn)的路徑長度加度

54、加 1之后計(jì)算出的代價(jià)。之后計(jì)算出的代價(jià)。6767Cij = Cik-1 + Wik-1 + pk + Ckj + +Wkjn表明表明: 整個(gè)樹的代價(jià)等于其左子樹的代價(jià)加上其整個(gè)樹的代價(jià)等于其左子樹的代價(jià)加上其右子樹的代價(jià)，再加上根的權(quán)值。右子樹的代價(jià)，再加上根的權(quán)值。n因?yàn)橐驗(yàn)?Wij = pk + Wik-1 + Wkj，故有故有 Cij = Wij + Cik-1 + Ckj n可用可用 k = i+1, i+2, , j 分別計(jì)算上式分別計(jì)算上式, 選取使得選取使得Cij達(dá)到最小的達(dá)到最小的 k。這樣可將最優(yōu)二叉搜索樹這樣可將最優(yōu)二叉搜索樹Tij構(gòu)造出來。構(gòu)造出來。6868構(gòu)造的步驟構(gòu)

55、造的步驟n第一步，構(gòu)造第一步，構(gòu)造只有一個(gè)內(nèi)部結(jié)點(diǎn)只有一個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜的最優(yōu)二叉搜索樹索樹：T01，T12，Tn-1n。n在在Ti-1i (1 i n) 中只包含關(guān)鍵碼中只包含關(guān)鍵碼 keyi。其代價(jià)分別是其代價(jià)分別是 Ci-1i = Wi-1i。另外設(shè)立。另外設(shè)立一一 個(gè)數(shù)組個(gè)數(shù)組 R0.n0.n 存放各最優(yōu)二叉搜索樹存放各最優(yōu)二叉搜索樹的根。的根。 R01 = 1, R12 = 2, , Rn-1n = nn第二步第二步, 構(gòu)造構(gòu)造有兩個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹：的最優(yōu)二叉搜索樹：T02, T13, , Tn-2n。6969n在在Ti-2i中包含兩個(gè)關(guān)鍵碼中包含兩個(gè)關(guān)

56、鍵碼 keyi-1, keyi。其代價(jià)取分別以其代價(jià)取分別以 keyi-1, keyi 做根時(shí)計(jì)算出做根時(shí)計(jì)算出的的 Ci-2i 中的小者。中的小者。n第三步第三步, 第四步第四步, ，構(gòu)造有，構(gòu)造有 3 個(gè)內(nèi)部結(jié)點(diǎn)，個(gè)內(nèi)部結(jié)點(diǎn)，有有 4 個(gè)內(nèi)部結(jié)點(diǎn)，個(gè)內(nèi)部結(jié)點(diǎn)， 的最優(yōu)二叉搜索樹。的最優(yōu)二叉搜索樹。n最后構(gòu)造出包含有最后構(gòu)造出包含有 n 個(gè)內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉?zhèn)€內(nèi)部結(jié)點(diǎn)的最優(yōu)二叉搜索樹。對(duì)于這樣的最優(yōu)二叉搜索樹搜索樹。對(duì)于這樣的最優(yōu)二叉搜索樹, 若設(shè)若設(shè)根根為為 k, 則則根根 k 的值存于的值存于 R0n 中中, 其代價(jià)存于其代價(jià)存于 C0n 中中, 左子樹左子樹的根存于的根存于 R0k-1

57、 中中, 右右子樹子樹的根存于的根存于 Rkn 中。中。7070例例: 給出關(guān)鍵碼集合和內(nèi)給出關(guān)鍵碼集合和內(nèi)/外部結(jié)點(diǎn)的權(quán)值序列外部結(jié)點(diǎn)的權(quán)值序列 關(guān)鍵碼集合關(guān)鍵碼集合 key1 key2 key3 實(shí)實(shí) 例例 do if to 對(duì)應(yīng)對(duì)應(yīng) 內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) p1=50 p2=10 p3=5權(quán)值權(quán)值 外部結(jié)點(diǎn)外部結(jié)點(diǎn) q0=15 q1=10 q2=5 q3=5501510doifto10105555T01 T12 T237171 501510dodoifif155010101055toif10510101055555toifT02 T137272 C 150 190 215 W 100 100

58、100 R 1 2 3左子樹左子樹 T00 T01 T02右子樹右子樹 T13 T23 T33501510doif10555to15 105510550ifdoto501510doif10555toT03 T03 T0373733個(gè)關(guān)鍵碼個(gè)關(guān)鍵碼 do, if, to 的的最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹0 15 75 90 1001 10 25 352 5 153 5Wij0 1 2 30 0 75 115 1501 0 25 502 0 153 0Cij0 1 2 3Rij0 1 2 30 0 1 1 11 0 2 22 0 33 0 p1=50, p2=10, p3=5q0=15, q1=1

59、0, q2= 5, q3= 5 7474AVLAVL樹樹 高度平衡的二叉搜索樹高度平衡的二叉搜索樹 ABCABCDEDEnAVL 樹的定義樹的定義 一棵一棵 AVL 樹或者是空樹，或樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是和右子樹都是 AVL 樹，且左子樹和右子樹的樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過高度之差的絕對(duì)值不超過1。 7575結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)的平衡因子bfbf (balance factorbalance factor)n每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的高度減去

60、左子樹的高度所得的高度差，這的高度減去左子樹的高度所得的高度差，這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子bf。 nAVL樹任一結(jié)點(diǎn)平衡因子只能取樹任一結(jié)點(diǎn)平衡因子只能取 -1, 0, 1。n如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則，則這棵二叉搜索樹就失去了平衡，不再是這棵二叉搜索樹就失去了平衡，不再是AVL樹。樹。n如果一棵有如果一棵有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹是高度平個(gè)結(jié)點(diǎn)的二叉搜索樹是高度平7676衡的，其高度可保持在衡的，其高度可保持在O(log2n)，平均搜索長，平均搜索長度也可保持在度也可保持在O(log2n)。#include #inclu