二叉查找樹 - gaochundong－IT工程師數位筆記本

文章出處

在文章《常用數據結構及復雜度》中，介紹了一些計算機程序設計中常用的線性數據結構，包括 Array、ArrayList、LinkedList<T>、List<T>、Stack<T>、Queue<T>、Hashtable 和 Dictionary<T> 等。并簡單介紹了這些數據結構的內部實現原理和常用操作的運算復雜度，以及如何選擇合適的數據結構。本篇文章中，我們將介紹常見的樹形結構及其常用操作的運算復雜度。

二叉樹（Binary Tree）
- 完全二叉樹和滿二叉樹
二叉查找樹（Binary Search Tree）

我們知道像家譜族譜、公司組織結構等都是以樹結構的形式組織數據。例如下圖中所展示的公司組織結構圖。

樹（Tree）是由多個節點（Node）的集合組成，每個節點又有多個與其關聯的子節點（Child Node）。子節點就是直接處于節點之下的節點，而父節點（Parent Node）則位于節點直接關聯的上方。樹的根（Root）指的是一個沒有父節點的單獨的節點。

所有的樹都呈現了一些共有的性質：

只有一個根節點；
除了根節點，所有節點都有且只有一個父節點；
無環。將任意一個節點作為起始節點，都不存在任何回到該起始節點的路徑。（正是前兩個性質保證了無環的成立。）

樹中使用的術語

根（Root）：樹中最頂端的節點，根沒有父節點。
子節點（Child）：節點所擁有子樹的根節點稱為該節點的子節點。
父節點（Parent）：如果節點擁有子節點，則該節點為子節點的父節點。
兄弟節點（Sibling）：與節點擁有相同父節點的節點。
子孫節點（Descendant）：節點向下路徑上可達的節點。
葉節點（Leaf）：沒有子節點的節點。
內節點（Internal Node）：至少有一個子節點的節點。
度（Degree）：節點擁有子樹的數量。
邊（Edge）：兩個節點中間的鏈接。
路徑（Path）：從節點到子孫節點過程中的邊和節點所組成的序列。
層級（Level）：根為 Level 0 層，根的子節點為 Level 1 層，以此類推。
高度（Height）/深度（Depth）：樹中層的數量。比如只有 Level 0,Level 1,Level 2 則高度為 3。

類別

樹名稱

二叉查找樹

（Binary Search Tree）

二叉查找樹，笛卡爾樹，T 樹

自平衡二叉查找樹

（Self-balancing Binary Search Tree）

AA 樹，AVL 樹，

紅黑樹（Red-Black Tree），

伸展樹（Splay Tree）

B 樹

（B-Tree）

2-3 樹，2-3-4 樹，

B 樹，B+ 樹，B* 樹

字典樹

（Trie-Tree）

后綴樹，基數樹，三叉查找樹，快速前綴樹

空間數據分割樹

（Spatial Data Partitioning Tree）

R 樹，R+ 樹，R* 樹，

線段樹，優先 R 樹

二叉樹（Binary Tree）

二叉樹（Binary Tree）是一種特殊的樹類型，其每個節點最多只能有兩個子節點。這兩個子節點分別稱為當前節點的左孩子（left child）和右孩子（right child）。

上圖中，二叉樹（a）包含 8 個節點，其中節點 1 是它的根節點。節點 1 的左孩子為節點 2，右孩子為節點 3。注意，并沒有要求一個節點同時具有左孩子和右孩子。例如，二叉樹（a）中，節點 4 就只有一個右孩子 6。此外，節點也可以沒有孩子節點。例如，二叉樹（b）中，節點 4、5、6、7 都沒有孩子節點。

沒有孩子的節點稱為葉節點（Leaf Node），有孩子的節點則稱為內節點（Internal Node）。如上圖中，二叉樹（a）中節點 6、8 為葉節點，節點 1、2、3、4、5、7 為內節點。

完全二叉樹和滿二叉樹

完全二叉樹（Complete Binary Tree）：深度為 h，有 n 個節點的二叉樹，當且僅當其每一個節點都與深度為 h 的滿二叉樹中，序號為 1 至 n 的節點對應時，稱之為完全二叉樹。

滿二叉樹（Full Binary Tree）：一棵深度為 h，且有 2^h - 1 個節點稱之為滿二叉樹。

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

A full binary tree is a tree in which every node other than the leaves has two children.

	完全二叉樹	滿二叉樹
總節點數 k	2^h-1 <= k < 2^h - 1	k = 2^h - 1
樹高 h	h = log₂k + 1	h = log₂(k + 1)

.NET 中并沒有直接提供二叉樹的實現，我們需要自己來實現 BinaryTree 類。在《你曾實現過二叉樹嗎》一文中，實現了一個基于泛型的簡單的二叉樹模型。

我們已經了解了數組是將元素連續地排列在內存當中，而二叉樹卻不是采用連續的內存存放。實際上，通常 BinaryTree 類的實例僅包含根節點（Root Node）實例的引用，而根節點實例又分別指向它的左右孩子節點實例，以此類推。所以關鍵的不同之處在于，組成二叉樹的節點對象實例可以分散到 CLR 托管堆中的任何位置，它們沒有必要像數組元素那樣連續的存放。

