二叉搜尋樹，也叫二叉排序樹、二叉查找樹或BST(Binary Search Tree)。二叉搜尋樹或是一棵空疏，或者是一棵具有下列特性的非空二叉樹：
1. 若左子樹非空，則左子樹上的所有節點的關鍵字值均小于根節點的關鍵字的值。
2. 若右子樹非空，則右子樹上的所有節點的關鍵字值均大于根節點的關鍵字的值。
3. 左右子樹，本身也是一棵二叉搜尋樹。
根據二叉搜尋樹定義，有左子樹節點值<根節點值<右子節點值，是以搜尋樹節點值，是以，對二叉搜尋樹進行中序周遊，可以得到一個遞增的有序序列。
查找：
如果樹為空，則查找失敗
如果值大于根節點關鍵字的值，遞歸查找右子樹
如果值小于根節點關鍵字的值，遞歸查找左子樹
如果根節點關鍵字的值等于查找的關鍵字，成功。
平均查找複雜度O(lgN)
1 template<typename T>
2 bool BinarySearchTree<T>::ContainsRecu(BinaryTreeNode* root, const T& val) const {
3 if (root == NULL) {
4 return false;
5 } else if (val > root->data) {
6 return Contains(root->right, val);
7 } else if (val < root->data) {
8 return Contains(root->left, val);
9 } else {
10 return true;
11 }
12 } 最小值：
從根節點開始一直往左走，直到無路可走。
時間複雜度O(lgN)
1 template <typename T>
2 BinarySearchTree::BinaryTreeNode* BinarySearchTree<T>::FindMin(BinaryTreeNode* &p) const {
3 while (p != NULL && p->left != NULL) {
4 p = p->left;
5 }
6
7 return p;
8 } 尋找最大值：
從根節點一直往右走，直到無路可走。
1 template <typename T>
2 BinarySearchTree::BinaryTreeNode* BinarySearchTree<T>::FindMin(BinaryTreeNode* &p) const {
3 while (p != NULL && p->left != NULL) {
4 p = p->left;
5 }
6
7 return p;
8 } 插入：
插入新元素時，可從根節點開始，與鍵值較大者就向左，遇鍵值較小者就向右，一直到尾端，即為插入點。
注意：新插入的節點總是葉子節點，如果樹種有相同的節點，則不做任何操作。
時間複雜度O（lgN)
1 template<typename T>
2 void BinarySearchTree<T>::Insert(BinaryTreeNode* &p, const T& val) {
3 if (p == NULL) {
4 p = new BinaryTreeNode(val);
5 } else if (val > p->data) {
6 Insert(p->right, val);
7 } else if (val < p->data) {
8 Insert(p->left, val);
9 } else
10 ; //重複，不做任何操作
11 } 删除：
1. 如果節點是一片樹葉，那麼它可以被立即删除。
2. 如果節點有一個兒子，則該節點可以再其父節點調整它的鍊繞過該節點後被删除。
3. 如果節點有兩個兒子的節點，一般的删除政策是用其右子樹的資料代替該節點的資料并遞歸地的删除那個節點。
1 template<typename T>
2 void BinarySearchTree<T>::Remove(BinaryTreeNode* &p, const T& val) {
3 if (p == NULL) {
4 return; //沒有此值
5 } else if (val > p->data) {
6 Remove(p->right, val);
7 } else if (val < p->data) {
8 Remove(p->left, val);
9 } else if (p->left != NULL && p->right != NULL) {
10 p->data = FindMin(p->right)->data;
11 Remove(p->right, val);
12 } else {
13 BinaryTreeNode* oldNode = p;
14 p = (p->left != NULL) ? p->left : p->right;
15 delete oldNode;
16 }
17 完整代碼：
頭檔案：
1 #ifndef BINARY_SEARCH_TREE_H_
2 #define BINARY_SEARCH_TREE_H_
3
4 template <typename T>
5 class BinarySearchTree {
6 public:
7 BinarySearchTree(): root(NULL) {}
8 BinarySearchTree(const BinarySearchTree& rhs) {
9 root = Clone(rhs.root);
10 }
11
12 BinarySearchTree& operator=(const BinarySearchTree& rhs) {
13 if (this != &rhs) {
14 MakeEmpty(root_);
15 root = Clone(rhs.root);
16 }
17
18 return *this;
19 }
20
21 ~BinarySearchTree() {
22 MakeEmpty(root_);
23 }
24
25
26 //使用遞歸的方法查找
27 bool ContainsRecu(const T& val) const {
28 return Contains(root_, val);
29 }
30
31 //疊代的方法查找
32 bool ContainsIter(const T& val) const;
33 //判斷樹是否為空
34 bool IsEmpty() const {
35 return root_ == NULL;
36 }
37
38 //插入資料
39 void Insert(const T& val) {
40 Insert(root_, val);
41 }
42
43 //删除資料
44 void Remove(const T& val) {
45 Remove(root_, val);
46 }
47
48 private:
49 struct BinaryTreeNode;
50
51 bool Contains(BinaryTreeNode* root, const T& val) const;
52
53
54 BinaryTreeNode* FindMin(BinaryTreeNode* &p) const;
55 BinaryTreeNode* FindMax(BinaryTreeNode* &p) const;
56
57 void Insert(BinaryTreeNode* &p, const T& val);
58 void Remove(BinaryTreeNode* &p, const T& val);
59
60 BinaryTreeNode* Clone(BinaryTreeNode* root);
61 void MakeEmpty(BinaryTreeNode *root);
62
63 struct BinaryTreeNode {
64 T data;
65 BinaryTreeNode* left;
66 BinaryTreeNode* right;
67
68 BinaryTreeNode(T d = T(), BinaryTreeNode* l = NULL, BinaryTreeNode *r = NULL)
69 : data(d), left(l), right(r) {}
70 };
71
72 BinaryTreeNode *root_;
73 };
74 #endif 源檔案：
1 #include "binary_search_tree.h"
2
3 //public部分的函數定義
4 //疊代的方法查找
5 template<typename T> bool BinarySearchTree<T>::ContainsIter(const T& val) const {
6
7 BinaryTreeNode* p = root;
8
9 while (p != NULL && p->data != val) {
10 p = p->data < val ? p->right : p->left;
11 }
12
13 return p != NULL;
14 }
15
16 //private部分的函數定義
17
18 //查找：如果樹為空，則查找失敗
19 //如果值大于根節點關鍵字的值，遞歸查找右子樹
20 //如果值小于根節點關鍵字的值，遞歸查找左子樹
21 //如果根節點關鍵字的值等于查找的關鍵字，成功。
22 //平均查找複雜度O(lgN)
23 template<typename T>
24 bool BinarySearchTree<T>::Contains(BinaryTreeNode* root, const T& val) const {
25 if (root == NULL) {
26 return false;
27 } else if (val > root->data) {
28 return Contains(root->right, val);
29 } else if (val < root->data) {
30 return Contains(root->left, val);
31 } else {
32 return true;
33 }
34 }
35
36 //尋找最小節點的值：
37 //從根節點一直往左走，直到無路可走，即可以得到最小節點
38 //時間複雜度O(lgN)
39 template <typename T>
40 typename BinarySearchTree<T>::BinaryTreeNode* BinarySearchTree<T>::FindMin(BinaryTreeNode* &p) const {
41 while (p != NULL && p->left != NULL) {
42 p = p->left;
43 }
44
45 return p;
46 }
47
48 //尋找最大節點的值
49 //從根節點往右走，直到無路可走，即可得到最大元素。
50 //時間複雜度O（lgN）
51 template <typename T>
52 typename BinarySearchTree<T>::BinaryTreeNode* BinarySearchTree<T>::FindMax(BinaryTreeNode* &p) const {
53 while (p != NULL && p->right != NULL) {
54 p = p->right;
55 }
56
57 return p;
58 }
59
60 //插入新元素，從根節點開始，遇鍵值較大者就往右左，遇建值較小者就向右，一直到尾端，即為插入點。
61 //如果有重複節點，則什麼也不做
62 //時間複雜度O(lgN)
63 template<typename T>
64 void BinarySearchTree<T>::Insert(BinaryTreeNode* &p, const T& val) {
65 if (p == NULL) {
66 p = new BinaryTreeNode(val);
67 } else if (val > p->data) {
68 Insert(p->right, val);
69 } else if (val < p->data) {
70 Insert(p->left, val);
71 } else
72 ; //重複，不做任何操作
73 }
74
75 //删除節點： 如果節點是葉子節點，那麼它立即删除。
76 //如果節點有一個兒子，則該節點可以再其父節點調整它的鍊繞過該節點後被删除
77 //如果該節點有兩個兒子。一般的政策是用右子樹的最小的資料代替該節點的資料并遞歸地删除那個節點。
78 //因為右子樹最小的節點不可能有左兒子，是以第二次删除很容易。
79 //時間複雜度O(lgN)
80 template<typename T>
81 void BinarySearchTree<T>::Remove(BinaryTreeNode* &p, const T& val) {
82 if (p == NULL) {
83 return; //沒有此值
84 } else if (val > p->data) {
85 Remove(p->right, val);
86 } else if (val < p->data) {
87 Remove(p->left, val);
88 } else if (p->left != NULL && p->right != NULL) {
89 p->data = FindMin(p->right)->data;
90 Remove(p->right, val);
91 } else {
92 BinaryTreeNode* oldNode = p;
93 p = (p->left != NULL) ? p->left : p->right;
94 delete oldNode;
95 }
96 }
97
98 template<typename T>
99 typename BinarySearchTree<T>::BinaryTreeNode* BinarySearchTree<T>::Clone(BinaryTreeNode* root) {
100 if (root == NULL) return NULL;
101
102 return new BinaryTreeNode(root->val, Clone(root->left), Clone(root->right));
103 }
104
105 template<typename T>
106 void BinarySearchTree<T>::MakeEmpty(BinaryTreeNode* root) {
107 if (root != NULL) {
108 MakeEmpty(root->left);
109 MakeEmpty(root->right);
110 delete root;
111 }
112
113 root = NULL;
114 } 平衡二叉搜尋樹：
也許因為輸入值不夠随機，也許因為經過長時間插入和删除操作，二叉搜尋樹可能都會失去平衡，造成搜尋效率較低的情況。
比如，n個關鍵字按嚴格遞增次序被插入，則這棵樹一定是高度為為n-1的鍊。入下圖所示：
所謂樹形平衡與否，并沒有一個絕對的測量标準。平衡的大緻意義是：沒有任何一個節點過深（深度過大）。不同的平衡條件，造就出不同的效率表現、以及不同的實作複雜度。有數種特殊結構如AVL-tree、RB-tree、AA-tree，均可實作出平衡二叉樹，它們都比一般的（無法絕對維持平衡的）二叉搜尋樹複雜，是以，插入節點和删除節點的平均時間也比平均時間長，但是它們可以避免極難應付的最壞情況（高度不平衡的情況），而且由于它們總是保持某種程度的平衡，是以元素的通路（搜尋）時間平均而言也就比較少。
參考文獻：《資料結構域算法分析》--Mark Allen Weiss
《STL源碼剖析》--候捷
《算法導論》