今天來(lái)學(xué)習(xí)一種特殊的的二叉樹(shù)二叉查找樹(shù)。二叉查找樹(shù)最大的特點(diǎn)就是支持動(dòng)態(tài)數(shù)據(jù)集合的快速插入、刪除、查找操作。

我們之前說(shuō)過(guò)，散列表也是支持這些操作的，并且散列表的這些操作比二叉查找樹(shù)更高效，時(shí)間復(fù)雜度是 O(1)。既然有了這么高效的散列表，使用二叉樹(shù)的地方是不是都可以替換成散列表呢？有沒(méi)有哪些地方是散列表做不了，必須要用二叉樹(shù)來(lái)做的呢？

二叉查找樹(shù)

二叉查找樹(shù)是二叉樹(shù)中最常用的一種類型，也叫二叉搜索樹(shù)。顧名思義，二叉查找樹(shù)是為了實(shí)現(xiàn)快速查找而生的。不過(guò)，它不僅僅支持快速查找一個(gè)數(shù)據(jù)，還支持快速插入、刪除一個(gè)數(shù)據(jù)。它是怎么做到這些的呢？

這些都依賴于二叉查找樹(shù)的特殊結(jié)構(gòu)。二叉查找樹(shù)要求，在樹(shù)中的任意一個(gè)節(jié)點(diǎn)，其左子樹(shù)中的每個(gè)節(jié)點(diǎn)的值，都要小于這個(gè)節(jié)點(diǎn)的值，而右子樹(shù)節(jié)點(diǎn)的值都大于這個(gè)節(jié)點(diǎn)的值。

1. 二叉查找樹(shù)的查找操作

我們先取根節(jié)點(diǎn)，如果它等于我們要查找的數(shù)據(jù)，那就返回。如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值小，那就在左子樹(shù)中遞歸查找；如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值大，那就在右子樹(shù)中遞歸查找。

2. 二叉查找樹(shù)的插入操作

二叉查找樹(shù)的插入過(guò)程有點(diǎn)類似查找操作。新插入的數(shù)據(jù)一般都是在葉子節(jié)點(diǎn)上，所以我們只需要從根節(jié)點(diǎn)開(kāi)始，依次比較要插入的數(shù)據(jù)和節(jié)點(diǎn)的大小關(guān)系。

如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大，并且節(jié)點(diǎn)的右子樹(shù)為空，就將新數(shù)據(jù)直接插到右子節(jié)點(diǎn)的位置；如果不為空，就再遞歸遍歷右子樹(shù)，查找插入位置。同理，如果要插入的數(shù)據(jù)比節(jié)點(diǎn)數(shù)值小，并且節(jié)點(diǎn)的左子樹(shù)為空，就將新數(shù)據(jù)插入到左子節(jié)點(diǎn)的位置；如果不為空，就再遞歸遍歷左子樹(shù)，查找插入位置。

3. 二叉查找樹(shù)的刪除操作

針對(duì)要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)的不同，我們需要分三種情況來(lái)處理。

• 第一種情況是，如果要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，我們只需要直接將父節(jié)點(diǎn)中指向要?jiǎng)h除節(jié)點(diǎn)的指針置為 null。

• 第二種情況是，如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（只有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中，指向要?jiǎng)h除節(jié)點(diǎn)的指針，讓它指向要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)就可以了。

• 第三種情況是，如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，這就比較復(fù)雜了。我們需要找到這個(gè)節(jié)點(diǎn)的右子樹(shù)中的最小節(jié)點(diǎn)，把它替換到要?jiǎng)h除的節(jié)點(diǎn)上。然后再刪除掉這個(gè)最小節(jié)點(diǎn)，因?yàn)樽钚」?jié)點(diǎn)肯定沒(méi)有左子節(jié)點(diǎn)（如果有左子結(jié)點(diǎn)，那就不是最小節(jié)點(diǎn)了），所以，我們可以應(yīng)用上面兩條規(guī)則來(lái)刪除這個(gè)最小節(jié)點(diǎn)。

實(shí)際上，關(guān)于二叉查找樹(shù)的刪除操作，還有個(gè)非常簡(jiǎn)單、取巧的方法，就是單純將要?jiǎng)h除的節(jié)點(diǎn)標(biāo)記為“已刪除”，但是并不真正從樹(shù)中將這個(gè)節(jié)點(diǎn)去掉。這樣原本刪除的節(jié)點(diǎn)還需要存儲(chǔ)在內(nèi)存中，比較浪費(fèi)內(nèi)存空間，但是刪除操作就變得簡(jiǎn)單了很多。而且，這種處理方法也并沒(méi)有增加插入、查找操作代碼實(shí)現(xiàn)的難度。

