1 概述

二叉搜索樹，顧名思義，其主要目的用于搜索，它是二叉樹結(jié)構(gòu)中最基本的一種數(shù)據(jù)結(jié)構(gòu)，是后續(xù)理解B樹、B⁺樹、紅黑樹的基礎(chǔ)，后三者在具體的工程實(shí)踐中更常用，比如C++中STL就是利用紅黑樹做Map，B樹用于磁盤上的數(shù)據(jù)庫維護(hù)等，后三者均是在二叉搜索樹的基礎(chǔ)上演變而來的，理解二叉搜索樹是學(xué)習(xí)后者的基礎(chǔ)。

與基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)如鏈表、堆、棧等基本結(jié)構(gòu)一樣，學(xué)習(xí)二叉搜索樹的關(guān)鍵是深入理解訪問與操作二叉樹的算法及性能分析，本文如下部分首先介紹二叉搜索樹的特征；然后重點(diǎn)介紹二叉搜索樹的遍歷、查找（包括最值查找、前驅(qū)后繼查找）、以及插入和刪除等操作，最后簡(jiǎn)單進(jìn)行分析。

本文涉及的算法已用golang完成一個(gè)初步版本，請(qǐng)?jiān)L問我的github，歡迎大家使用測(cè)試，希望各位批評(píng)指正！

2 二叉搜索樹的定義及操作

二叉樹很簡(jiǎn)單，表示每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，二叉搜索樹則更作了更近一步的要求，其必須滿足如下性質(zhì)：

設(shè)x為二叉搜索樹中的一個(gè)節(jié)點(diǎn)，如果y是x左子樹的一個(gè)節(jié)點(diǎn)（注：不是直接子節(jié)點(diǎn)，是左子樹的所有節(jié)點(diǎn)），則y.key <= x.key；如果y是x右子樹的一個(gè)節(jié)點(diǎn)，則y.key >= x.key
分析：二叉樹本身具有固定的結(jié)構(gòu)，上述規(guī)定對(duì)二叉樹中節(jié)點(diǎn)之間的關(guān)系進(jìn)行限制，即賦予了二叉樹特定的語義，只要滿足二叉樹的這種語義，就可以直接根據(jù)二叉樹結(jié)構(gòu)特征更高效地進(jìn)行查詢搜索等操作

如下圖1所示：

圖1: 二叉搜索樹例子

2.1 二叉搜索樹的遍歷

樹的遍歷有三種：先序遍歷、中序遍歷、后序遍歷。

• 先序遍歷：先訪問當(dāng)前節(jié)點(diǎn)x，再訪問x的左子樹x.left，最后訪問x的右子樹x.right
• 中序遍歷：先訪問當(dāng)前節(jié)點(diǎn)x的左子樹x.left, 再訪問當(dāng)前節(jié)點(diǎn)x, 最后訪問x的右子樹x.right
• 后序遍歷：先訪問當(dāng)前節(jié)點(diǎn)x的左子樹x.left, 再訪問當(dāng)前節(jié)點(diǎn)的右子樹x.right, 最后訪問x

中序遍歷的遞歸算法如下：

圖2:中序遍歷算法(摘自算法導(dǎo)論)

遍歷二叉搜索樹其實(shí)就是遍歷二叉樹，因?yàn)楦揪蜎]有用到二叉搜索樹的特性。不過，根據(jù)二叉搜索樹的特性，中序遍歷得到的就是從小到大排序的結(jié)果。如果用遞歸算法完成遍歷，其時(shí)間復(fù)雜度為:(簡(jiǎn)書也不支持latex，真是蛋疼的寫法)

分析：假設(shè)遍歷二叉搜索樹時(shí)間為T(n)，遞歸遍歷無非就是每個(gè)節(jié)點(diǎn)訪問一次，因此T(n) >= kn，這里k是訪問每個(gè)節(jié)點(diǎn)的時(shí)間常數(shù)，n為二叉搜索樹節(jié)點(diǎn)數(shù)；遞歸需要入棧出棧，其時(shí)間為一個(gè)常數(shù)設(shè)為d，二叉搜索樹最多有n顆子樹，因此，kn <= T(n) <= kn + dn = (k+d)n，證明完畢。

2.2 二叉搜索樹的查詢

