在計(jì)算機(jī)許多應(yīng)用領(lǐng)域中,查找操作都是十分重要的研究技術(shù)。查找效率的好壞直接影響應(yīng)用軟件的性能,而查找算法又分靜態(tài)查找和動(dòng)態(tài)查找。 靜態(tài)查找:數(shù)據(jù)集合穩(wěn)定,不需要添加,刪除元素的查找操作。 動(dòng)態(tài)查找:數(shù)據(jù)集合在查找的過(guò)程中需要添加或刪除元素。 順序查找:大家都知道,最簡(jiǎn)單的查找方法就是順序查找 (一個(gè)接一個(gè)得查下去)。這種線性結(jié)構(gòu)的查找效率是最低的,時(shí)間復(fù)雜度在O(N)數(shù)量級(jí),最壞的情況莫過(guò)于所有數(shù)據(jù)都 找遍了,還是沒(méi)找到。 或許你會(huì)想到不一定每個(gè)數(shù)據(jù)都要找一次。 折半查找就是一個(gè)不錯(cuò)的例子,對(duì)有序的線性數(shù)據(jù)進(jìn)行查找,每一次都找1/2的部分,查找的次數(shù)當(dāng)然就大大減少了。時(shí)間復(fù)雜度在O(log2 N)數(shù)量級(jí)上。 但是如果某些特定的數(shù)據(jù)一年可能才查找?guī)状危行?shù)據(jù)一天可能都要查找?guī)装俅?,這種折半查找效率又不行了 那就針對(duì)被查找的概率構(gòu)建數(shù)據(jù)結(jié)構(gòu)吧 靜態(tài)最優(yōu)查找樹(shù)/次優(yōu)查找樹(shù):次優(yōu)查找樹(shù)的思想就是在折半查找二叉樹(shù)的基礎(chǔ)上求解一個(gè)帶權(quán)(數(shù)據(jù)概率)路徑長(zhǎng)度最小/近視最小的樹(shù)??傮w上說(shuō),靜態(tài)最優(yōu)/次優(yōu)查找樹(shù)的時(shí)間復(fù) 雜度也在 O(log2 N)數(shù)量級(jí)上(特別是在數(shù)據(jù)具有查找概率的情況下也能保證這個(gè)效率) 此外,還有一些別的靜態(tài)查找結(jié)構(gòu):索引順序表的分塊查找,線性沖突再散列的hash表的查找等等。 上面介紹查找表都屬于靜態(tài)查找結(jié)構(gòu),也就是說(shuō)當(dāng)需要查找的數(shù)據(jù)集合動(dòng)態(tài)變化的時(shí)候,這些結(jié)構(gòu)都很不方便。 比如:折半查找: 當(dāng)查找過(guò)程中沒(méi)有發(fā)現(xiàn)元素A的時(shí)候,需要?jiǎng)討B(tài) 添加元素A,此時(shí)整個(gè)有序表將面臨重新排序的問(wèn)題。 靜態(tài)最優(yōu)查找樹(shù): 新增元素不光要重新排序,而且原有的整棵帶權(quán)路徑長(zhǎng)度最小值的樹(shù)也將重建(最優(yōu)解變化了)。這在代價(jià)上是沉重的,這也是為什么 靜態(tài)最優(yōu)查找樹(shù)并不適 合實(shí)際應(yīng)用的巨大缺陷了。 正是由于實(shí)際應(yīng)用中,很多時(shí)候需要在查找的同時(shí)進(jìn)行添加,刪除操作。因此便捷的動(dòng)態(tài)查找結(jié)構(gòu)就十分的重要了,例如:二叉查找樹(shù),平衡二叉樹(shù),紅黑樹(shù),B-樹(shù)/B+樹(shù)。 二叉查找樹(shù):查找一個(gè)數(shù)不必遍歷所有結(jié)點(diǎn)數(shù)據(jù),查找效率很高。但是最壞情況下,二叉查找樹(shù)蛻變成一個(gè)單支數(shù),樹(shù)的深度為n,其查找時(shí)間復(fù)雜度與順序查找一樣O(N)。最好的 情況是二叉排序樹(shù)的形態(tài)和折半查找的判定樹(shù)相同,其平均查找長(zhǎng)度和log2(N)成正比 (O(log2(n)))。 效率總結(jié) : 查找最好時(shí)間復(fù)雜度O(logN),最壞時(shí)間復(fù)雜度O(N)。 插入刪除操作算法簡(jiǎn)單,時(shí)間復(fù)雜度與查找差不多 所以平衡查找樹(shù)就解決了二叉查找樹(shù)不平衡的問(wèn)題 平衡二叉樹(shù):又稱(chēng) AVL樹(shù)。 它除了具備二叉查找樹(shù)的基本特征之外,還具有一個(gè)非常重要的特點(diǎn):它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù),且左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值( 平衡因子 ) 不超過(guò)1。也就是說(shuō)AVL樹(shù)每個(gè)節(jié)點(diǎn)的平衡因子只可能是-1、0和1(左子樹(shù)高度減去右子樹(shù)高度)。AVL保持平衡的基本思想就是在插入一個(gè)數(shù)據(jù)節(jié)點(diǎn)時(shí),首先檢查是否 破壞了平衡,若破壞,則找出其中的最小不平衡二叉樹(shù),在保持二叉排序樹(shù)特性的情況下,調(diào)整最小不平衡子樹(shù)中節(jié)點(diǎn)之間的關(guān)系,以達(dá)到新的平衡。所謂最小不平衡子樹(shù) 指離插 入節(jié)點(diǎn)最近且以平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)作為根的子樹(shù)。 這里調(diào)整的方法就是4鐘旋轉(zhuǎn)方法,根據(jù)不同的情況進(jìn)行調(diào)整。平衡二叉樹(shù)的優(yōu)勢(shì)在于不會(huì)出現(xiàn)普通二叉查找樹(shù)的最 差情況。其查找的時(shí)間復(fù)雜度為O(logN)。但是為了保證高度平衡,動(dòng)態(tài)插入和刪除的代價(jià)也隨之增加,其查找代價(jià)也與樹(shù)高密切相關(guān),還有就是在大量數(shù)據(jù)情況下,所有二叉查找 結(jié)構(gòu)都不適合,因?yàn)閷⒈热鐜譍數(shù)據(jù)在內(nèi)存中組織成一棵平衡二叉樹(shù)基本不可能。 效率總結(jié) : 查找的時(shí)間復(fù)雜度維持在O(logN),不會(huì)出現(xiàn)最差情況 AVL樹(shù)在執(zhí)行每個(gè)插入操作時(shí)最多需要1次旋轉(zhuǎn),其時(shí)間復(fù)雜度在O(logN)左右。 AVL樹(shù)在執(zhí)行刪除時(shí)代價(jià)稍大,執(zhí)行每個(gè)刪除操作的時(shí)間復(fù)雜度需要O(2logN)。 正是上面提到的缺點(diǎn),就有了深度有界查找樹(shù)來(lái)解決。 紅黑樹(shù):由于紅黑樹(shù)的一些性質(zhì)就決定了紅黑樹(shù)的查找長(zhǎng)度最多不超過(guò)2log(n+1),因此其查找時(shí)間復(fù)雜度也是O(log N)級(jí)別的。每一個(gè)紅黑樹(shù)也是一個(gè)特化的二叉查找樹(shù),因此紅 黑樹(shù)上的查找操作與普通二叉查找樹(shù)上的查找操作相同。 然而,在紅黑樹(shù)上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不 再符合紅黑樹(shù)的性質(zhì)?;謴?fù)紅黑樹(shù)的屬性需要少量(O(log n))的顏 色變更(實(shí)際是非??焖俚?和不超過(guò)三次樹(shù)旋轉(zhuǎn)(對(duì)于插入操作是兩次)。 雖然插入和刪除很復(fù)雜,但操作時(shí)間仍可以保持為 O(log n) 次,所以紅黑樹(shù)的優(yōu)勢(shì)很明顯。 效率總結(jié) : 查找效率最好情況下時(shí)間復(fù)雜度為O(logN),但在最壞情況下比AVL要差一些,但也遠(yuǎn)遠(yuǎn)好于BST。 插入和刪除操作改變樹(shù)的平衡性的概率要遠(yuǎn)遠(yuǎn)小于AVL(RBT不是高度平衡的)。因此需要的旋轉(zhuǎn)操作的可能性要小,而且一旦需要旋轉(zhuǎn),插入一個(gè)結(jié)點(diǎn)最多只需要旋轉(zhuǎn) 2次,刪除最多只需要旋轉(zhuǎn)3次(小于AVL的刪除操作所需要的旋轉(zhuǎn)次數(shù))。雖然變色操作的時(shí)間復(fù)雜度在O(logN),但是實(shí)際上,這種操作由于簡(jiǎn)單所需要的代價(jià)很小。 上面總結(jié)的都是典型的二叉查找樹(shù)結(jié)構(gòu),其查找的時(shí)間復(fù)雜度與樹(shù)高相關(guān)。那么降低樹(shù)高自然對(duì)查找效率是有所幫助的。另外還有一個(gè)比較實(shí)際的問(wèn)題:就是大量數(shù)據(jù)存儲(chǔ)中,實(shí) 現(xiàn)查詢這樣一個(gè)實(shí)際背景下,平衡二叉樹(shù)由于樹(shù)深度過(guò)大而造成磁盤(pán)IO讀寫(xiě)過(guò)于頻繁,進(jìn)而導(dǎo)致效率低下。進(jìn)而提出了多路查找樹(shù) 平衡多路查找樹(shù):其性質(zhì)就不在介紹了,主要思想就是每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)元素,但是不是無(wú)限多,不然就成了節(jié)點(diǎn)內(nèi)部的線性查找了,另外就是采用多叉樹(shù)。一棵m階的平衡多路查 找樹(shù)和平衡二叉樹(shù)不同的是,每次插入一個(gè)關(guān)鍵字并不是在樹(shù)中上添加一個(gè)節(jié)點(diǎn),而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字,若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1,則插 入完成。否則,要產(chǎn)生結(jié)點(diǎn)的分裂 。 效率總結(jié): 由于考慮磁盤(pán)儲(chǔ)存結(jié)構(gòu),B樹(shù)的查找、刪除、插入的代價(jià)都遠(yuǎn)遠(yuǎn)要小于任何二叉結(jié)構(gòu)樹(shù)(讀寫(xiě)磁盤(pán)次數(shù)的降低) B+樹(shù):是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種平衡多路查找樹(shù)的變形樹(shù)。B+樹(shù)的葉子結(jié)點(diǎn)包含了所有待查詢關(guān)鍵字,而非終節(jié)點(diǎn)只是作為葉子結(jié)點(diǎn)中最大(最小)關(guān)鍵字的索引。因此B+樹(shù) 的非終結(jié)點(diǎn)沒(méi)有文件內(nèi)容所在物理存儲(chǔ)的地址,而平衡多路查找樹(shù)所有結(jié)點(diǎn)均有文件內(nèi)容所在的磁盤(pán)物理地址。 這個(gè)特點(diǎn)是B+樹(shù)的一個(gè)重要優(yōu)勢(shì)(B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更低,B+樹(shù) 的查詢效率更加穩(wěn)定)所在。B+樹(shù)在數(shù)據(jù)庫(kù),文件系統(tǒng)的索引結(jié)構(gòu)中是十分常用的。 在應(yīng)用背景下,特別是文件結(jié)構(gòu)存儲(chǔ)中。B+樹(shù)的應(yīng)用要更多,其效率也要比B~樹(shù)好 上面介紹的幾種動(dòng)態(tài)查找樹(shù)(二叉查找樹(shù)(BST),平衡二叉查找樹(shù)(AVL),紅黑樹(shù)(RBT),B~/B+樹(shù)(B-tree))都是動(dòng)態(tài)結(jié)構(gòu),在刪除,插入操作的時(shí)候,都不需要徹底重建原始的索 引樹(shù)。最多就是執(zhí)行一定量的旋轉(zhuǎn),變色操作來(lái)有限的改變樹(shù)的形態(tài)。而這些操作所付出的代價(jià)都遠(yuǎn)遠(yuǎn)小于重建一棵樹(shù), 查找的時(shí)間復(fù)雜度大體維持在O(log(N))數(shù)量級(jí)上??赡?nbsp; 有些結(jié)構(gòu)在最差的情況下效率將會(huì)下降很快,比如上面說(shuō)的二叉查找樹(shù)最壞的情況。 |
|
來(lái)自: 昵稱(chēng)9724423 > 《算法》