4. 二叉查找樹(shù)的其他操作

除了插入、刪除、查找操作之外，二叉查找樹(shù)中還可以支持快速地查找最大節(jié)點(diǎn)和最小節(jié)點(diǎn)、前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。

二叉查找樹(shù)還有一個(gè)重要的特性：中序遍歷二叉查找樹(shù)，可以輸出有序的數(shù)據(jù)序列，時(shí)間復(fù)雜度是 O(n)，非常高效。因此，二叉查找樹(shù)也叫作二叉排序樹(shù)。

支持重復(fù)數(shù)據(jù)的二叉查找樹(shù)

前面講二叉查找樹(shù)的時(shí)候，我們默認(rèn)樹(shù)中節(jié)點(diǎn)存儲(chǔ)的都是數(shù)字。很多時(shí)候，在實(shí)際的軟件開(kāi)發(fā)中，我們?cè)诙娌檎覙?shù)中存儲(chǔ)的是一個(gè)包含很多字段的對(duì)象。我們利用對(duì)象的某個(gè)字段作為鍵值（key）來(lái)構(gòu)建二叉查找樹(shù)。我們把對(duì)象中的其他字段叫作衛(wèi)星數(shù)據(jù)。

前面我們講的二叉查找樹(shù)的操作，針對(duì)的都是不存在鍵值相同的情況。那如果存儲(chǔ)的兩個(gè)對(duì)象鍵值相同，這種情況該怎么處理呢？這里有兩種解決方法。

• 第一種方法比較容易。二叉查找樹(shù)中每一個(gè)節(jié)點(diǎn)不僅會(huì)存儲(chǔ)一個(gè)數(shù)據(jù)，因此我們通過(guò)鏈表和支持動(dòng)態(tài)擴(kuò)容的數(shù)組等數(shù)據(jù)結(jié)構(gòu)，把值相同的數(shù)據(jù)存儲(chǔ)在同一個(gè)節(jié)點(diǎn)上。

• 第二種方法比較不好理解，不過(guò)更加優(yōu)雅。每個(gè)節(jié)點(diǎn)仍然只存儲(chǔ)一個(gè)數(shù)據(jù)。在查找插入位置的過(guò)程中，如果碰到一個(gè)節(jié)點(diǎn)的值，與要插入數(shù)據(jù)的值相同，我們就將這個(gè)要插入的數(shù)據(jù)放到這個(gè)節(jié)點(diǎn)的右子樹(shù)，也就是說(shuō)，把這個(gè)新插入的數(shù)據(jù)當(dāng)作大于這個(gè)節(jié)點(diǎn)的值來(lái)處理。

當(dāng)要查找、刪除數(shù)據(jù)時(shí)，遇到值相同的節(jié)點(diǎn)，并不能停止查找，而是繼續(xù)在右子樹(shù)中查找，直到遇到葉子節(jié)點(diǎn)。

二叉查找樹(shù)的時(shí)間復(fù)雜度分析

當(dāng)二叉查找樹(shù)根節(jié)點(diǎn)的左右子樹(shù)極度不平衡時(shí)，就退化成了鏈表，所以查找時(shí)間復(fù)雜度就變成了 O(n)。

剛剛分析了一種最糟糕的情況，我們現(xiàn)在來(lái)分析一個(gè)最理想的情況，二叉查找樹(shù)是一棵完全二叉樹(shù)，這個(gè)時(shí)候插入、刪除、查找的時(shí)間復(fù)雜度是多少？

從前面的介紹可以看出，不管是插入、刪除還是查找，時(shí)間復(fù)雜度都跟樹(shù)的高度成正比，即 O(height)?，F(xiàn)在問(wèn)題轉(zhuǎn)化成了求一棵包含 n 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的高度。

樹(shù)的高度就等于最大層數(shù)減一，為了方便計(jì)算，我們轉(zhuǎn)換成層來(lái)表示。

包含 n 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，第一層包含 1 個(gè)節(jié)點(diǎn)，第二層包含 2 個(gè)節(jié)點(diǎn)，第三層包含 4 個(gè)節(jié)點(diǎn)，依次類推，下面一層節(jié)點(diǎn)個(gè)數(shù)是上一層的 2 倍，第 K 層包含的節(jié)點(diǎn)個(gè)數(shù)就是 2 ^ (k - 1)。

