前文介紹了符號表的兩種實現，無序鏈表和有序數組，無序鏈表在插入的時候具有較高的靈活性，而有序數組在查找時具有較高的效率，本文介紹的二叉查找樹(Binary Search Tree，BST)這一數據結構綜合了以上兩種數據結構的優點。

二叉查找樹具有很高的靈活性，對其優化可以生成平衡二叉樹，紅黑樹等高效的查找和插入數據結構，后文會一一介紹。

一定義

二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

3. 任意節點的左、右子樹也分別為二叉查找樹。

4. 沒有鍵值相等的節點（no duplicate nodes）。

如下圖，這個是普通的二叉樹：

binary tree

在此基礎上，加上節點之間的大小關系，就是二叉查找樹：

binary search tree

二實現

在實現中，我們需要定義一個內部類Node，它包含兩個分別指向左右節點的Node，一個用于排序的Key，以及該節點包含的值Value，還有一個記錄該節點及所有子節點個數的值Number。

public class BinarySearchTreeSymbolTable<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TValue>
{private Node root;private class Node{public Node Left { get; set; }public Node Right { get; set; }public int Number { get; set; }public TKey Key { get; set; }public TValue Value { get; set; }public Node(TKey key, TValue value, int number){this.Key = key;this.Value = value;this.Number = number;}}
...
}

查找

查找操作和二分查找類似，將key和節點的key比較，如果小于，那么就在Left Node節點查找,如果大于，則在Right Node節點查找，如果相等，直接返回Value。

? SearchhitAndSearchMissinBST

該方法實現有迭代和遞歸兩種。

遞歸的方式實現如下：

public override TValue Get(TKey key)
{TValue result = default(TValue);Node node = root;while (node != null){if (key.CompareTo(node.Key) > 0){node = node.Right;}else if (key.CompareTo(node.Key) < 0){node = node.Left;}else{result = node.Value;break;}}return result;
}

迭代的如下：

public TValue Get(TKey key)
{return GetValue(root, key);
}private TValue GetValue(Node root, TKey key)
{if (root == null) return default(TValue);int cmp = key.CompareTo(root.Key);if (cmp > 0) return GetValue(root.Right, key);else if (cmp < 0) return GetValue(root.Left, key);else return root.Value;
}

插入

插入和查找類似，首先查找有沒有和key相同的，如果有，更新；如果沒有找到，那么創建新的節點。并更新每個節點的Number值，代碼實現如下：

public override void Put(TKey key, TValue value)
{root = Put(root, key, value);
}private Node Put(Node x, TKey key, TValue value)
{//如果節點為空，則創建新的節點，并返回//否則比較根據大小判斷是左節點還是右節點，然后繼續查找左子樹還是右子樹//同時更新節點的Number的值if (x == null) return new Node(key, value, 1);int cmp = key.CompareTo(x.Key);if (cmp < 0) x.Left = Put(x.Left, key, value);else if (cmp > 0) x.Right = Put(x.Right, key, value);else x.Value = value;x.Number = Size(x.Left) + Size(x.Right) + 1;return x;
}private int Size(Node node)
{if (node == null) return 0;else return node.Number;
}

? 插入操作圖示如下：

insert into BST

下面是插入動畫效果：

insert into BST

隨機插入形成樹的動畫如下，可以看到，插入的時候樹還是能夠保持近似平衡狀態：

Insert keys random order in BST

最大最小值

如下圖可以看出，二叉查找樹的最大最小值是有規律的：

the max and min item in bst

從圖中可以看出，二叉查找樹中，最左和最右節點即為最小值和最大值，所以我們只需迭代調用即可。

public override TKey GetMax()
{TKey maxItem = default(TKey);Node s = root;while (s.Right != null){s = s.Right;}maxItem = s.Key;return maxItem;
}public override TKey GetMin()
{TKey minItem = default(TKey);Node s = root;while (s.Left != null){s = s.Left;}minItem = s.Key;return minItem;
}

