第8章-1(查找的基本概念)

第8章查找8.1查找的基本概念1.查找:也稱為檢索。如:查找某人的地址、電話號(hào)碼等，都屬于查找范疇。⑴查找是按關(guān)鍵字進(jìn)行的:①關(guān)鍵字(key):是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)(或識(shí)別)一個(gè)數(shù)據(jù)元素。例如:描述一個(gè)考生的信息，可以包含：考號(hào)、姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵字。②有些關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而有的關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如:考生信息中，姓名不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(因有同名同姓的人)，而考號(hào)可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(每個(gè)考生考號(hào)是唯一的，不能相同)。③能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。⑵查找就是根據(jù)給定的值，在一個(gè)表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素:①若表中有這樣的元素，則稱查找是成功的:

查找的信息為給定整個(gè)數(shù)據(jù)元素的輸出或指出該元素在表中的位置；②若表中不存在這樣的記錄，則稱查找是不成功的，或稱查找失敗，并可給出相應(yīng)的提示。2.采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示

“表”:即表中結(jié)點(diǎn)是按何種方式組織的。3.為了提高查找速度，經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來組織表。4.研究各種查找算法時(shí)，首先必須弄清這些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)。5.查找有內(nèi)查找和外查找之分:⑴若整個(gè)查找過程全部在內(nèi)存進(jìn)行，則稱這樣的查找為內(nèi)查找⑵若在查找過程中還需要訪問外存，則稱之為外查找。我們僅介紹內(nèi)查找。6.將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn):

⑴對(duì)于一個(gè)含有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為ASL=

①Ｐi為查找第i個(gè)元素的概率，且=1。

②一般情形下我們認(rèn)為查找每個(gè)元素的概率相等，

③Ｃi為查找第i個(gè)元素所用到的比較次數(shù)。

8．2線性表的查找8.2.1順序查找1．順序查找的基本思想:⑴從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較:

①若相等，則查找成功，

②若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于Ｋ的元素，則查找失敗。⑵順序查找既適用于順序表，也適用于鏈表:

①順序表查找可從前往后掃描，也可從后往前掃描

②采用單鏈表，則只能從前往后掃描。

③另外，順序查找的表中元素可以是無序的。2．順序查找算法實(shí)現(xiàn):constintn=maxn//n為表的最大長(zhǎng)度structnode{…elemtypekey;//key為關(guān)鍵字};

intseqsearch(nodeR[n+1],elemtypek)//在表Ｒ中查找關(guān)鍵字值為Ｋ的元素{R[0].key=k;inti=n;//從表尾開始向前掃描

while(R[i].key!=k)i--;returni;}⑴函數(shù)中查找的范圍從Ｒ[n]到Ｒ[１]，⑵Ｒ[０]為監(jiān)視哨，起兩個(gè)作用:

①為了省去判定while循環(huán)中下標(biāo)越界的條件i≥1，從而節(jié)省比較時(shí)間

②保存要找值的副本，若查找時(shí)，遇到它，表示查找不成功。⑶若算法中不設(shè)立監(jiān)視哨R[0]，程序花費(fèi)的時(shí)間將會(huì)增加，這時(shí)的算法可寫為下面形式。intseqsearch(nodeR[n+1]，elemtypek){inti=n;while(R[i].key!=k)&&(i>=1)i--;returni;}3.順序查找性能分析:⑴假設(shè)在每個(gè)位置查找的概率相等，即有pi=1/n，由于查找是從后往前掃描，則有每個(gè)位置的查找比較次數(shù)

Cn=1，Cn-1=2，…，C1=n，于是，查找成功的平均查找ASL===⑵時(shí)間復(fù)雜度為O(n)。這就是說，查找成功的平均比較次數(shù)約為表長(zhǎng)的一半。⑶若k值不在表中，則必須進(jìn)行n+1次比較之后才能確定查找失敗。⑷另處:當(dāng)n較大時(shí)，ASL值較大，查找的效率較低。⑸順序查找的特點(diǎn):①算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無任何要求:

無論是用向量還是用鏈表來存放結(jié)點(diǎn)，也無論結(jié)點(diǎn)之間是否按關(guān)鍵字有序或無序，它都同樣適用。②順序查找的缺點(diǎn):

