一·概念：

静图展示：

动图展示：

①左子树不为空，则左子树节点值小于根节点值。

②右子树不为空，则右子树节点值大于根节点值。

③左右子树均为二叉搜索树。

④对于它可以插入相等的也可以插入不相等的,这里如果插入的话一般执行的就是覆盖操作，也就是不允许插入如：

注：以二叉树为底层的容器：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<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;}}

3·2删除：

当然大体框架到了删除这一步一般就是难点了，因为考虑的情况很多，下面我们画图把它要考虑的情况画出：

代码：

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为空故用elseelse {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<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;
}

四·应用（key与key_value):

4·1key模型：

上面提到了set容器就是key模型：

简单来说就是key不是决定了树的性质排列，然后值是对key来完成增删查等操作。

场景1：小区车牌号放行系统简单模拟。

场景2：检查单词是否出现拼写错误。

实现代码：

namespace K {template< typename k>struct bsnode {k _key;bsnode<k>* _left;bsnode<k>* _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为空故用elseelse {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<k,v>* _left;bsnode<k,v>* _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为空故用elseelse {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;};}

到此为止希望对你对二叉搜索树的理解有点帮助，感谢支持！！！