以下是遞歸的版本：

public TKey GetMaxRecursive()
{return GetMaxRecursive(root);
}private TKey GetMaxRecursive(Node root)
{if (root.Right == null) return root.Key;return GetMaxRecursive(root.Right);
}public TKey GetMinRecursive()
{return GetMinRecursive(root);
}private TKey GetMinRecursive(Node root)
{if (root.Left == null) return root.Key;return GetMinRecursive(root.Left);
}

Floor和Ceiling

查找Floor(key)的值就是所有<=key的最大值，相反查找Ceiling的值就是所有>=key的最小值，下圖是Floor函數的查找示意圖：

floor function in BST

以查找Floor為例，我們首先將key和root元素比較，如果key比root的key小，則floor值一定在左子樹上；如果比root的key大，則有可能在右子樹上，當且僅當其右子樹有一個節點的key值要小于等于該key；如果和root的key相等，則floor值就是key。根據以上分析，Floor方法的代碼如下，Ceiling方法的代碼類似，只需要把符號換一下即可：

public TKey Floor(TKey key)
{Node x = Floor(root, key);if (x != null) return x.Key;else return default(TKey);
}private Node Floor(Node x, TKey key)
{if (x == null) return null;int cmp = key.CompareTo(x.Key);if (cmp == 0) return x;if (cmp < 0) return Floor(x.Left, key);else{Node right = Floor(x.Right, key);if (right == null) return x;else return right;}
}

刪除

刪除元素操作在二叉樹的操作中應該是比較復雜的。首先來看下比較簡單的刪除最大最小值得方法。

以刪除最小值為例，我們首先找到最小值，及最左邊左子樹為空的節點，然后返回其右子樹作為新的左子樹。操作示意圖如下：

delete minimun in BST

代碼實現如下：

public void DelMin()
{root = DelMin(root);
}private Node DelMin(Node root)
{if (root.Left == null) return root.Right;root.Left = DelMin(root.Left);root.Number = Size(root.Left) + Size(root.Right) + 1;return root;
}

刪除最大值也是類似。

現在來分析一般情況，假定我們要刪除指定key的某一個節點。這個問題的難點在于：刪除最大最小值的操作，刪除的節點只有1個子節點或者沒有子節點，這樣比較簡單。但是如果刪除任意節點，就有可能出現刪除的節點有0個，1 個，2個子節點的情況，現在來逐一分析。

當刪除的節點沒有子節點時，直接將該父節點指向該節點的link設置為null。

? delete node which has 0 childrens

當刪除的節點只有1個子節點時，將該自己點替換為要刪除的節點即可。

delete node which has 1 childrens

當刪除的節點有2個子節點時，問題就變復雜了。

假設我們刪除的節點t具有兩個子節點。因為t具有右子節點，所以我們需要找到其右子節點中的最小節點，替換t節點的位置。這里有四個步驟：

1. 保存帶刪除的節點到臨時變量t

2. 將t的右節點的最小節點min(t.right)保存到臨時節點x

3. 將x的右節點設置為deleteMin(t.right)，該右節點是刪除后，所有比x.key最大的節點。

4. 將x的做節點設置為t的左節點。

整個過程如下圖：

delete node which has 2 childrens

對應代碼如下：

public void Delete(TKey key)
{root =Delete(root, key);}private Node Delete(Node x, TKey key)
{int cmp = key.CompareTo(x.Key);if (cmp > 0) x.Right = Delete(x.Right, key);else if (cmp < 0) x.Left = Delete(x.Left, key);else{if (x.Left == null) return x.Right;else if (x.Right == null) return x.Left;else{Node t = x;x = GetMinNode(t.Right);x.Right = DelMin(t.Right);x.Left = t.Left;}}x.Number = Size(x.Left) + Size(x.Right) + 1;return x;
}private Node GetMinNode(Node x)
{if (x.Left == null) return x;else return GetMinNode(x.Left); 
}