不過(guò)對(duì)于完全二叉樹(shù)來(lái)說(shuō)，最后一層的節(jié)點(diǎn)個(gè)數(shù)不遵守上面的規(guī)律，它包含的節(jié)點(diǎn)個(gè)數(shù)在 1 個(gè)到 2 ^ (L - 1) 個(gè)之間，L 是最大層數(shù)。

如果 n 是各層節(jié)點(diǎn)數(shù)之和，那么 n 滿足這樣一個(gè)關(guān)系：

n >= 1 + 2 + 4 + 8 + ... + 2 ^ (L - 2) + 1
n <= 1 + 2 + 4 + 8 + ... + 2 ^ (L - 2) + 2 ^ (L - 1)

運(yùn)用等比數(shù)列求和公式可計(jì)算出 L 的范圍是 [ ]。

完全二叉樹(shù)的層數(shù)小于等于 ，也就是說(shuō)，完全二叉樹(shù)的高度小于等于 。所以完全二叉樹(shù)查找時(shí)間復(fù)雜度為 。

顯然，極度不平衡的二叉查找樹(shù)，它的查找性能肯定不能滿足我們的需求。我們需要構(gòu)建一種不管怎么刪除、插入數(shù)據(jù)，在任何時(shí)候，都能保持任意節(jié)點(diǎn)左右子樹(shù)都比較平衡的二叉查找樹(shù)，這就是我們下一節(jié)課要詳細(xì)講的，一種特殊的二叉查找樹(shù)，平衡二叉查找樹(shù)。平衡二叉查找樹(shù)的高度接近 logn，所以插入、刪除、查找操作的時(shí)間復(fù)雜度也比較穩(wěn)定，是 O(logn)。

開(kāi)篇解答

我們?cè)谏⒘斜砟枪?jié)中講過(guò)，散列表的插入、刪除、查找操作的時(shí)間復(fù)雜度可以做到常量級(jí)的 O(1)，非常高效。而二叉查找樹(shù)在比較平衡的情況下，插入、刪除、查找操作時(shí)間復(fù)雜度才是 O(logn)，相對(duì)散列表，好像并沒(méi)有什么優(yōu)勢(shì)，那我們?yōu)槭裁催€要用二叉查找樹(shù)呢？我認(rèn)為有下面幾個(gè)原因：

第一，散列表中的數(shù)據(jù)是無(wú)序存儲(chǔ)的，如果要輸出有序的數(shù)據(jù)，需要先進(jìn)行排序。而對(duì)于二叉查找樹(shù)來(lái)說(shuō)，我們只需要中序遍歷，就可以在 O(n) 的時(shí)間復(fù)雜度內(nèi)，輸出有序的數(shù)據(jù)序列。

第二，散列表擴(kuò)容耗時(shí)很多，而且當(dāng)遇到散列沖突時(shí)，性能不穩(wěn)定，盡管二叉查找樹(shù)的性能不穩(wěn)定，但是在工程中，我們最常用的平衡二叉查找樹(shù)的性能非常穩(wěn)定，時(shí)間復(fù)雜度穩(wěn)定在 O(logn)。

第三，籠統(tǒng)地來(lái)說(shuō)，盡管散列表的查找等操作的時(shí)間復(fù)雜度是常量級(jí)的，但因?yàn)楣_突的存在，這個(gè)常量不一定比 logn 小，所以實(shí)際的查找速度可能不一定比 O(logn) 快。加上哈希函數(shù)的耗時(shí)，也不一定就比平衡二叉查找樹(shù)的效率高。

第四，散列表的構(gòu)造比二叉查找樹(shù)要復(fù)雜，需要考慮的東西很多。比如散列函數(shù)的設(shè)計(jì)、沖突解決辦法、擴(kuò)容、縮容等。平衡二叉查找樹(shù)只需要考慮平衡性這一個(gè)問(wèn)題，而且這個(gè)問(wèn)題的解決方案比較成熟、固定。

最后，為了避免過(guò)多的散列沖突，散列表裝載因子不能太大，特別是基于開(kāi)放尋址法解決沖突的散列表，會(huì)浪費(fèi)一定的存儲(chǔ)空間。

綜合這幾點(diǎn)，平衡二叉查找樹(shù)在某些方面還是優(yōu)于散列表的，所以，這兩者的存在并不沖突。我們?cè)趯?shí)際的開(kāi)發(fā)過(guò)程中，需要結(jié)合具體的需求來(lái)選擇使用哪一個(gè)。

課后思考

今天我講了二叉樹(shù)高度的理論分析方法，給出了粗略的數(shù)量級(jí)。如何通過(guò)編程，求出一棵給定二叉樹(shù)的確切高度呢？