一·概念：
静图展示：
动图展示：
①左子树不为空，则左子树节点值小于根节点值。
②右子树不为空，则右子树节点值大于根节点值。
③左右子树均为二叉搜索树。
④对于它可以插入相等的也可以插入不相等的,这里如果插入的话一般执行的就是覆盖操作，也就是不允许插入如：
注：以二叉树为底层的容器：map(key_value模型),set(key模型),multimap,multiset，其中前两个不支持插入相等的值，而后两者便支持。
二·性能分析：
最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O(log2 N)
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O( N)
所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)
下面是它的缺点：插入的数据在它中应该是有序的，而且要知道这样会可以随机访问里面的数据，那么插入与删除就变得复杂了，因此引出后面需要的平衡二叉树。
三·实现步骤：
下面把它的主体分为三点：插入，删除（复杂点），查找，（不支持修改，因为会改变这棵树的性质）。
3·1插入：
这里比较简单，就是找比这个节点值大就往右走，小就往左走，直到走到空，就可以开辟节点并插入，但是问题就是连接起来，因此需要保存上一个也就是parent节点：
bool insert(const k& key) {
//头结点直接加：
if (_root == nullptr) {
_root = new bsnode(key);
return true;
}
else {
//找到这个位置（通过搜索比较）
bsnode parent = nullptr;//为了连接：
bsnode 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 bsnode<k>(key);
//完成连接操作：
if (parent->_key > key) parent->_left = cur;
else parent->_right = cur;
return true;
}
}
3·2删除：
当然大体框架到了删除这一步一般就是难点了，因为考虑的情况很多，下面我们画图把它要考虑的情况画出：
代码：
bool erase(const k& key) {
bsnode parent = nullptr;
bsnode cur = _root;
if (_root == nullptr) return false;
//找到这个key的位置
while (cur) {
if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
else {
//下面就是找到了，开始删除操作：
//第一种情况：
if (cur->_left == nullptr && cur->_right == nullptr) {
//这里由于parent左右指针还和cur连一起，注意置空
if (parent == nullptr) {
delete cur;
}
else {
if (parent->_left == cur) parent->_left = nullptr;
else if (parent->_right == cur) parent->_right = nullptr;
delete cur;
}
//这里最后发现是多余分出了，可以和后面归为一类，就是要么左空要么右空一类（下面就先不更改了）
}
//第二种情况：
else if (cur->_left == nullptr) {
if (parent == nullptr) _root = cur->_right;//后面防止parent为空故用else
else {
if (parent->_left == cur) parent->_left = cur->_right;//看到要访问parent的左指针，就
//要考虑parent是否为空
else if (parent->_right == cur) parent->_right = cur->_right;
}
delete cur;
}
//第三种情况：
else if (cur->_right == nullptr) {
if (parent == nullptr) _root = cur->_left;
else {
if (parent->_left == cur) parent->_left = cur->_left;
else if (parent->_right == cur) parent->_right = cur->_left;
}
delete cur;
}
第四种情况：（相对复杂因为这里不能直接删，而是找一个正确位置的节点的key与它互换然后再删除那个节点）
//这里通过证明可以发现替换的那个节点是cur的右节点的最左节点：因为既然是cur的右节点的最左节点一定比①cur的右key小，
//然而既然能排到cur的右节点的那块最左边的这个节点，则它一定比cur大，②故就推出比cur的左节点key大
else {
bsnode<k>* er_right_min_p = cur;//它的父亲节点
bsnode<k>* er_right_min = cur->_right;//那个被替换要删除的节点
while (er_right_min->_left) {
er_right_min_p = er_right_min;
er_right_min = er_right_min->_left;//找到这个被替代节点
}
cur->_key = er_right_min->_key;//完成覆盖
//下面判断这个节点是父亲左节点还是右节点连接的：
if (er_right_min_p->_left == er_right_min)
er_right_min_p->_left = er_right_min->_right;
else if (er_right_min_p->_right == er_right_min)
er_right_min_p->_right = er_right_min->_right;//这里有一种情况就是当while没有进去，也就是
//er_right_min_p 与er_right_min未改变，这是就是父亲的右指针连接
delete er_right_min;
}
return true;
}
}
return false;
}
3·3查找：
这里由于不考虑相同值的情况，因此就按照它的性质去查找即可：
bool find(const k& key) {//这里也可搞成返回bsnode类型方便使用
bsnode cur = _root;
while (cur) {
if (cur->_key > key) cur = cur->_left;
else if (cur->_key < key) cur = cur->_right;
else return true;
}
return false;
}
四·应用（key与key_value):
4·1key模型：
上面提到了set容器就是key模型：
简单来说就是key不是决定了树的性质排列，然后值是对key来完成增删查等操作。
场景1：小区车牌号放行系统简单模拟。
场景2：检查单词是否出现拼写错误。
实现代码：
namespace K {
template< typename k>
struct bsnode {
k _key;
bsnode _left;
bsnode _right;
bsnode(const k& key) :
_key(key),
_left(nullptr),
_right(nullptr) {}
};
template< typename k>
class bstree {
public:
bstree() = default;
bstree(bstree<k>& t) {
_root = copy(t._root);//这里利用copy函数搞了个临时对象，为了不让swap操作这个root而是操作的临时对象
}
bstree<k> operator=(bstree<k> t) {
swap(_root, t._root);//t自定义类型会调用拷贝构造然后swap交换的事这个临时对象，t不受影响
return *this;
}
bool insert(const k& key) {
//头结点直接加：
if (_root == nullptr) {
_root = new bsnode<k>(key);
return true;
}
else {
//找到这个位置（通过搜索比较）
bsnode<k>* parent = nullptr;//为了连接：
bsnode<k>* 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 bsnode<k>(key);
//完成连接操作：
if (parent->_key > key) parent->_left = cur;
else parent->_right = cur;
return true;
}
}
bool find(const k& key) {//这里也可搞成返回bsnode*类型方便使用
bsnode<k>* cur = _root;
while (cur) {
if (cur->_key > key) cur = cur->_left;
else if (cur->_key < key) cur = cur->_right;
else return true;
}
return false;
}
bool erase(const k& key) {
bsnode<k>* parent = nullptr;
bsnode<k>* cur = _root;
if (_root == nullptr) return false;
//找到这个key的位置
while (cur) {
if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
else {
//下面就是找到了，开始删除操作：
//第一种情况：
if (cur->_left == nullptr && cur->_right == nullptr) {
//这里由于parent左右指针还和cur连一起，注意置空
if (parent == nullptr) {
delete cur;
}
else {
if (parent->_left == cur) parent->_left = nullptr;
else if (parent->_right == cur) parent->_right = nullptr;
delete cur;
}
//这里最后发现是多余分出了，可以和后面归为一类，就是要么左空要么右空一类（下面就先不更改了）
}
//第二种情况：
else if (cur->_left == nullptr) {
if (parent == nullptr) _root = cur->_right;//后面防止parent为空故用else
else {
if (parent->_left == cur) parent->_left = cur->_right;//看到要访问parent的左指针，就
//要考虑parent是否为空
else if (parent->_right == cur) parent->_right = cur->_right;
}
delete cur;
}
//第三种情况：
else if (cur->_right == nullptr) {
if (parent == nullptr) _root = cur->_left;
else {
if (parent->_left == cur) parent->_left = cur->_left;
else if (parent->_right == cur) parent->_right = cur->_left;
}
delete cur;
}
第四种情况：（相对复杂因为这里不能直接删，而是找一个正确位置的节点的key与它互换然后再删除那个节点）
//这里通过证明可以发现替换的那个节点是cur的右节点的最左节点：因为既然是cur的右节点的最左节点一定比①cur的右key小，
//然而既然能排到cur的右节点的那块最左边的这个节点，则它一定比cur大，②故就推出比cur的左节点key大
else {
bsnode<k>* er_right_min_p = cur;//它的父亲节点
bsnode<k>* er_right_min = cur->_right;//那个被替换要删除的节点
while (er_right_min->_left) {
er_right_min_p = er_right_min;
er_right_min = er_right_min->_left;//找到这个被替代节点
}
cur->_key = er_right_min->_key;//完成覆盖
//下面判断这个节点是父亲左节点还是右节点连接的：
if (er_right_min_p->_left == er_right_min)
er_right_min_p->_left = er_right_min->_right;
else if (er_right_min_p->_right == er_right_min)
er_right_min_p->_right = er_right_min->_right;//这里有一种情况就是当while没有进去，也就是
//er_right_min_p 与er_right_min未改变，这是就是父亲的右指针连接
delete er_right_min;
}
return true;
}
}
return false;
}
~bstree()
{
destroy(_root);
}
void inorder() {
_inorder(_root);
cout << endl;
}
private:
//中序遍历：
void _inorder(const bsnode<k>* root) {
if (root == nullptr) return;
_inorder(root->_left);
cout << root->_key << " ";
_inorder(root->_right);
}
//后序删除：
void destroy(bsnode<k>* root) {
if (root == nullptr) return;
destroy(root->_left);
destroy(root->_right);
delete root;
root = nullptr;
}
//前序安装：
bsnode<k>* copy(bsnode<k>* root) {
//这里递归完成：假设copy的递归已经完成到最后一步，即只需要按照根节点把它的左右子树连起来即可
if (root == nullptr) return nullptr;
bsnode<k>* newnode = new bsnode<k>(root->_key);
newnode->_left = copy(root->_left);
newnode->_right = copy(root->_right);
return newnode;
}
bsnode<k>* _root = nullptr;
};
}
4·2key_value模型：
key包含了性质，而value不改变性质只是一个标志，可以更改，而查找和删除还是根据key来决定。
场景1：单词的英汉互译。
场景2：无人停车时长收费计算系统模拟。
场景3：一些物品的计数统计。
这里如果要是实现只需要再key模型代码完成一些对value的改变即可：
namespace K_Value {
template< typename k,typename v>
struct bsnode {
k _key;
v _value;
bsnode _left;
bsnode _right;
bsnode(const k& key, const v& value) :
_key(key),
_value(value),
_left(nullptr),
_right(nullptr) {}
};
template< typename k, typename v>
class bstree {
public:
bstree() = default;
bstree(bstree<k,v>& t) {
_root = copy(t._root);//这里利用copy函数搞了个临时对象，为了不让swap操作这个root而是操作的临时对象
}
bstree<k,v> operator=(bstree<k,v> t) {
swap(_root, t._root);//t自定义类型会调用拷贝构造然后swap交换的事这个临时对象，t不受影响
return *this;
}
bool insert(const k& key, const v& value) {
//头结点直接加：
if (_root == nullptr) {
_root = new bsnode<k,v>(key,value);
return true;
}
else {
//找到这个位置（通过搜索比较）
bsnode<k,v>* parent = nullptr;//为了连接：
bsnode<k,v>* 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 bsnode<k,v>(key,value);
//完成连接操作：
if (parent->_key > key) parent->_left = cur;
else parent->_right = cur;
return true;
}
}
bsnode<k,v>* find(const k& key) {
bsnode<k,v>* cur = _root;
while (cur) {
if (cur->_key > key) cur = cur->_left;
else if (cur->_key < key) cur = cur->_right;
else return cur;
}
return nullptr;
}
bool erase(const k& key, const v& value) {
bsnode<k,v>* parent = nullptr;
bsnode<k,v>* cur = _root;
if (_root == nullptr) return false;
//找到这个key的位置
while (cur) {
if (cur->_key > key) {
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
else {
//下面就是找到了，开始删除操作：
//第一种情况：
if (cur->_left == nullptr && cur->_right == nullptr) {
if (parent == nullptr) {
delete cur;
}
else {
if (parent->_left == cur) parent->_left = nullptr;
else if (parent->_right == cur) parent->_right = nullptr;
delete cur;
}
//这里最后发现是多余分出了，可以和后面归为一类，就是要么左空要么右空一类（下面就先不更改了）
}
//第二种情况：
else if (cur->_left == nullptr) {
if (parent == nullptr) _root = cur->_right;//后面防止parent为空故用else
else {
if (parent->_left == cur) parent->_left = cur->_right;//看到要访问parent的左指针，就
//要考虑parent是否为空
else if (parent->_right == cur) parent->_right = cur->_right;
}
delete cur;
}
//第三种情况：
else if (cur->_right == nullptr) {
if (parent == nullptr) _root = cur->_left;
else {
if (parent->_left == cur) parent->_left = cur->_left;
else if (parent->_right == cur) parent->_right = cur->_left;
}
delete cur;
}
第四种情况：（相对复杂因为这里不能直接删，而是找一个正确位置的节点的key与它互换然后再删除那个节点）
//这里通过证明可以发现替换的那个节点是cur的右节点的最左节点：因为既然是cur的右节点的最左节点一定比①cur的右key小，
//然而既然能排到cur的右节点的那块最左边的这个节点，则它一定比cur大，②故就推出比cur的左节点key大
else {
bsnode<k,v>* er_right_min_p = cur;//它的父亲节点
bsnode<k,v>* er_right_min = cur->_right;//那个被替换要删除的节点
while (er_right_min->_left) {
er_right_min_p = er_right_min;
er_right_min = er_right_min->_left;//找到这个被替代节点
}
cur->_key = er_right_min->_key;//完成覆盖
//下面判断这个节点是父亲左节点还是右节点连接的：
if (er_right_min_p->_left == er_right_min)
er_right_min_p->_left = er_right_min->_right;
else if (er_right_min_p->_right == er_right_min)
er_right_min_p->_right = er_right_min->_right;//这里有一种情况就是当while没有进去，也就是
//er_right_min_p 与er_right_min未改变，这是就是父亲的右指针连接
delete er_right_min;
}
return true;
}
}
return false;
}
~bstree()
{
destroy(_root);
}
void inorder() {
_inorder(_root);
cout << endl;
}
private:
//中序遍历：
void _inorder(const bsnode<k,v>* root) {
if (root == nullptr) return;
_inorder(root->_left);
cout << root->_key << ":"<<root->_value;
_inorder(root->_right);
}
//后序删除：
void destroy(bsnode<k,v>* root) {
if (root == nullptr) return;
destroy(root->_left);
destroy(root->_right);
delete root;
root = nullptr;
}
//前序安装：
bsnode<k,v>* copy(bsnode<k,v>* root) {
//这里递归完成：假设copy的递归已经完成到最后一步，即只需要按照根节点把它的左右子树连起来即可
if (root == nullptr) return nullptr;
bsnode<k>* newnode = new bsnode<k,v>(root->_key);
newnode->_left = copy(root->_left);
newnode->_right = copy(root->_right);
return newnode;
}
bsnode<k,v>* _root = nullptr;
};
}
到此为止希望对你对二叉搜索树的理解有点帮助，感谢支持！！！
