本文轉(zhuǎn)載自公眾號(hào)“讀芯術(shù)”(ID：AI_Discovery)。

生活中，我們經(jīng)常需要找東西或做決定，一個(gè)簡單的方法就是將選擇一分為二。假設(shè)你在玩“猜猜我是誰”的游戲，目標(biāo)是猜測你的對(duì)手所選擇的角色。你就可以問他們這樣的問題，比如：

• 你的角色是男性還是女性?
• 男性。好，那他有胡子嗎?
• 沒有。好，他戴帽子嗎?

我們?cè)诿恳徊蕉祭^續(xù)推斷我們的選擇。同理，二叉搜索樹通過在每一步都減少選項(xiàng)來幫助找到想要的東西。

[[345440]]

首先，二叉搜索樹到底是什么?

二叉搜索樹(BST)是一種特殊類型的樹形數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)及其子節(jié)點(diǎn)組成，子節(jié)點(diǎn)也被視作“后代”，可以把它想象成一棵倒置的樹或者是樹的根部。

每個(gè)節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)：左節(jié)點(diǎn)和右節(jié)點(diǎn)。為了使它成為一個(gè)有效的二叉搜索樹，左節(jié)點(diǎn)的值必須總是小于母節(jié)點(diǎn)，而右節(jié)點(diǎn)的值必須總是大于母節(jié)點(diǎn)。沒有任何間隙的BST，即每個(gè)節(jié)點(diǎn)都有一個(gè)左節(jié)點(diǎn)和一個(gè)右節(jié)點(diǎn)的二叉搜索樹，被稱為“完美”樹。

在完美樹中，當(dāng)遍歷樹時(shí)，每個(gè)級(jí)別中的節(jié)點(diǎn)數(shù)會(huì)翻倍，將前面的所有節(jié)點(diǎn)相加并在該數(shù)字上再添加“1”可以得出底層的節(jié)點(diǎn)總數(shù)。

當(dāng)在平衡二叉搜索樹中搜索一個(gè)元素時(shí)，平均需要花費(fèi)額的時(shí)間為O(log n)，在最壞的情況下，需要O(n)。你可以把在二叉搜索樹中的搜索看作是“選擇你自己的冒險(xiǎn)”模型，從頂部節(jié)點(diǎn)開始，然后沿著樹向下，在到達(dá)的每個(gè)節(jié)點(diǎn)問同樣的2個(gè)問題。

• 我要找的值是否小于當(dāng)前節(jié)點(diǎn)?如果是，向左走。
• 我要找的值是否大于當(dāng)前節(jié)點(diǎn)?如果是，向右走。

插入和刪除也非常快，平均花費(fèi)O(log n)的時(shí)間。但有一個(gè)缺點(diǎn)就是不能像數(shù)組那樣獲得隨機(jī)元素。

什么時(shí)候可以使用二叉搜索樹?

假設(shè)你需要為Facebook這樣的社交媒體應(yīng)用程序設(shè)計(jì)一個(gè)數(shù)據(jù)庫。該數(shù)據(jù)庫需要處理數(shù)百萬個(gè)用戶名，并且需要在登錄期間快速檢索到其中一個(gè)用戶名。由于每天都有新注冊(cè)或刪除的賬戶，你也需要方便進(jìn)行插入和刪除的操作。

通過一個(gè)排序過的數(shù)組進(jìn)行二分搜索會(huì)非常快(需要花費(fèi)O(log n)時(shí)間)，但是插入或刪除一個(gè)用戶名會(huì)導(dǎo)致整個(gè)數(shù)組重新排序，需要花費(fèi)O(n)時(shí)間，這取決于數(shù)組的大小，可能會(huì)相對(duì)慢一些。如果我們使用二叉搜索樹，插入或刪除的時(shí)間會(huì)快得多(花費(fèi)O(log n)時(shí)間)。

如果有一個(gè)帶有名字的二叉搜索樹(比如這個(gè)《海底總動(dòng)員》的樹)，就可以按字母順序排列。

在字母表中，Dory在Marlin之前，所以它是左邊的節(jié)點(diǎn)，而Moonfish在Marlin之后，所以它是右邊的節(jié)點(diǎn)。同樣地，在下一層搜索也遵循這個(gè)規(guī)律。Bruce在Crush之前，也在Dory和Marlin之前。Darla在Crush之后，但在Dory和Marlin之前。

現(xiàn)在準(zhǔn)備好，是時(shí)候?qū)ふ襈emo了!

尋找Nemo!

