厦门网络科技有限公司_广州新一期lpr_创建自己的网站怎么弄_优化搜狗排名

二叉搜索树的结构

二叉搜索树其实和二叉树差不多，都是一颗树，但是它有点排序的作用，因为比根节点大的在根的右边，比根节点小的在根节点的左边，以此类推，这样下来只要走一个高度次就能确认一个数在不在里面，不过这是最好的情况，因为如果是有序或者一直来大于或者小于根的值，那么这棵树虽然还是搜索树，但是其实已经失衡了，这样效率就会变低，所以它还是带点缺陷的。

这就是它的基本结构，需要注意的是这里的节点暂时是不允许重复且不能插入的，后面会有multi版本支持重复，但是还是不允许插入，因为它害怕结构被破坏。

二叉搜索树的实现

  

为了方便写 我们先typedef一下咱的树节点

插入insert：

	bool insert(const K& key){if (_root == nullptr)//二叉树老样子{_root = new node(key);//不过在这里如果为空需要new一个根节点出来return true;}node* parent = nullptr;//按照后面的逻辑 我们的cur会走到虚空里去 所以得记录一下它的父node* cur = _root;//这两行就是前后指针 方便cur走到虚空后 父还能连接到curwhile (cur)//递归和循环 当然是选循环了 规避一下栈溢出{if (cur->_key < key)//按照逻辑 大走右{parent = cur;//前后指针记录一下cur = cur->_right;}else if (cur->_key > key)//小走左{parent = cur;cur = cur->_left;}else{return false;//走到这说明因为某些原因失败了(比如重复的数) 直接返回flase就好}}node* newnode = new node(key);//上面走完说明父和cur都找到指定位置了 那么先new一个key值的节点出来if (parent->_key < key)//然后判断大于还是小于父 直接插入即可{parent->_right = newnode;}else{parent->_left = newnode;}return true;//走到这说明插入成功 返回true}

找find:

	bool find(const K& key){node* cur = _root;//还是从根开始找while (cur){if (cur->_key < key)//根小找右{cur = cur->_right;}else if (cur->_key > key)//根大找左{cur = cur->_left;}else{return true;//不大不小不重复就是找到了 返回true}}return false;//走到这说明找不到}

删除erase:

bool erase(const K& key)//这个有点复杂{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{//这里就需要区分情况 //一共有四种情况 左为空 右为空 左右都为空 左右都不为空//前面三个我们其实可以归为两种 左为空 右为空if (cur->_left == nullptr)//在左为空的大前提下{if (cur == _root)//如果我本身就是根 那删除就太简单了 我的右升级为根 {_root = cur->_right;}else//不然我不是根 那就老老实实找替代品{if (parent->_left == cur)//如果上面更新完的父的左等于cur 那说明右为空{//把cur的右连接到原本cur的位置parent->_left = cur->_right;}else//不然就是左为空{//把cur的右连接到cur的位置parent->_right = cur->_right;}}delete cur;//连接完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{//换一种方式记录父和cur 因为原本的父不用动node* rparent = cur;node* replace = cur->_right;//替代品while (replace->_left){rparent = replace;replace = replace->_left;}//走到这我们可以确认是两边都有节点的情况//又根据搜索树的特性我们可以知道 左的最右和右的最左其实就是很好的替代品//用它们替代被删除的位置很完美//所以我们根据这俩特性任选一边当替代品即可cur->_key = replace->_key;//直接把要删除的位置的数据改成替代品的数据if (rparent->_left == replace){rparent->_left = replace->_right;//上面走完rplace已经属于是孤儿节点了//所以其实就是把replace的位置先置为空}else{//同理rparent->_right = replace->_right;}//然后删除replace就好delete replace;}//能走到这就说明成功了return true;}}return false;//while走完没返回true 我管你啥问题我都先返回false再说}

其实双节点的删除就是这么个过程

单节点就更简单了

    二叉搜索树除了删除复杂一点，其实大部分还是二叉树的正常操作，多出来的特性只是提升了它一点点功能而已。关键的提升在于map和set对它的提升

使用场景

对于二叉搜索树的使用场景其实有两个，一个就是上面我们实现的key版本，但是它也多少有点缺陷，因为不能修改，所以衍生了一个 key + key_value的版本出来。

它既照顾到了不能修改的特性又实现了修改，它的key还是不能修改，但是它有一个key_vlaue用来存值。

比如说停车场，进了车先记录车牌，也就是key，车牌不能修改，同时key_value记录进场时间，等要走的时候用现在的时间减去key_value记录的时间，但是如果我和停车场保安是亲戚，我就可以叫他改一下我的入场时间，直接免费停车。