查找效率低，當(dāng)n較大時(shí)，不宜采用順序查找，而必須尋求更好的查找方法。8.2.2二分查找1.二分查找的基本思想:⑴二分查找，也稱折半查找，它是一種高效率的查找方法。

①

二分查找有條件限制：要求表必須用向量作存貯結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序(升序或降序均可)。假設(shè)表中元素為升序排列。

②二分查找的基本思想是：首先將待查值K與有序表R[1]到R[n]的中點(diǎn)

mid上的關(guān)鍵字R[mid].key進(jìn)行比較:a.若相等，則查找成功；

b.否則，若R[mid].key>k，則在R[1]到R[mid-1]中繼續(xù)查找，若有

R[mid].key<k，則在R[mid+1]到R[n]中繼續(xù)查找。⑵每通過一次關(guān)鍵字的比較，區(qū)間的長(zhǎng)度就縮小一半，區(qū)間的個(gè)數(shù)就增加一倍，如此不斷進(jìn)行下去，直到找到關(guān)鍵字為K的元素；若當(dāng)前的查找區(qū)間為空(表示查找失敗)。從上述查找思想可知，每進(jìn)行一次關(guān)鍵字比較，區(qū)間數(shù)目增加一倍，故稱為二分（區(qū)間一分為二），而區(qū)間長(zhǎng)度縮小一半，故也稱為折半（查找的范圍縮小一半）。2．二分查找算法實(shí)現(xiàn)intbinsearch(nodeR[n+1],elemtypek){intlow=1,high=n;while(low<=high){intmid=(low+high)/2;//取區(qū)間中點(diǎn)

if(R[mid].key==k)returnmid;//查找成功

elseif(R[mid].key>k)

high=mid-1;//在左子區(qū)間中查找

elselow=mid+1;//在右子區(qū)間中查找

}return0;//查找失敗

}例如，假設(shè)給定有序表中關(guān)鍵字為8,17,25,44,68,77,98,100,115,125，將查找K=17和K=120的情況描述為圖8-1及圖8-2形式。3.二分查找的性能分析:

⑴用二叉樹來描述二分查找過程:

把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹

⑵左子區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。例如:圖8-1給定的關(guān)鍵字序列:8,17,25,44,68,77,98,100,115,125，的判定樹見圖8-3。從圖8-3可知:①查找根結(jié)點(diǎn)68，需一次查找②查找17和100，各需二次查找③查找8、25、77、115各需三次查找④查找44、98、125各需四次查找。⑤結(jié)論：二叉樹第K層結(jié)點(diǎn)的查找次數(shù)各為k次(根結(jié)點(diǎn)為第1層)，而第k層結(jié)點(diǎn)數(shù)最多為2k-1個(gè)。假設(shè):該二叉樹的深度為h，則二分查找的成功的平均查找長(zhǎng)度為（假設(shè)每個(gè)結(jié)點(diǎn)的查找概率相等）：ASL==1/n≤1/n(1+2﹡2+3﹡22+…+h﹡2h-1）①在最壞情形下，上面的不等號(hào)將會(huì)成立，并根據(jù)二叉樹的性質(zhì)，最大的結(jié)點(diǎn)數(shù)n=2h-1，h=log2(n+1)

②可以得到平均查找長(zhǎng)度:ASL=(n+1)/nlog2(n+1)-1③log2(n+1)-1可以作為二分查找成功時(shí)的平均查找長(zhǎng)度它的時(shí)間復(fù)雜度為O(log2n)。4.二分查找的優(yōu)缺點(diǎn):

⑴

優(yōu)點(diǎn):

比較次數(shù)較順序查找少,查找速度快,

執(zhí)行效率高。

⑵缺點(diǎn)：表的存儲(chǔ)結(jié)構(gòu)只能是順序存儲(chǔ)，不能是鏈?zhǔn)酱鎯?chǔ)，且表中元素必須是有序的。8.2.3索引查找1.索引查找的思想⑴索引查找(分級(jí)查找):

它既是一種查找方法，又是一種存貯方法，稱為索引存貯。例如:在漢語字典中查找某個(gè)漢字時(shí):