如果要訪問二叉樹中的某一個節點，通常需要逐個遍歷二叉樹中的節點，來定位那個節點。它不象數組那樣能對指定的節點進行直接的訪問。所以查找二叉樹的漸進時間是線性的 O(n)，在最壞的情況下需要查找樹中所有的節點。也就是說，隨著二叉樹節點數量增加時，查找任一節點的步驟數量也將相應地增加。

那么，如果一個二叉樹的查找時間是線性的，定位時間也是線性的，那相比數組來說到底哪里有優勢呢？畢竟數組的查找時間雖然是線性 O(n)，但定位時間卻是常量 O(1) 啊？的確是這樣，通常來說普通的二叉樹確實不能提供比數組更好的性能。然而，如果我們按照一定的規則來組織排列二叉樹中的元素時，就可以很大程度地改善查詢時間和定位時間。

二叉查找樹（Binary Search Tree）

二叉查找樹（BST：Binary Search Tree）是一種特殊的二叉樹，它改善了二叉樹節點查找的效率。二叉查找樹有以下性質：

對于任意一個節點 n，

其左子樹（left subtree）下的每個后代節點（descendant node）的值都小于節點 n 的值；
其右子樹（right subtree）下的每個后代節點的值都大于節點 n 的值。

所謂節點 n 的子樹，可以將其看作是以節點 n 為根節點的樹。子樹的所有節點都是節點 n 的后代，而子樹的根則是節點 n 本身。

下圖中展示了兩個二叉樹。二叉樹（b）是一個二叉查找樹（BST），它符合二叉查找樹的性質規定。而二叉樹（a），則不是二叉查找樹。因為節點 10 的右孩子節點 8 小于節點 10，但卻出現在節點 10 的右子樹中。同樣，節點 8 的右孩子節點 4 小于節點 8，但出現在了它的右子樹中。無論是在哪個位置，只要不符合二叉查找樹的性質規定，就不是二叉查找樹。例如，節點 9 的左子樹只能包含值小于節點 9 的節點，也就是 8 和 4。

從二叉查找樹的性質可知，BST 各節點存儲的數據必須能夠與其他的節點進行比較。給定任意兩個節點，BST 必須能夠判斷這兩個節點的值是小于、大于還是等于。

假設我們要查找 BST 中的某一個節點。例如在上圖中的二叉查找樹（b）中，我們要查找值為 10 的節點。

我們從根開始查找。可以看到，根節點的值為 7，小于我們要查找的節點值 10。因此，如果節點 10 存在，必然存在于其右子樹中，所以應該跳到節點 11 繼續查找。此時，節點值 10 小于節點 11 的值，則節點 10 必然存在于節點 11 的左子樹中。在查找節點 11 的左孩子，此時我們已經找到了目標節點 10，定位于此。

如果我們要查找的節點在樹中不存在呢？例如，我們要查找節點 9。重復上述操作，直到到達節點 10，它大于節點 9，那么如果節點 9 存在，必然存在于節點 10 的左子樹中。然而我們看到節點 10 根本就沒有左孩子，因此節點 9 在樹中不存在。

總結來說，我們使用的查找算法過程如下：

假設我們要查找節點 n，從 BST 的根節點開始。算法不斷地比較節點值的大小直到找到該節點，或者判定不存在。每一步我們都要處理兩個節點：樹中的一個節點，稱為節點 c，和要查找的節點 n，然后并比較 c 和 n 的值。開始時，節點 c 為 BST 的根節點。然后執行以下步驟：

如果 c 值為空，則 n 不在 BST 中；
比較 c 和 n 的值；
如果值相同，則找到了指定節點 n；
如果 n 的值小于 c，那么如果 n 存在，必然在 c 的左子樹中。回到第 1 步，將 c 的左孩子作為 c；
如果 n 的值大于 c，那么如果 n 存在，必然在 c 的右子樹中。回到第 1 步，將 c 的右孩子作為 c；

通過 BST 查找節點，理想情況下我們需要檢查的節點數可以減半。如下圖中的 BST 樹，包含了 15 個節點。從根節點開始執行查找算法，第一次比較決定我們是移向左子樹還是右子樹。對于任意一種情況，一旦執行這一步，我們需要訪問的節點數就減少了一半，從 15 降到了 7。同樣，下一步訪問的節點也減少了一半，從 7 降到了 3，以此類推。

根據這一特點，查找算法的時間復雜度應該是 O(log₂n)，簡寫為 O(lg n)。我們在文章《算法復雜度分析》中有一些關于時間復雜度的描述。可知，log₂n = y，相當于 2^y = n。即，如果節點數量增加 n，查找時間只緩慢地增加到 log₂n。下圖中顯示了 O(log₂n) 和線性增長 O(n) 的增長率之間的區別。時間復雜度為 O(log₂n) 的算法運行時間為下面那條線。

