1.概念
二叉搜索树又叫做二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树
（1）若左子树不为空，左子树所有结点都小于（等于）根节点的值
（2）若右子树不为空，右子树所有结点都大于（等于）根节点的值
（3）它的左右子树也是二叉搜索树
二叉树可以支持插入相等的值，也可以不支持，看具体场景，后面的set,multiset,map,multimap容器底层就是二叉搜索树，set和map不支持插入相等的值，而multiset和multimap支持插入相等的值
2.性能分析
最好的情况下，二叉搜索树接近一棵完全二叉树，查找次数最多为高度次（logN），最坏的情况下，二叉搜索树是单支树，高度为（N/2），综合二叉走所属增删查改的时间复杂度为O（N）。
后面的红黑树和AVL树也是二叉搜索树的变形，进一步提高了搜索的速率。
以前我们所学的二分查找，它的时间复杂度也可以达到O（logN），但是要存储在下标可以随机访问的结构中，并且要有序，此外增删数据需要挪动数据，代价太大。
3.二叉搜索树的相关算法
3.1 插入
(1)若树为空，直接将结点赋给root指针。
（2）若树不为空，比较插入值和当前结点，若插入值比当前结点小往左走，比当前结点往右走，找到空结点位置，注意记录空结点的双亲结点，便于链接。
（3）如果支持插入相等的值，可以往左走，也可以往右走，找到空位置插入即可。
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;
}3.2 查找
（1）从根开始比较，查找x，x比根的值大往右走，比根小往左走。
（2）最多查找高度次，若走到空，则没有找到，这个值就不存在。
（3）如果不支持插入相等的值，找到即可返回
（4）若支持插入相等的值，则可能会有多个x，一般是返回中序的是第一个x，这是为后面支持相同数据插入的二叉搜索树的删除数据做铺垫，找到中序的第一个x，根据中序遍历，依次可以找到后面的x并删除。
bool Find(const K& key)
{Node* cur = _root;while (cur){if (key < _root->_key){cur = cur->_left;}else if (key > _root->_right){cur = cur->_right;}else{return true;}}return false;
}3.3 删除
假设被删除结点为N，首先查找被删除结点N是否在二叉搜索树中，如果不存在返回false，如果找到，这个结点有4种情况.
（1）N的左右孩子都为空
（2）左孩子为空，右孩子不为空
（3）左孩子不为空，右孩子为空
（4）左右孩子均不为空
对应上述4种情况，对应4种处理方法
（1）这种就是删除其叶子结点，直接将其父结点的孩子结点指向空
（2）将N的父结点的孩子结点指向N的右孩子
（3）将N的父节点的孩子结点指向N的左孩子
（4）无法直接删除N结点，N的两个孩子无处安放，若直接删除，会破坏二叉搜索树的结构，可以使用替换法删除。找到N左子树的最大结点R（最右结点）或者N右子树的最小结点R（最左结点）来替换N，这样替换后仍然满足二叉树的搜索规则。
这里的替代指的是将结点N和R的值交换， 转换为删除R结点，R结点一定符合情况2或3。
bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (key < _root->_key){parent = cur;cur = cur->_left;}else if (key > _root->_right){parent = cur;cur = cur->_right;}else//找到结点开始删除{//被删除结点的左子树为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}//被删除结点的右子树为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}//被删除结点的左右子树都不为空//找右子树最左面的结点替代要被删除结点else{Node* replaceParent = cur;Node* replace = cur->_right;//右子树的最小结点是右子树的最左面的结点while (replace->_left){replaceParent = replace;/replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left == replace->_right;elsereplaceParent->_right == replace->_right;delete replace;}}}return false;
}4 二叉搜索树key和key/value的使用场景
4.1 key的搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构了。
场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示本小区车辆，无法进⼊。
场景2：检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中单
词，查找是否在⼆叉搜索树中，不在则波浪线标红提示。
4.2 key/value搜索场景
每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修改key破坏搜索树结构了，可以修改value。
场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。
场景2：商场无人值守⻋库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，⽤当前时间-入场时间计算出停车时长，计算出停车费⽤，缴费后抬杆，车辆离场。
场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。