①若知道某個(gè)漢字讀音，則可以先在音節(jié)表中查找到對(duì)應(yīng)正文中的頁碼，然后再在正文中所對(duì)應(yīng)的頁中查出待查的漢字②若知道該漢字的字形，但不知道讀音，則可以先在部首表中根據(jù)字的部首查找到對(duì)應(yīng)檢字表中的頁碼，再在檢字表中根據(jù)字的筆畫找到該漢字所在的頁碼。③整個(gè)字典就是索引查找的對(duì)象，字典的正文是字典的主要部分，被稱之為主表，而檢字表，部首表和音節(jié)表都是為了方便查找主表而建立的索引，所以被稱之為索引表。④在索引查找中:

主表只有一個(gè):包含的是待查找的內(nèi)容，索引表可以有多個(gè):包含一級(jí)索引，二級(jí)索引……，所需的級(jí)數(shù)可根據(jù)具體問題而定。如:剛才的利用讀音查找漢字為一級(jí)索引，利用字形查找漢字為二級(jí)索引（部首表→檢字表→漢字）。我們僅討論一級(jí)索引。⑵索引查找是在線性表（主表）的索引存貯結(jié)構(gòu)上進(jìn)行的，而索引存貯的基本思想是：①首先將一個(gè)線性表（主表）按照一定的規(guī)則分成若干個(gè)邏輯上的子表，并為每個(gè)子表分別建立一個(gè)索引項(xiàng)，由所有這些索引項(xiàng)得到主表的一個(gè)索引表，②可采用順序或鏈接的方法來存儲(chǔ)索引表和各個(gè)子表。③索引表中的每個(gè)索引項(xiàng)通常包含三個(gè)域：一是索引值域:用來存儲(chǔ)標(biāo)識(shí)對(duì)應(yīng)子表的索引值，它相當(dāng)于記錄的關(guān)鍵字，在索引表中由此索引值來唯一標(biāo)識(shí)一個(gè)索引項(xiàng)（子表）；二是子表的開始位置:用來存儲(chǔ)對(duì)應(yīng)子表的第一個(gè)元素的存儲(chǔ)位置；三是子表的長(zhǎng)度:用來存儲(chǔ)對(duì)應(yīng)子表的元素個(gè)數(shù)。例如，設(shè)有一個(gè)學(xué)校部分教師檔案表如表8-1所示，設(shè)編號(hào)為主關(guān)鍵字，則該表可以用一個(gè)線性表L=（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10）來表示，其中ai(1≤i≤n)表示第i位教師的信息（包含有編號(hào)，姓名，部門，職稱），而它的索引表可以按部門進(jìn)行，也可以按職稱進(jìn)行，按部門的索引表中有4個(gè)子表，分別為：計(jì)算機(jī)系J=（a1,a2,a3,a4）電工系D=(a5,a6,a7)管理系G=(a8,a9)成教部C=(a10)該4個(gè)子表示成一個(gè)索引表如表8-2所示。

表8-1教師檔案表

編號(hào)

姓名

部門

職稱J001趙一計(jì)算機(jī)系教授J002錢二計(jì)算機(jī)系講師J003張三計(jì)算機(jī)系副教授J004李四計(jì)算機(jī)系助教D001王五電工系講師D002孫六電工系助教D003劉七電工系副教授G001朱八管理系教授G002楊九管理系講師C001羅十成教部副教授表8-2按部門的索引表J04D43G72C91indexstartlength若按職稱進(jìn)行索引，則得到的索引表中也有4個(gè)子表，分別為：

Jiaosou=(a1,a8)FuJiaosou=(a3,a7,a10)Jiangshi=(a2,a5,a9)Zhujiao=(a4,a6)這時(shí)的主表用順序存貯不太方便，因相同職稱的教師沒有連在一起，故用鏈?zhǔn)酱鎯?chǔ)得到主表較方便。具體的存貯如圖8-4所示。在圖8-4中，箭頭上面的數(shù)字表示該元素在主表中的下標(biāo)位置（指針），每個(gè)子表中最后個(gè)元素的指針為-1，表示為空指針。于是，可以得到如表8-3所示的職稱索引表。

