避免孤立的學(xué)習(xí)知識點(diǎn)，要關(guān)聯(lián)學(xué)習(xí)。

　　比如實(shí)際應(yīng)用當(dāng)中，我們經(jīng)常使用的是查找，排序以及增刪改，這在我們的各種管理系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、操作系統(tǒng)等當(dāng)中，十分常用，我們通過這個(gè)線索將知識點(diǎn)串聯(lián)起來：

　　數(shù)組的下標(biāo)尋址十分迅速，但計(jì)算機(jī)的內(nèi)存是有限的，故數(shù)組的長度也是有限的，實(shí)際應(yīng)用當(dāng)中的數(shù)據(jù)往往十分龐大；而且無序數(shù)組的查找最壞情況需要遍歷整個(gè)數(shù)組;后來人們提出了二分查找，二分查找要求數(shù)組的構(gòu)造一定有序，二分法查找解決了普通數(shù)組查找復(fù)雜度過高的問題。任何一種數(shù)組無法解決的問題就是插入、刪除操作比較復(fù)雜，因此，在一個(gè)增刪查改比較頻繁的數(shù)據(jù)結(jié)構(gòu)中，數(shù)組不會(huì)被優(yōu)先考慮

　　普通鏈表由于它的結(jié)構(gòu)特點(diǎn)被證明根本不適合進(jìn)行查找

　　哈希表是數(shù)組和鏈表的折中，同時(shí)它的設(shè)計(jì)依賴散列函數(shù)的設(shè)計(jì)，數(shù)組不能無限長、鏈表也不適合查找，所以也不適合大規(guī)模的查找

　　二叉查找樹因?yàn)榭赡芡嘶涉湵?，同樣不適合進(jìn)行查找

　　AVL樹是為了解決二叉查找樹可能退化成鏈表問題。AVL樹是嚴(yán)格的平衡二叉樹，平衡條件必須滿足(所有節(jié)點(diǎn)的左右子樹高度差的絕對值不超過1)。不管我們是執(zhí)行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉(zhuǎn)來保持平衡，而旋轉(zhuǎn)是非常耗時(shí)的，由此我們可以知道AVL樹適合用于插入與刪除次數(shù)比較少，但查找多的情況。

　　紅黑樹是二叉查找樹和AVL樹的折中。它是一種弱平衡二叉樹，但在每個(gè)節(jié)點(diǎn)增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅或黑(非紅即黑)。通過對任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色的方式的限制，紅黑樹確保沒有一條路徑會(huì)比其它路徑長出兩倍，因此，紅黑樹是一種弱平衡二叉樹(由于是弱平衡，可以看到，在相同的節(jié)點(diǎn)情況下，AVL樹的高度低于紅黑樹)，相對于要求嚴(yán)格的AVL樹來說，它的旋轉(zhuǎn)次數(shù)少，所以對于搜索，插入，刪除操作較多的情況下，我們就用紅黑樹。

　　多路查找樹是大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下，樹節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的(如果元素?cái)?shù)量非常多的話，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了)，這樣導(dǎo)致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進(jìn)而導(dǎo)致查詢效率低下。

　　B樹與自平衡二叉查找樹不同，B樹適用于讀寫相對大的數(shù)據(jù)塊的存儲(chǔ)系統(tǒng)，例如磁盤。它的應(yīng)用是文件系統(tǒng)及部分非關(guān)系型數(shù)據(jù)庫索引。

　　B+樹在B樹基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針(B樹+葉子有序鏈表)，所有關(guān)鍵字都在葉子結(jié)點(diǎn) 中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引;B+樹總是到葉子結(jié)點(diǎn)才命中。通常用于關(guān)系型數(shù)據(jù)庫(如Mysql)和操作系統(tǒng)的文件系統(tǒng)中。

　　B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針, 在B+樹基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3。

　　R樹是用來做空間數(shù)據(jù)存儲(chǔ)的樹狀數(shù)據(jù)結(jié)構(gòu)。例如給地理位置，矩形和多邊形這類多維數(shù)據(jù)建立索引。 Trie樹是自然語言處理中最常用的數(shù)據(jù)結(jié)構(gòu)，很多字符串處理任務(wù)都會(huì)用到。

　　Trie樹本身是一種有限狀態(tài)自動(dòng)機(jī)，還有很多變體。什么模式匹配、正則表達(dá)式，都與這有關(guān)。