對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，搜索其中某個(gè)節(jié)點(diǎn)x的算法的時(shí)間復(fù)雜度為O(n)，因?yàn)槭莕個(gè)無序節(jié)點(diǎn)...。而對(duì)于二叉搜索樹BST，根據(jù)它的特性，其本質(zhì)是一顆已排好序的節(jié)點(diǎn)序列，若要查找的節(jié)點(diǎn)元素z, 則從BST的根節(jié)點(diǎn)root開始查找，其算法為：
Search(root, z){ if root != nil { if root.key == z.key return root elif root.key > z.key Search(root.left, z) else Search(root.right, z) } return nil }
算法的時(shí)間復(fù)雜度為O(h)，h為二叉搜索樹的高度。分析：搜索時(shí)間取決于算法中比較的次數(shù)，而比較的次數(shù)由二叉搜索樹的高度決定。（近一步分析，如果二叉搜索樹的各子樹極度不平衡，最壞情況是退化為一個(gè)鏈表或向量，則Search的時(shí)間復(fù)雜度為O(n)；如果二叉搜索樹的各子樹極度平衡，則其高度為h = O(logn)，h值此時(shí)最小，這就涉及到本文開頭提到的其它樹結(jié)構(gòu)了）

與一般二叉樹不同，二叉搜索樹因?yàn)楸旧硪呀?jīng)是有序的，所以，它還提供了查找最大值、查找最小值、查找某個(gè)元素x的前驅(qū)和查找某個(gè)元素x的后繼等，這里x的前驅(qū)表示二叉搜索樹中剛好比x小的數(shù)z，即在(x, z)范圍內(nèi)的其它數(shù)據(jù)不在二叉搜索樹中，后繼的意思與此類似。

觀察圖1中的例子，可以發(fā)現(xiàn)：

規(guī)律1（最小值）：樹T（假設(shè)其根節(jié)點(diǎn)為t），如果T沒有左子樹，則t為子樹T的最小值節(jié)點(diǎn)；如果有左子樹L，則L的最小值節(jié)點(diǎn)為T的最小值節(jié)點(diǎn)。其算法如下所示：
Min(t){ if t == nil return nil; if t.left == nil return t; return Min(t.left) }
Min函數(shù)的時(shí)間復(fù)雜度為O(h)，h為二叉搜索樹的高度。

規(guī)律2（最大值）: 樹T（假設(shè)其根節(jié)點(diǎn)為t），如果T沒有右子樹，則t為子樹T的最大值節(jié)點(diǎn)；如果有右子樹R，則R的最大值節(jié)點(diǎn)為T的最大值節(jié)點(diǎn)。其算法為：
Max(t){ if t == nil return nil; if t.right == nil return t; return Max(t.right) }
Max函數(shù)的時(shí)間復(fù)雜度為O(h)

規(guī)律3（前驅(qū)）：樹T中查找節(jié)點(diǎn)x的前驅(qū)，如果x是T的最左子節(jié)點(diǎn)，則沒有前驅(qū)，如圖1左的值為2的節(jié)點(diǎn)；如果x有左子樹L，則L的最大值為x的前驅(qū)（利用規(guī)律2求）；如果x沒有左子樹，這個(gè)情況稍顯復(fù)雜，假設(shè)x的父節(jié)點(diǎn)為p，若x為p的右子樹，則p為x的前驅(qū)，如圖1中右圖中值為8的節(jié)點(diǎn)，其前驅(qū)為7的節(jié)點(diǎn), 若x為p的左子樹（即p節(jié)點(diǎn)的值比x的大），則繼續(xù)按照x與p的邏輯向上尋找p的父節(jié)點(diǎn)p'，直到p為p'的右節(jié)點(diǎn)，則p'為x的前驅(qū)，如圖3右圖最下面的值為5的節(jié)點(diǎn)的前驅(qū)為值為3的節(jié)點(diǎn)。

圖3: 二叉搜索樹示例

其算法為：
Predecessor(t, x){ if Min(t) is x or x is nil return nil; if x.left return Max(x.left); p = x.parent; while p.right != x { x = p; p = p.parent } return p }
Predecessor算法的時(shí)間復(fù)雜度取決于Max的復(fù)雜度或while循環(huán)次數(shù)，而二者都取決于二叉搜索樹的高度，所以Predecessor的時(shí)間復(fù)雜度為O(h)。

規(guī)律4（后繼）：樹T中查找節(jié)點(diǎn)x的后繼，若x為其最有最右子節(jié)點(diǎn)，則x沒有后繼；如果x有右子樹R，則R的最小值為x的后繼（利用規(guī)律1求）；如果x沒有右子樹，假設(shè)x的父節(jié)點(diǎn)為p，若x為p的左子樹根節(jié)點(diǎn)，則p為x的后繼，如圖3中值為6的節(jié)點(diǎn)的后繼為值為7的節(jié)點(diǎn)，若x為p的右子樹根節(jié)點(diǎn)，按照x與p的邏輯向上尋找p的父節(jié)點(diǎn)p'，直到p為p'的左節(jié)點(diǎn)，則p'為x的后繼，如圖4中值為9的節(jié)點(diǎn)的后繼為值是10的節(jié)點(diǎn)。

圖4: 示例

