目录1. 二叉搜索树的概念2. 二叉搜索树的性能分析3. 二叉搜索树的插入4. 二叉搜索树的查找5. 二叉搜索树的删除6. 二叉搜索树的实现代码7. 二叉搜索树key和key/value使用场景7.1 key搜索场景7.2 key/value搜索场景7.3 key/value二叉搜索树代码实现1. 二叉搜索树的概念二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:• 若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值• 若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值• 它的左右子树也分别为二叉搜索树• 二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值2. 二叉搜索树的性能分析最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其高度为最差情况下二叉搜索树退化为单支树(或者类似单支)其高度为O(N)所以综合而言二叉搜索树增删查改时间复杂度为 O(N)那么这样的效率显然是无法满足我们需求的我们后续课程需要继续讲解二叉搜索树的变形平衡二叉搜索树(AVL树)和红黑树才能适用于我们在内存中存储和搜索数据。另外需要说明的是二分查找也可以实现 O(logN)级别的查找效率但是二分查找有两大缺陷1. 需要存储在支持下标随机访问的结构中并且有序。2. 插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。这里也就体现出了平衡二叉搜索树的价值。3. 二叉搜索树的插入插入的具体过程如下1. 树为空则直接新增结点赋值给root指针2. 树不空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。3. 如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走测试数组int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };4. 二叉搜索树的查找1. 从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。2. 最多查找高度次走到到空还没找到这个值不存在。3. 如果不支持插入相等的值找到x即可返回4. 如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回5. 二叉搜索树的删除首先查找元素是否在二叉搜索树中如果不存在则返回false。如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N1. 要删除结点N左右孩子均为空2. 要删除的结点N左孩子为空右孩子结点不为空3. 要删除的结点N左孩子不为空右孩子结点为空4. 要删除的结点N左右孩子结点均不为空对应以上四种情况的解决方案(1). 把N结点的父亲对应孩子指针指向空直接删除N结点情况1可以当成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可以直接删除。6. 二叉搜索树的实现代码二叉搜索树实现代码7. 二叉搜索树key和key/value使用场景7.1 key搜索场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。场景1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在则抬杆不在则提示非本小区车辆无法进入。场景2检查一篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不在则波浪线标红提示。7.2 key/value搜索场景每一个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改但是不支持修改key修改key破坏搜索树结构了可以修改value。场景1简单中英互译字典树的结构中(结点)存储key(英文)和vlaue(中文)搜索时输入英文则同时查找到了英文对应的中文。场景2商场无人值守车库入口进场时扫描车牌记录车牌和入场时间出口离场时扫描车牌查找入场时间用当前时间-入场时间计算出停车时长计算出停车费用缴费后抬杆车辆离场。场景3统计一篇文章中单词出现的次数读取一个单词查找单词是否存在不存在这个说明第一次出现单词1单词存在则单词对应的次数。7.3 key/value二叉搜索树代码实现C二叉搜索树key-value的实现