二叉搜索树

二叉搜索树，也叫二叉排序树、二叉查找树或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 }

寻找最大值：

　　从根节点一直往右走，直到无路可走。

　　时间复杂度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 }

插入：

　　插入新元素时，可从根节点开始，与键值较大者就向左，遇键值较小者就向右，一直到尾端，即为插入点。

　　注意：新插入的节点总是叶子节点，如果树种有相同的节点，则不做任何操作。

　　时间复杂度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. 如果节点有两个儿子的节点，一般的删除策略是用其右子树的数据代替该节点的数据并递归地的删除那个节点。

　　时间复杂度O(lgN)

 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源码剖析》--候捷

　　　　　 《算法导论》