说明：本文仅供学习交流，转载请标明出处，欢迎转载！

        二分查找树BST（也叫二叉查找树、二叉排序树）的提出是为了提供查找效率，之所以称为二分查找树，因为该二叉树对应着二分查找算法，查找平均的时间复杂度为o(logn)，所以该数据结构的提出是为了提高查找效率。

       定义

       二分查找树或者是一棵空树，或者具有下列性质：

       1.若它的左子树不为空，则左子树上所有结点的值均小于根结点的值；

       2.若它的右子树不为空，则右子树上所有结点的值均大于根结点的值；

       3.它的左右子树均为二分查找树。

       操作

       二分查找树的操作主要包括：插入、查找、删除。

       1.插入操作

        设s指向待插入的结点，root指向二叉查找树的根结点,则插入操作的步骤如下：

        （1）若root为空，则将s指向的结点作为跟结点插入，否则执行（2）、（3）；

        （2）若s->data < root->data，则将s指向的结点插入到根结点的左子树中；

        （3）若s->data > root->data，则将s指向的结点插入到根结点的右子树中。

        总结：二叉树的构造就是通过不断地插入新的元素。

      2.查找操作

      在二分查找树中查找给定值k的查找过程如下：

     （1）若root=NULL，则查找失败；

     （2）若root->data=http://www.mamicode.com/k，则查找成功；

     （3）若k <  root->data，则去root的左边查找；

      （4）若k > root->data，则去root的右边查找。

      总结：若二分查找树接近平衡二叉树，则其时间复杂度为O(logn)，若二分查找树是斜的（如插入是有序插入的情况下），则其实际复杂度为O(n)，即退化为线性表。

      3.删除操作

      设p指向待删除的结点，pre指向待删除结点的父亲，则删除操作视如下情况而定：

    （1）若待删除的结点是叶子结点，不妨设pre->right=p(即待删除的结点为其父亲结点的右孩子)，则直接删除p，对应为：pre->right=NULL，delete p；

    （2）若待删除的结点只有左子树或右子树，则只需将待删除结点的父亲与左孩子（或右孩子）连接起来，对应为，不妨设pre->right=p,以待删除结点仅有左子树的情况为例（右子树同理），对应为：pre->right=p->left，delete p；

     （3）若待删除结点左右子树都有，则执行如下步骤：

        总体来说，整个线索是：找到右子树的最小值结点-->连接断开结点-->对最小值结点的上下文做善后工作。

        I.先找到待删除结点的右子树中的最小值（或左子树中的最大值），对应的指针为min，并记下min的父亲结点为min_pre；

       II.用min所指结值覆盖待删结点的值，对应为:p->data=http://www.mamicode.com/min->data；

       III.分两种情况（如下图所示）：

       特殊情况：若待删除结点的右孩子无左子树，也就是说待删结点的右孩子就是右子树的最大值，则直接连接即可，对应为：p->right=min->right，delete min；

       一般情况：若待删除结点的右孩子有左子树，则将min_pre所指结点的右孩子指向min所只结点的右孩子，对应为：min_pre->right=min->right，delete min；

      举例：

      假设有下图所示的二分查找树，现在我们分别对该树做杉树情况的删除操作。

     删除元素1（叶子结点）：

     删除元素9（只有一个孩子）：

     删除元素7（有左右孩子）

     4.懒惰删除

       通常情况下的删除策略都是用待删除结点的右子树中的最小结点来替换待删除的结点，但这种删除方法的效率其实不高，因为它沿着该树进行两趟搜索，第一次搜索是为了找到待删除的结点的位置，即p，第二趟搜索是为了找到最小的替补，即min。如果删除的次数不多，则通常采用的策略是懒惰删除（lazy deletion)。

        懒惰删除的思想是：当一个元素被删除时，它仍然留在树中，只对它做删除标记。下次我们做搜素操作时，把该元素当作是一个存在的元素（当然，如果查找的元素就是该元素，我们只要看下该元素是否有删除标记），当作删除操作时，该元素被当作一个空元素，当在带有删除标记的点处插入新元素时，就把该位置当作一个空位置。

       5.含有重复元素的二分查找树

       含有重复元素的二分查找树的难题在于如何元素插入的问题，这里提供了一种解决的方法：通过在每个结点记录中保留一个附加域以指示该结点元素出现的次数。当然这也大大增加了附加空间，但是却比重复信息放到树中要好（因为如果将重复元素放到树中会增加树的深度）。

        元素的删除问题：由于树中可能存在重复的元素，这时候我们可以采用懒惰删除。即当元素出现删除操作时，就将该元素出现的次数减1，若减到次数为0，则将该元素标记为被删除状态（而实际上并未真正被删除）。

        测试代码如下：

#include<iostream>
using namespace std;
struct Node
{
	int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		this->data=http://www.mamicode.com/data;>
        测试结果如下：

参考资料：
[1]《数据结构(C++版）王红梅等》
[2]《数据结构与算法分析---C语言描述 原书第二版》