假設(shè)已經(jīng)有一個(gè)有效的二叉搜索樹，并且需要找到Nemo。因?yàn)槲覀冎罉渲械墓?jié)點(diǎn)是按字母順序排序的，所以這應(yīng)該相當(dāng)簡單。

從Marlin開始，左邊是Dory，右邊是Moonfish。我們知道Nemo在字母表中位于Marlin之后，所以我們將遍歷到正確的節(jié)點(diǎn)(Moonfish)。Nemo按字母順序是排在Moonfish之后的，所以繼續(xù)往下看Moonfish的右子節(jié)點(diǎn)。很幸運(yùn)，那是…Nemo!找到Nemo了!

效率很高。二叉搜索樹減少了整個(gè)搜索過程的時(shí)間復(fù)雜性!如果樹沒有分類，只是一個(gè)普通的樹形結(jié)構(gòu)呢?或者要證實(shí)這是個(gè)二叉搜索樹呢?目前有兩種不同的搜索技術(shù)可以實(shí)現(xiàn)這一點(diǎn)。

什么是廣度優(yōu)先搜索?

廣度優(yōu)先搜索是一種在樹(或圖形)中一次遍歷一級(jí)的方法，每次都從左到右在節(jié)點(diǎn)之間移動(dòng)。

在《海底總動(dòng)員》的例子中，Marlin首先會(huì)問Dory，“你知道我兒子Nemo在哪里嗎?”如果它說不，Marlin就會(huì)問Moonfish同樣的問題。如果它也說不，Marlin會(huì)再下一層，問Crush、Gill和Mr. Ray，然后Marlin就找到Nemo了!

廣度優(yōu)先搜索

如果在Mr. Ray之后沒有找到Nemo，Marlin會(huì)到下一級(jí)詢問Bruce和Darla等等。使用廣度優(yōu)先搜索可以找到起始節(jié)點(diǎn)(Marlin)和目標(biāo)節(jié)點(diǎn)(Nemo)之間的最短距離。時(shí)間復(fù)雜度是O(n)，因?yàn)樵谧顗牡那闆r下，需要檢查每個(gè)節(jié)點(diǎn)才能找到Nemo。

什么是深度優(yōu)先搜索?

深度優(yōu)先搜索(Depth first search)是一種從頂部節(jié)點(diǎn)一直向下遍歷到其最遠(yuǎn)子節(jié)點(diǎn)的樹(或圖形)的方法，然后在未找到目標(biāo)節(jié)點(diǎn)時(shí)再回去并嘗試其他路徑。

在《海底總動(dòng)員》的例子中，Marlin首先會(huì)問Dory “你知道Nemo在哪里嗎?” 如果她不知道，他就會(huì)問Crush同樣的問題，因?yàn)镃rush是Dory最左邊的子節(jié)點(diǎn)。如果Crush也說沒有，Marlin將移動(dòng)到下一級(jí)去問Bruce，盡管他害怕成為鯊魚的點(diǎn)心，但也會(huì)問問他有沒有見到自己的兒子。

深度優(yōu)先搜索

如果Bruce說沒看到Nemo，并向Marlin保證“魚是朋友，不是食物”，Marlin就需要回到上級(jí)，尋找另一個(gè)他還沒有問到的節(jié)點(diǎn)。回到Crush那里，他會(huì)發(fā)現(xiàn)下一步應(yīng)該問Darla。由于Crush的所有后代現(xiàn)在都被審問過了，Marlin會(huì)回到Dory那里，檢查她其余的“后代”。Marlin需要把每個(gè)角色詢問一遍后才能找到Nemo。

深度優(yōu)先搜索順序

與廣度優(yōu)先搜索一樣，深度優(yōu)先搜索也包括時(shí)間復(fù)雜度O(n)，但空間復(fù)雜度可能有所不同。深度優(yōu)先搜索通常占用較少的內(nèi)存或空間，假設(shè)可以在遍歷整個(gè)樹之前找到目標(biāo)節(jié)點(diǎn)。

由于二叉搜索樹中的每增加一級(jí)節(jié)點(diǎn)會(huì)加倍(至少對(duì)于平衡樹而言)，如果丟失的節(jié)點(diǎn)(Nemo)位于樹的較低位置，則可以使用深度優(yōu)先搜索來節(jié)省內(nèi)存。在最壞的情況下，兩種方法的空間復(fù)雜度都是O(n)。

關(guān)于二叉搜索樹以及如何通過代碼實(shí)現(xiàn)它們還有很多需要學(xué)習(xí)，但這個(gè)有趣的案例會(huì)成為你了解數(shù)據(jù)結(jié)構(gòu)的起點(diǎn)。