數(shù)據(jù)結(jié)構(gòu)是可以被串起來的，每新出現(xiàn)一種新的數(shù)據(jù)結(jié)構(gòu)或者算法肯定是前面的存在一些不足，新提出的可以對其進行改進，多問自己為什么要有這種數(shù)據(jù)結(jié)構(gòu)/算法，這樣子就有利于將知識點串聯(lián)起來，知識點不再是孤立地散布在大腦中，調(diào)用起來也會更快。

在查找的章節(jié)，可以按照如下的知識點串聯(lián)起來，學(xué)起來會更加容易一點。

查找數(shù)據(jù)結(jié)構(gòu)和算法

首先介紹了順序表（可以理解為數(shù)組）查找，首先從最簡單的數(shù)據(jù)無序可以找起，其復(fù)雜度為O（n），顯然我們是不滿意的，于是我們可以想到將數(shù)據(jù)進行排序可能會加快查找的速度，接下來是數(shù)據(jù)有序的情況找起，一共有三種查找的方法，二分法、插值法、Fabonacci法，三種方法大同小異，只不過是每次分開數(shù)據(jù)的節(jié)點不同而已，這時的已經(jīng)變?yōu)闀r間復(fù)雜度為O（lgn），當(dāng)然我們在一開始的時候要對數(shù)據(jù)進行排序。這個時候我們還發(fā)現(xiàn)一個問題，順序表查找在刪除和插入的時候時間復(fù)雜度是O（n）（看見有沒有，一路下來都是發(fā)現(xiàn)問題，針對問題設(shè)計新的方案），于是我們引入了搜索二叉樹（BST）。網(wǎng)上搜文的時候發(fā)現(xiàn)有人說搜索二叉樹是為了加快搜索的速度，那么我就要問他，為什么不用有序排序的順序表？搜索二叉樹數(shù)據(jù)結(jié)構(gòu)比起一個簡單的數(shù)組可是要比較復(fù)雜，顯然搜索二叉樹并不是為了加快搜索速度，僅僅為此，我們用有序排序的順序表查找就可以了。甚至嚴(yán)格來說，搜索二叉樹的時間復(fù)雜度跟其高度有關(guān)，不完全是O（lgn）。搜索二叉樹是為了加快順序表刪除和插入操作。引入搜索二叉樹后，我們可知，其搜索、插入、刪除都與其高度有關(guān)，對于滿/完全二叉樹來說，高度接近lgn，但卻存在為單鏈的情況，這時高度為n，各種操作的復(fù)雜度都是O（lgn）。因此我們又引入平衡二叉樹，平衡二叉樹可以盡量平衡整棵二叉樹，注意不是將其弄成滿/完全二叉樹，那這樣子操作起來比較復(fù)雜，我們只要求盡量平衡。每次在插入和刪除節(jié)點的時候，都檢查樹是否違反了平衡二叉樹的定義（平衡因子絕對值小于2），如果是對檢測地方進行旋轉(zhuǎn)，于是得到的樹整體仍然可以比較平衡，高度比較低。那現(xiàn)在總歸可以了吧，各種操作時間復(fù)雜度都是O（lgn）。然而在查找的數(shù)據(jù)多到內(nèi)存裝不下的時候，我們每次判斷一個節(jié)點就要到硬盤進行讀取一次數(shù)據(jù)，這樣子耗時是非常多的，硬盤讀取的速度跟內(nèi)存讀取速度相差10^5倍，大概是1天和1秒的區(qū)別，因此又有了多路查找樹（2-3數(shù)、3-3-4樹、B樹）。多路查找樹在每個節(jié)點放多個數(shù)據(jù)，我們可以一次性讀取多個，“一棵B個樹的階為1001（即一個節(jié)點包含1000個關(guān)鍵字），高度為2，它可以存儲超過10億個關(guān)鍵字......讀取兩次硬盤即可.......”。

數(shù)據(jù)結(jié)構(gòu)

總結(jié)

如果你已經(jīng)對查找的各種數(shù)據(jù)結(jié)構(gòu)建立起了以上的知識結(jié)構(gòu)，那么下次需要遇到查找相關(guān)的問題，你的思路收斂起來是比較快的，而不是像一團漿糊，比如問你。

在解決一個新的問題，我們首先對其進行簡化后模式識別，看該問題跟其他已經(jīng)遇到的問題，學(xué)過的知識點是否有共通之處，如果有我們便能夠?qū)ζ浔容^快地進行解決。（如果沒有，那就真的靠的是智商了，不過大部分情況下，我們還是在腦子搜索是否遇到類似的問題）而識別的快慢，能否識別起來，靠的是我們的學(xué)習(xí)能力，學(xué)習(xí)的時候你是否有將這些知識點進行歸納整理。所以大部分情況下，想問題想的慢可能要歸咎于學(xué)習(xí)能力的問題。