|
在計(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 > 《算法》
