1.二叉搜索树的概念

二叉搜索树又称为二叉排序树，为什么这么说呢，我们学过就知道，对二叉搜索树进行一遍中序遍历，就会实现排序的功能。二叉搜索树也可以是一个空树，他的性质有如下几点：

1. 若它的左子树不为空，则左子树上的结点值都是小于或等于根结点的值。
2. 若它的右子树不为空，则右子树上的结点值都是大于或等于根结点的值。
3. 它的左右子树也是一个二叉搜索树。
4. 二叉搜索树可以支持插入相等的值（如mutiset、mutimap），有的不允许插入相等的值（如set、map），具体使用哪个要看具体场景，后续我们会学到这些容器，他们就像二叉搜索树一下，底层是用红黑树实现的。
   
   上图就是一个二叉搜索树，他的左子树的值都是比根结点小的，而右子树的值都是比根结点大的。
   再次，我们用中序遍历遍历一遍这个二叉树，就可以实现一个排序好的递增的顺序。

2.二叉搜索树的性能分析

二叉搜索树最优情况下，其高度为logN（完全二叉树）。
二叉搜索树最差情况下，其高度为N
综合来说，二叉搜索树的增删查的时间复杂度为O(N)
当然，朴素的二叉搜索树在项目中是很少使用的，之后我们会看到他们的变种，如AVL树、红黑树。

Q：为什么要设计二叉搜索树？我们想查找使用二分查找效率不是很高吗？
A：二分查找只支持可以随机访问的结构中，而且需要有序；而且二分查找只能查找，他插入和删除数据效率是很低的。

3.二叉搜索树的接口设计

这里先声明一下，对于二叉搜索树，“改”是没有必要的，而且改完数据再恢复到二叉搜索树很难设计，因此我们只会实现增、删、查

3.1 二叉搜索树的插入

例如，我们还是给如上的例子，我们想插入4怎么实现呢？

1. 若树为空，直接新增节点，把它赋值给root
2. 若树不空，我们要满足二叉搜索树的性质：左子树 < 根 < 右子树；若我们插入的数大于根结点则往右走，反之往左走，知道走到空位置，插入他。
3. 如果是实线满足插入相等值的情况下，既可以往左走，也可以往右走，找到空位置插入。（注意：要满足逻辑的一致性，要是往左就一直往左）

代码实现统一在后面给出。

3.2 二叉搜索树的查找

步骤：

1. 从根节点开始查找比较，比根结点值大就往右，反之往左
2. 最多查找根的高度次，走到空还是没找到，说明就这值就不存在
3. 如果不支持插入相等的值，找到这个值即可
4. 如果支持插入相等的值，意味着树中可能存在多个这个值，一般是找到第一个即可（我们一般采取中序遍历的方式找，这样不容易找漏）。

3.3 二叉搜索树的删除

删除的过程最为复杂，首先我们要确定这个值在书中存在不存在，不存在我们直接返回false。

如果该值存在，要删除的节点N有如下四种情况：

1. 要删除的节点N左右孩子均为空
2. 要删除的节点N左孩子为空，右孩子不为空
3. 要删除的节点N左孩子不为空，右孩子为空
4. 要删除的节点N左右孩子均不为空。

对于上面四中情况的解决如下：

1. 直接free掉N，删除节点N（这种情况可以和2、3一起处理，不用单独处理）
   
2. 把节点N的父亲指向N的右孩子，然后直接删除N
   
3. 把节点N的父亲指向N的左孩子，然后直接删除N
   
4. ⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。
   

3.4 代码实现

//树的节点
template <class T>
struct BSTNode
{T _key;//值struct BSTNode* _left;//左孩子struct BSTNode* _right;//右孩子//构造BSTNode(const T& key):_key(key),_left(nullptr),_right(nullptr){}
};//二叉搜索树
template <class T>
class BSTree
{typedef struct BSTNode<T> Node;
public://插入操作bool Insert(const T& key){//1.当树还是一个空树时if (_root == nullptr){_root = new Node(key);return true;}//2.当树不为空Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else return false;//我们构建的二叉搜索树不允许有重复的值}cur = new Node(key);if (parent->_key < key) parent->_right = cur;else parent->_left = cur;return true;}//查找操作bool Find(const T& key){Node* cur = _root;while (cur){if (cur->_key < key) cur = cur->_right;else if (cur->_key > key) cur = cur->_left;else return true;}return false;}//删除操作bool Erase(const T& key){if (_root == nullptr) return false;Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//1.左孩子为空if (cur->_left == nullptr){//特别注意，当删除的就是根节点时if (cur == _root) _root = cur->_right;else{if (cur == parent->_left)	parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;}//2.右孩子为空else if (cur->_right == nullptr){//特别注意，当删除的就是根节点时if (cur == _root) _root = cur->_left;else{if (cur == parent->_left)	parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;}//3.左右均不为空else{//这里我们找右子树的最小节点（最左下角）Node* replace = cur->_right;Node* replaceParent = cur;//不能给nullptr；循环不一定进去，导致空指针的解引用while (replace->_left){replaceParent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);if(replaceParent->_left == replace)	replaceParent->_left = replace->_right;else replaceParent->_right = replace->_right;delete replace;}}}return false;//都没有找到这个节点}//中序遍历，可以对二叉搜索树进行排序操作void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(const Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;//根节点
};