表8-3按職稱的索引表

indexstartlength教授02副教授23

講師13

助教32索引查找的基本思想如下：第一步，在索引表中按index域查找所給值K1，這時(shí)可得到子表起始位置start和長(zhǎng)度length，若找不到K1，結(jié)束查找，表示查找不成功。第二步，在主表的start位置開始，長(zhǎng)度為length的范圍內(nèi)查找所給值K2，若找到，查找成功，否則，查找不成功。例如，對(duì)于按部門的索引查找，主表可以用順序存貯，假設(shè)K1=“D”，“D”代電工系，K2=“孫六”，則先在表8-2的索引表中找到的index域?yàn)椤癉”的項(xiàng)，得到start=4，length=3，然后從主表的第4個(gè)位置開始（即a5）找姓名為“孫六”的人，則在主表的第5個(gè)位置可以找到，故查找成功。若假設(shè)K1=“D”，K2=“楊九”，則索引表的查找與上面相同，然后在主表的第4個(gè)位置開始查找，沒找到，進(jìn)入第5個(gè)位置查找，還沒找到進(jìn)入第6位置查找，仍然沒找到，但查找的length=3，既只允許3次查找，故查找不成功。若假設(shè)K1=“F”，K2=“張三”，則首先在索引表中就找不到“F”，故無需進(jìn)入主表進(jìn)行查找，查找不成功。3.索引查找的性能分析由于索引查找中涉及到兩方面查找，第一個(gè)是索引表的查找，第二個(gè)是主表的查找，假設(shè)兩種查找都按順序查找方式進(jìn)行，則索引表的平均查找長(zhǎng)度為(m+1)/2，主表中的平均查找長(zhǎng)度為（s+1）/2，(m為索引表的長(zhǎng)度，S為主表中相應(yīng)子表的長(zhǎng)度)，則索引查找的平均查找長(zhǎng)度為：ASL=(m+1)/2+(s+1）/2。若假定每個(gè)子表具有相同的長(zhǎng)度，而主表的長(zhǎng)度為n，則有n=m.s，這時(shí)當(dāng)s=時(shí)，索引查找具有最小的平均查找長(zhǎng)度，即ASL=1+。從該公式可以看出，索引查找的性能優(yōu)先順序查找，但比二分查找要差，時(shí)間復(fù)雜度介于O(log2n)~O(n)之間。8.2.4分塊查找

1.分塊查找的思想:⑴分塊查找實(shí)際上就是一種索引查找，但查找的性能更優(yōu)先于索引查找。⑵分塊查找的索引表是一個(gè)有序表，故可以用二分查找來代替順序查找實(shí)現(xiàn)索引表的快速查找。⑶具體實(shí)現(xiàn)：將一個(gè)含有n個(gè)元素的主表分成m個(gè)子表，但要求子表之間元素是按關(guān)鍵字有序排列的，而子表中元素可以無序的，然后建立索引表⑷索引表中索引域的值用每個(gè)子表最大關(guān)鍵字代替，則可以按索引查找思想找到表中元素。例如，給定關(guān)鍵字序列如下：18,7,26,34,15,42,36,70,60,55,83,90,78,72,74，假設(shè)m=3，s=5，即將該序序分成3個(gè)子表，每個(gè)子表有5個(gè)元素，則得到的主表和索引表如圖8-5所示。8．3樹表查找8.3.1二叉排序樹查找1．什么是二叉排序樹二叉排序樹（BinarySortingTree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：(1)若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；(2)若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字；(3)左、右子樹本身又都是一棵二叉排序樹。2．二叉排序樹的數(shù)據(jù)類型描述和第六章類似，可以用一個(gè)二叉鏈表來描述一棵二叉排序樹，具體為：

structBtreenode{elemtypedata;//代表關(guān)鍵字

Btreenode*left,*right;//代表左、右孩子

};3．二叉排序樹的基本運(yùn)算（1）二叉排序樹的插入若二叉排序樹為空，則作為根結(jié)點(diǎn)插入，否則，若待插入的值小于根結(jié)點(diǎn)值，則作為左子樹插入，否則作為右子樹插入，算法描述為：voidInsert

(Btreenode*BST,elemtypeX){if(BST==NULL){Btreenode*p=newBtreenode;

p->data=X;p->left=p->right=NULL;BST=p;}

elseif(BST->data>=X)

Insert(BST->left,X);//在左子樹中扦入

elseInsert(BST->right,X);//在右子樹中扦入}（2）二叉排序樹的建立只要反復(fù)調(diào)用二叉排序樹的扦入算法即可，算法描述為：Btreenode*Creat(intn)//建立含有n個(gè)結(jié)點(diǎn)的二叉排序樹{Btreenode*BST=NULL;for(inti=1;i<=n;i++){cin>>x;//輸入關(guān)鍵字序列

Insert(BST,x);}returnBST;}例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖8-6所示。（注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二叉排序樹也不一樣）4．二叉排序樹上的查找（1）二叉排序樹的查找思想若二叉排樹為空，則查找失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點(diǎn)時(shí)，還沒有找到待找結(jié)點(diǎn)，則查找不成功。（2）二叉排序樹查找的算法實(shí)現(xiàn)Btreenode*find(Btreenode*BST,elentypex)