從上圖可以看出，O(log₂n) 曲線幾乎是水平的，隨著 n 值的增加，曲線增長十分緩慢。舉例來說，查找一個具有 1000 個元素的數組，需要查詢 1000 個元素，而查找一個具有 1000 個元素的 BST 樹，僅需查詢不到10 個節點（log₂1024 = 10）。

而實際上，對于 BST 查找算法來說，其十分依賴于樹中節點的拓撲結構，也就是節點間的布局關系。下圖描繪了一個節點插入順序為 20, 50, 90, 150, 175, 200 的 BST 樹。這些節點是按照遞升順序被插入的，結果就是這棵樹沒有廣度（Breadth）可言。也就是說，它的拓撲結構其實就是將節點排布在一條線上，而不是以扇形結構散開，所以查找時間也為 O(n)。

當 BST 樹中的節點以扇形結構散開時，對它的插入、刪除和查找操作最優的情況下可以達到亞線性的運行時間 O(log₂n)。因為當在 BST 中查找一個節點時，每一步比較操作后都會將節點的數量減少一半。盡管如此，如果拓撲結構像上圖中的樣子時，運行時間就會退減到線性時間 O(n)。因為每一步比較操作后還是需要逐個比較其余的節點。也就是說，在這種情況下，在 BST 中查找節點與在數組（Array）中查找就基本類似了。

因此，BST 算法查找時間依賴于樹的拓撲結構。最佳情況是 O(log₂n)，而最壞情況是 O(n)。

插入節點

我們不僅需要了解如何在二叉查找樹中查找一個節點，還需要知道如何在二叉查找樹中插入和刪除一個節點。

當向樹中插入一個新的節點時，該節點將總是作為葉子節點。所以，最困難的地方就是如何找到該節點的父節點。類似于查找算法中的描述，我們將這個新的節點稱為節點 n，而遍歷的當前節點稱為節點 c。開始時，節點 c 為 BST 的根節點。則定位節點 n 父節點的步驟如下：

如果節點 c 為空，則節點 c 的父節點將作為節點 n 的父節點。如果節點 n 的值小于該父節點的值，則節點 n 將作為該父節點的左孩子；否則節點 n 將作為該父節點的右孩子。
比較節點 c 與節點 n 的值。
如果節點 c 的值與節點 n 的值相等，則說明用戶在試圖插入一個重復的節點。解決辦法可以是直接丟棄節點 n，或者可以拋出異常。
如果節點 n 的值小于節點 c 的值，則說明節點 n 一定是在節點 c 的左子樹中。則將父節點設置為節點 c，并將節點 c 設置為節點 c 的左孩子，然后返回至第 1 步。
如果節點 n 的值大于節點 c 的值，則說明節點 n 一定是在節點 c 的右子樹中。則將父節點設置為節點 c，并將節點 c 設置為節點 c 的右孩子，然后返回至第 1 步。

當合適的節點找到時，該算法結束。從而使新節點被放入 BST 中成為某一父節點合適的孩子節點。

BST 的插入算法的復雜度與查找算法的復雜度是一樣的：最佳情況是 O(log₂n)，而最壞情況是 O(n)。因為它們對節點的查找定位策略是相同的。

刪除節點

從 BST 中刪除節點比插入節點難度更大。因為刪除一個非葉子節點，就必須選擇其他節點來填補因刪除節點所造成的樹的斷裂。如果不選擇節點來填補這個斷裂，那么就違背了 BST 的性質要求。

刪除節點算法的第一步是定位要被刪除的節點，這可以使用前面介紹的查找算法，因此運行時間為 O(log₂n)。接著應該選擇合適的節點來代替刪除節點的位置，它共有三種情況需要考慮。

情況 1：如果刪除的節點沒有右孩子，那么就選擇它的左孩子來代替原來的節點。二叉查找樹的性質保證了被刪除節點的左子樹必然符合二叉查找樹的性質。因此左子樹的值要么都大于，要么都小于被刪除節點的父節點的值，這取決于被刪除節點是左孩子還是右孩子。因此用被刪除節點的左子樹來替代被刪除節點，是完全符合二叉搜索樹的性質的。
情況 2：如果被刪除節點的右孩子沒有左孩子，那么這個右孩子被用來替換被刪除節點。因為被刪除節點的右孩子都大于被刪除節點左子樹的所有節點，同時也大于或小于被刪除節點的父節點，這同樣取決于被刪除節點是左孩子還是右孩子。因此，用右孩子來替換被刪除節點，符合二叉查找樹的性質。
情況 3：如果被刪除節點的右孩子有左孩子，就需要用被刪除節點右孩子的左子樹中的最下面的節點來替換它，就是說，我們用被刪除節點的右子樹中最小值的節點來替換。

我們知道，在 BST 中，最小值的節點總是在最左邊，最大值的節點總是在最右邊。因此替換被刪除節點右子樹中最小的一個節點，就保證了該節點一定大于被刪除節點左子樹的所有節點。同時，也保證它替代了被刪除節點的位置后，它的右子樹的所有節點值都大于它。因此這種選擇策略符合二叉查找樹的性質。