其算法為：
Successor(t, x){ if Max(t) is x or x is nil return nil; if x.right return Min(x.right); p = x.parent; while p.left != x { x = p; p = p.parent; } return p }
與Predecessor類似，其算法復(fù)雜度為O(h)

2.3 節(jié)點(diǎn)插入與刪除

如果采用二叉搜索樹存儲(chǔ)數(shù)據(jù)，增加和刪除數(shù)據(jù)不可避免。與一般的二叉樹的插入和刪除不同，需要保證二叉搜索樹的特性不變。

2.3.1 節(jié)點(diǎn)插入

向二叉樹中插入節(jié)點(diǎn)，首先面臨的一個(gè)問題是，這個(gè)節(jié)點(diǎn)應(yīng)該放在哪里？是作為葉子節(jié)點(diǎn)還是作為非葉子節(jié)點(diǎn)插入？顯然，插入節(jié)點(diǎn)作為葉子節(jié)點(diǎn)是較為直接和簡(jiǎn)單的方式，問題是：是否對(duì)于任何值的節(jié)點(diǎn)都可以作為葉子節(jié)點(diǎn)插入？？？答案是肯定的，如果有興趣可以證明（證明也比較直接），如果有懷疑，可以嘗試在下圖5中插入任何數(shù)值的節(jié)點(diǎn)，驗(yàn)證其二叉搜索樹的特性是否成立。

圖5：節(jié)點(diǎn)插入圖示

插入節(jié)點(diǎn)的算法為：
Insert(t, x){ while t { // while循環(huán)中查找合適的葉節(jié)點(diǎn)位置 y = t; if x.key < t.key t = t.left; else t = t.right; } x.parent = y if y == nil t = x; elif x.key < y.key y.left = x; else y.right = x; }
while循環(huán)的復(fù)雜度決定Insert操作的復(fù)雜度，其中的比較次數(shù)（即二叉搜索樹的高度）決定了Insert的復(fù)雜度，因此其復(fù)雜度為O(h)

2.3.2 刪除節(jié)點(diǎn)

與插入節(jié)點(diǎn)相比，刪除節(jié)點(diǎn)會(huì)更復(fù)雜。刪除節(jié)點(diǎn)有兩種情況：

• 刪除葉節(jié)點(diǎn)，這種情況較為簡(jiǎn)單，直接刪除不會(huì)改變二叉搜索樹的特征；
• 刪除非葉子節(jié)點(diǎn)x。這種情況稍微復(fù)雜，又可分為如下幾種情況：

  • 如果x的左子樹或右子樹為空，則直接用左子樹或右子樹代替x即可，如圖6中的a和b

    
    
    圖6：示例
  • 如果x的左子樹L和右子樹均R存在，則存在兩種刪除的思路，一種是在左子樹L中尋找最大值節(jié)點(diǎn)LMax（LMax比為葉子節(jié)點(diǎn)），刪除LMax并用LMax代替x即可；另一種思路則是在右子樹R中尋找最小值節(jié)點(diǎn)RMin（RMin必為葉子節(jié)點(diǎn)），刪除RMin并用RMin代替x即可。

因此，刪除節(jié)點(diǎn)的算法為：
Delete(t, x){ if t == nil return nil; if x.left == nil and x.right == nil{ // 葉子節(jié)點(diǎn)的情況 if x == t return nil; } elif x.left != nil and x.right == nil{ // 左子樹非空的情況 p = x.parent; if x is p.left p.left = x.left; else p.right = x.left; x.left.parent = p; } elif x.right != nil and x.left == nil{ // 右子樹非空的情況 p = x.parent; if x is p.left p.left = x.right; else p.right = x.right; x.right.parent = p; } else{ //左右子樹均為非空的情況 LMax = Max(x.left); // * copy = copyAndSetNode(LMax); // 深度復(fù)制一個(gè)LMax并對(duì)其左右子節(jié)點(diǎn)和父節(jié)點(diǎn)均賦值為nil t = Delete(t, LMax); p = x.parent; copy.left = x.left; copy.right = x.right; copy.parent = p; if x is p.left p.left = copy; else p.right = copy; } x = nil; return t; }
對(duì)于Delete函數(shù)，其復(fù)雜度由左右子樹均為非空情況中的行*決定，其復(fù)雜度為O(h).

3 小結(jié)

由上面的分析知：二叉搜索樹的查詢、插入、刪除操作的時(shí)間復(fù)雜度均為O(h)。表面上看，比較理想，但是，h的值由二叉搜索樹的形態(tài)決定，而二叉搜索樹的形態(tài)是不確定的，如{1, 3, 5, 7, 9, 11, 13}可以構(gòu)建出高度為2、3、4、5、6的二叉搜索樹，這種不確定性是由于二叉搜索樹限定的特征較為寬松造成的。在二叉搜索樹上加上其它限定特征，即可構(gòu)成B樹、B⁺樹、紅黑樹等。