建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自公眾號“讀芯術(shù)”(ID：AI_Discovery)。
創(chuàng)新互聯(lián)是一家專業(yè)從事成都網(wǎng)站制作、做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計的品牌網(wǎng)絡(luò)公司。如今是成都地區(qū)具影響力的網(wǎng)站設(shè)計公司,作為專業(yè)的成都網(wǎng)站建設(shè)公司,創(chuàng)新互聯(lián)依托強大的技術(shù)實力、以及多年的網(wǎng)站運營經(jīng)驗,為您提供專業(yè)的成都網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)及網(wǎng)站設(shè)計開發(fā)服務(wù)！
生活中，我們經(jīng)常需要找東西或做決定，一個簡單的方法就是將選擇一分為二。假設(shè)你在玩“猜猜我是誰”的游戲，目標(biāo)是猜測你的對手所選擇的角色。你就可以問他們這樣的問題，比如：
- 你的角色是男性還是女性?
- 男性。好，那他有胡子嗎?
- 沒有。好，他戴帽子嗎?
我們在每一步都繼續(xù)推斷我們的選擇。同理，二叉搜索樹通過在每一步都減少選項來幫助找到想要的東西。
首先，二叉搜索樹到底是什么?
二叉搜索樹(BST)是一種特殊類型的樹形數(shù)據(jù)結(jié)構(gòu)，由節(jié)點及其子節(jié)點組成，子節(jié)點也被視作“后代”，可以把它想象成一棵倒置的樹或者是樹的根部。
每個節(jié)點最多只能有2個子節(jié)點：左節(jié)點和右節(jié)點。為了使它成為一個有效的二叉搜索樹，左節(jié)點的值必須總是小于母節(jié)點，而右節(jié)點的值必須總是大于母節(jié)點。沒有任何間隙的BST，即每個節(jié)點都有一個左節(jié)點和一個右節(jié)點的二叉搜索樹，被稱為“完美”樹。
在完美樹中，當(dāng)遍歷樹時，每個級別中的節(jié)點數(shù)會翻倍，將前面的所有節(jié)點相加并在該數(shù)字上再添加“1”可以得出底層的節(jié)點總數(shù)。
當(dāng)在平衡二叉搜索樹中搜索一個元素時，平均需要花費額的時間為O(log n)，在最壞的情況下，需要O(n)。你可以把在二叉搜索樹中的搜索看作是“選擇你自己的冒險”模型，從頂部節(jié)點開始，然后沿著樹向下，在到達(dá)的每個節(jié)點問同樣的2個問題。
- 我要找的值是否小于當(dāng)前節(jié)點?如果是，向左走。
- 我要找的值是否大于當(dāng)前節(jié)點?如果是，向右走。
插入和刪除也非常快，平均花費O(log n)的時間。但有一個缺點就是不能像數(shù)組那樣獲得隨機元素。
什么時候可以使用二叉搜索樹?
假設(shè)你需要為Facebook這樣的社交媒體應(yīng)用程序設(shè)計一個數(shù)據(jù)庫。該數(shù)據(jù)庫需要處理數(shù)百萬個用戶名，并且需要在登錄期間快速檢索到其中一個用戶名。由于每天都有新注冊或刪除的賬戶，你也需要方便進(jìn)行插入和刪除的操作。
通過一個排序過的數(shù)組進(jìn)行二分搜索會非?？?需要花費O(log n)時間)，但是插入或刪除一個用戶名會導(dǎo)致整個數(shù)組重新排序，需要花費O(n)時間，這取決于數(shù)組的大小，可能會相對慢一些。如果我們使用二叉搜索樹，插入或刪除的時間會快得多(花費O(log n)時間)。
如果有一個帶有名字的二叉搜索樹(比如這個《海底總動員》的樹)，就可以按字母順序排列。
在字母表中，Dory在Marlin之前，所以它是左邊的節(jié)點，而Moonfish在Marlin之后，所以它是右邊的節(jié)點。同樣地，在下一層搜索也遵循這個規(guī)律。Bruce在Crush之前，也在Dory和Marlin之前。Darla在Crush之后，但在Dory和Marlin之前。
現(xiàn)在準(zhǔn)備好，是時候?qū)ふ襈emo了!
尋找Nemo!
假設(shè)已經(jīng)有一個有效的二叉搜索樹，并且需要找到Nemo。因為我們知道樹中的節(jié)點是按字母順序排序的，所以這應(yīng)該相當(dāng)簡單。
從Marlin開始，左邊是Dory，右邊是Moonfish。我們知道Nemo在字母表中位于Marlin之后，所以我們將遍歷到正確的節(jié)點(Moonfish)。Nemo按字母順序是排在Moonfish之后的，所以繼續(xù)往下看Moonfish的右子節(jié)點。很幸運，那是…Nemo!找到Nemo了!
效率很高。二叉搜索樹減少了整個搜索過程的時間復(fù)雜性!如果樹沒有分類，只是一個普通的樹形結(jié)構(gòu)呢?或者要證實這是個二叉搜索樹呢?目前有兩種不同的搜索技術(shù)可以實現(xiàn)這一點。
什么是廣度優(yōu)先搜索?
廣度優(yōu)先搜索是一種在樹(或圖形)中一次遍歷一級的方法，每次都從左到右在節(jié)點之間移動。
在《海底總動員》的例子中，Marlin首先會問Dory，“你知道我兒子Nemo在哪里嗎?”如果它說不，Marlin就會問Moonfish同樣的問題。如果它也說不，Marlin會再下一層，問Crush、Gill和Mr. Ray，然后Marlin就找到Nemo了!
廣度優(yōu)先搜索
如果在Mr. Ray之后沒有找到Nemo，Marlin會到下一級詢問Bruce和Darla等等。使用廣度優(yōu)先搜索可以找到起始節(jié)點(Marlin)和目標(biāo)節(jié)點(Nemo)之間的最短距離。時間復(fù)雜度是O(n)，因為在最壞的情況下，需要檢查每個節(jié)點才能找到Nemo。
什么是深度優(yōu)先搜索?
深度優(yōu)先搜索(Depth first search)是一種從頂部節(jié)點一直向下遍歷到其最遠(yuǎn)子節(jié)點的樹(或圖形)的方法，然后在未找到目標(biāo)節(jié)點時再回去并嘗試其他路徑。
在《海底總動員》的例子中，Marlin首先會問Dory “你知道Nemo在哪里嗎?” 如果她不知道，他就會問Crush同樣的問題，因為Crush是Dory最左邊的子節(jié)點。如果Crush也說沒有，Marlin將移動到下一級去問Bruce，盡管他害怕成為鯊魚的點心，但也會問問他有沒有見到自己的兒子。
深度優(yōu)先搜索
如果Bruce說沒看到Nemo，并向Marlin保證“魚是朋友，不是食物”，Marlin就需要回到上級，尋找另一個他還沒有問到的節(jié)點。回到Crush那里，他會發(fā)現(xiàn)下一步應(yīng)該問Darla。由于Crush的所有后代現(xiàn)在都被審問過了，Marlin會回到Dory那里，檢查她其余的“后代”。Marlin需要把每個角色詢問一遍后才能找到Nemo。
深度優(yōu)先搜索順序
與廣度優(yōu)先搜索一樣，深度優(yōu)先搜索也包括時間復(fù)雜度O(n)，但空間復(fù)雜度可能有所不同。深度優(yōu)先搜索通常占用較少的內(nèi)存或空間，假設(shè)可以在遍歷整個樹之前找到目標(biāo)節(jié)點。
由于二叉搜索樹中的每增加一級節(jié)點會加倍(至少對于平衡樹而言)，如果丟失的節(jié)點(Nemo)位于樹的較低位置，則可以使用深度優(yōu)先搜索來節(jié)省內(nèi)存。在最壞的情況下，兩種方法的空間復(fù)雜度都是O(n)。
關(guān)于二叉搜索樹以及如何通過代碼實現(xiàn)它們還有很多需要學(xué)習(xí)，但這個有趣的案例會成為你了解數(shù)據(jù)結(jié)構(gòu)的起點。
名稱欄目：什么是二叉搜索樹，如何通過代碼實現(xiàn)它們？
瀏覽路徑：http://m.5511xx.com/article/dphicpg.html