//在以BST為根指針的二叉排隊(duì)樹中查找值為x的結(jié)點(diǎn){if(BST==NULL)returnNULL;//查找失敗

else{if(BST->data==x)//查找成功

returnBST;

elseif(BST->data>x)//進(jìn)入左子樹查找

returnfind(BST->left,x);

else//進(jìn)入右子樹查找

returnfind(BST->right,x);}}5．二叉排序樹查找的性能分析在二叉排序樹查找中，成功的查找次數(shù)不會(huì)超過二叉樹的深度，而具有n個(gè)結(jié)點(diǎn)的二叉排序樹的深度，最好為log2n，最壞為n。因此，二叉排序樹查找的最好時(shí)間復(fù)雜度為O(log2n)，最壞的時(shí)間復(fù)雜度為O(n)，一般情形下，其時(shí)間復(fù)雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。8.3.2平衡二叉樹查找1．平衡二叉樹的概念平衡二叉樹(balancedbinarytree)是由阿德爾森一維爾斯和蘭迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又稱為AVL樹。若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的深度之差的絕對(duì)值不超過1，則稱這樣的二叉樹為平衡二叉樹。將該結(jié)點(diǎn)的左子樹深度減去右子樹深度的值，稱為該結(jié)點(diǎn)的平衡因子(balancefactor)。也就是說，一棵二叉排序樹中，所有結(jié)點(diǎn)的平衡因子只能為0、1、-1時(shí)，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹。如圖8-8所示二叉排序樹，是一棵平衡二叉樹，而如圖8-9所示二叉排序樹，就不是一棵平衡二叉樹。2.非平衡二叉樹的平衡處理若一棵二叉排序樹是平衡二叉樹，扦入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹，這時(shí)，就可以對(duì)該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。處理的原則應(yīng)該是處理與扦入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡處理。（1）LL型的處理(左左型)如圖8-10所示，在C的左孩子B上扦入一個(gè)左孩子結(jié)點(diǎn)A，使C的平衡因子由1變成了2，成為不平衡的二叉樹。這時(shí)的平衡處理為：將C順時(shí)針旋轉(zhuǎn)，成為B的右子樹，而原來B的右子樹則變成A的左子樹，待扦入結(jié)點(diǎn)A作為B的左子樹。(注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)的平衡因子)（2）RR型的處理(右右型)如圖8-12所示，在A的右孩子B上扦入一個(gè)右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時(shí)的平衡處理為：將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待扦入結(jié)點(diǎn)C成為B的右子樹。（3）RL型的處理(右左型)如圖8-13所示，在A的右孩子C上扦入一個(gè)左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時(shí)的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3)種情形RR型處理。（4）LR型的處理(左右型)如圖8-11所示，在C的左孩子A上扦入一個(gè)右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C之間，使之成為L(zhǎng)L型，然后按第(1)種情形LL型處理。例8-2，給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹。分析：平衡二叉樹實(shí)際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見圖8-14。3．平衡二叉樹的查找及性能分析平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找性能優(yōu)于二叉排序樹，不會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排