巩义网站建设哪家专业,公司网站点击量如何看,百度推广怎么收费标准案例,前端素材网站文章目录 查找基本概念线性表查找顺序查找折半查找#xff08;二分#xff09;分块查找 树查找二叉排序树#xff08;BST#xff09;平衡二叉树#xff08;AVL#xff09;的插入平衡化复杂度分析 平衡二叉树的删除 红黑树红黑树的定义和性质红黑树定义红黑树性质 红黑树的… 文章目录 查找基本概念线性表查找顺序查找折半查找二分分块查找 树查找二叉排序树BST平衡二叉树AVL的插入平衡化复杂度分析 平衡二叉树的删除 红黑树红黑树的定义和性质红黑树定义红黑树性质 红黑树的插入红黑树的删除 B树B树基础B树插入和删除B树 散列查找 查找
基本概念 查找表其实就类似于数据库的数据表。 所谓的数据项就是数据库的一列而关键字就是key是唯一的。
查找长度SL即key的比较次数ASL是Average SL
线性表查找
顺序查找 基本的查找算法如果不会写就废了注意循环跳出条件key匹配则跳出
哨兵可以简化代码本质在于哨兵和普通元素的逻辑是一致的但是可以发挥出终止的效果 因此for循环不需要考虑越界最后return的时候也不需要判断是否查找成功哨兵本身的0下标就代表失败
其实链表里的头结点也是一种哨兵。 查找的优化思路有二
有序情况下假定顺序如果key已经大于目标key了那么后面也就没必要继续扫了即提前终止可以减少失败ASL如果已知查找到的概率那么可以将高概率的排在前面即提前成功可以减少成功ASL
分析ASL的时候可以用判定树来分析将判定逻辑写成树分析ASL的思路如下
成功的ASL就把n个成功节点加权和而失败的ASL就把n1个失败节点加权和单个成功节点的SL高度而失败节点的SL父节点高度 折半查找二分 前提是有序。
low和high构成一个闭区间目标元素只可能在闭区间内每次要和mid对比。
和mid对比情况有两大类
等则成功不等则代表只能在两侧区域不包括mid因此边界要调整为mid-1小mid1大 此时你可能会怀疑最后能不能收敛如果你是以mid为新边界下面这种情况可能就无法收敛了但是如果你去掉mid即以mid1为新边界假设能查到最坏的情况也一定会收敛到具体的一个点上此时lowhigh
假设查不到在收敛到具体的一个点后low和high就要错开构成lowhigh的情景此时直接报错 整体来看这个算法过程如下
考察区域从全部收敛到-1 极限情况low≤high一定会不断收缩一定可以判定完最后一个点之后继续走的话low和high会交错退出循环 在收敛过程中如果成功则提前退出循环
因此这个算法是完美无缺的可以全覆盖所有可能。 分析效率继续用判定树这个判定树是非常的神奇好用把成功节点mid逐层展开再补上失败节点就如下图 需要注意的是假如总结点数量为偶数个那么考虑到mid是向下取整就会出现右子树左子树1的现象不可能更多了也就是说右子树-左子树0或1只有这两种可能。
反过来如果mid向上取整自然就是左-右0或1
无论哪种方式折半查找判定树是平衡二叉树而且只可能有最下面一层不满那么树高就可以用完全二叉树的算法去算即logn1向下取整 分块查找
其实分块的最佳储存结构是索引数组n条链表操作系统里也会有类似结构出现比如文件索引 分块查找索引顺序索引用来缩减范围进而使得顺序查找次数更少 值得讨论的是查找索引的过程。
首先要明白索引中的maxValue代表索引中最大的值包括最大这是后面讨论的基础
midkey这种情况其实比较少见mid≠key则最终一定会停在low上 最终high在左low在右因为low左边都是小于目标key的根据前面maxValue的意义索引的值都小于key了那必然不存在所以low左边是不可能的太小而low右边又太大了那么最后就会卡在low上假如low越界代表所有索引对应的块都不可能存在目标key
对于每一个节点其SL索引查找次数顺序查找次数
需要注意折半情况下的索引查找次数分析起来比较复杂假如key≠mid那么最后就要反复调整直到highlow的时候这才是真正的索引次数。
因为SL有两部分而且相关联所以算ASL比较麻烦为了便于分析直接把数组等分那么这两部分的关联性就打破了可以分别计算ASL1和ASL2最后相加。 具体分析顺序情况下nsb因此把bn/s带进去ASL就可以得到一个式子进而求得极限情况的ASL 其实这才是最完美的索引顺序结构。 树查找
二叉排序树可以说是带有伸缩功能的顺序数组只是说不平衡会导致其效率退化 而进一步的AVL树弥补了不平衡的问题在保证伸缩性的前提下最大化逼近数组的效率 可以说是比较完美的结构了。
二叉排序树BST 递归和循环的思路一样
退出条件空或者匹配到否则就查左/右子树 插入就是要找到插入点位
有一样的失败没有一样的生成新节点令父节点链域指向该节点。 父节点指针从何而来需要注意BSTree T也就是说在最后T0的时候这个T不仅仅是空指针其本身还是父节点的孩子链域因此我们直接把T指向新节点就可以了在第一步就完成了。记得初始化左右孩子为NULL
有了插入后给定一个TNULL的初始链域就可以反复插入形成二叉树。 删除节点这个涉及到树结构的重构比较复杂
叶子结点只有单边孩子有双边孩子按照中序序列上层是左根右展开后变为左根右根左根右删去根后有两种顶替思路 以右子树最左边的节点顶替根大中最小那么拆掉的这个节点又该怎么补呢恰好最左边的节点一定不可能有左子树这就划归到了2情况左侧情况反过来就行
查找效率用ASL评估这俩在查找中是等价的。
给定具体的一个例子成功的ASL则要去计算n个成功节点的加权而失败则要补n1个失败节点再加权
下图表示二叉树查找的平均效率与其高度成正比那么理想情况是把高度压制成平衡二叉树这就是后面的内容了。 平衡二叉树AVL的插入 平衡化
平衡二叉树任一节点的平衡因子左-右都只可能是-1,01如果添加节点导致破坏平衡性就要找到最小不平衡树进行平衡化修正 以最小不平衡树根节点为A则不平衡无非就是四种情况LLLRRLRR这四种情况的记忆方法如下
第一个字母代表A的左右子树第二个字母代表子树的左右孩子
因此LL就是左子树左孩子插入导致不平衡到时候自己画图就好。
首先要说明三个子树都是H高度这个是铁定的否则插入就不会破坏平衡性。
LL和RR比较简单本质在于让B当根节点因此转一下就行
看下操作实际上是要让B当根A当孩子因此分三步写旋转代码要按这三个步骤来
替换A的左孩子此时A成为一颗可以随意挪动的树让A成为B的孩子让B成为根节点 LR和RL复杂一些对于LR具体还要把L子树的R孩子高度为H1继续展开以便于分析但是实际上这两种情况是一样的因此假定是下图情况。
但是实际上本质不变最终的目标是让C当根节点BA分别为左右那么C就要转两下先和B在和A这样C就可以变成根节点两次旋转沿用前面的思路即可。
RL也是如此最终要让C当根节点。 最后再整体总结一下你会发现4类情况最小不平衡子树本来都是H2高度然后插入新节点变成H3破坏平衡性调整以后重归H2同时平衡性保持住了
之所以只调整最小不平衡树就可以保证整体平衡性是因为这一通调整将多出来的高度抹平了更上面的节点的平衡因子自然就退回到平衡状态了。
我们把眼光落实在做题上你要盯一眼从下往上找到第一个不平衡的节点代表最小不平衡树的根节点然后回忆4种情况标上ABC剩下步骤就很简单了如此就秒杀了。 复杂度分析
无论是插入还是删除费时间的其实还是查找目标位置说白了ASL和查找是一样的调平衡度不影响。
再有就是复杂度分析ASL层数即Oh效率关键在于如何通过节点数量n计算h的上界或者通过h计算n的下界
这是个数学问题根本在于AVL的特性即平衡因子最多为1那么极限情况就是高度为h的树一颗子树高度为h-1另一颗为h-2因此这颗树的节点数 n h n h − 1 n h − 2 1 n_hn_{h-1}n{h-2}1 nhnh−1nh−21左子树右子树根
考虑初始情况高度为012最少节点也是012按照递推就可以计算出任何高度的节点数下界。 反过来已知n就可以知道h上界 最后算ASL经过一通推导结果就是OlogN 平衡二叉树的删除
第一步是按照二叉排序树删除这一步本身就挺麻烦 先看一个简单的例子熟悉流程
从删去点向上找找到第一个不平衡节点这就是最小不平衡树的根从根开始找个头最高的儿子和孙子其实就是从上往下找到不平衡的传导链条判断4类不平衡情况进行旋转 这一步可以使得不平衡部分的H减小1这样可能会导致树的另一侧过高失衡要二次调整回到1步开始 接下来举一个需要二次平衡的例子下图进行第一次平衡后右子树高度减一导致左子树太高。 跳回到1步
从调整点位开始向上找找到第一个不平衡点即33然后从根节点开始向下找不平衡链条为33-10-20进行翻转即可平衡
有没有可能出现第三次不平衡有可能因为我们这次找到根恰好也是整个树的根因此一步到位假设我们找到的根上面还有东西那么这一层降低高度后还有可能导致另一侧失衡总之是一定要向上找是否失衡 考试中可能出现的最极限的情况是删除的节点同时有左右孩子那么这个时候就有两种删除方案。 后面仍然按照我们的流程来进行调整
但是这其实就有歧义了408不太可能出这种最后提一嘴复杂度同查找OlogN 红黑树
红黑树的定义和性质
虽说AVL的复杂度是logN但是实际上每次找最小不平衡树比较费时间实际消耗时间会有一个常数级别的放大如果要频繁改变结构就比较慢红黑树应运而生。 首先明白红黑树是从BSTAVL一脉相承过来的所以本身也具有BST性质左根右 或者说AVL和红黑树都是BST的改进AVL和红黑树严格来说是并列关系但是性能是要碾压的
红黑树相比于BST来说有两点改变
使用三叉链表结构增加了节点的红黑特性对标AVL的平衡因子但是有所不同
红黑树定义
多出来的两个信息可以为操作带来诸多方便理解一下下面的规律
左根右。这告诉我们红黑树的本质还是BST根叶黑。根节点和叶节点都是黑色的 叶节点并不是我们传统意义上的叶节点而是代表外部NULL失败这三个说法是等同的也就是我们之前判定树计算失败ASL时补上的节点。与叶节点对应的就是内部节点就是有具体意义的节点可以成功的节点。 不红红。不存在相邻的红节点 这是对红节点的限制但是黑节点无所谓可以相邻 黑路同。任意节点不一定只是根节点到任一叶节点的通路上路过的黑节点数量相同 这是对黑节点的限制同理红节点无所谓 一个基本功就是判断红黑树是否符合定义大致思路如下
根叶黑。先看根节点和叶节点不红红。扫一眼看看有没有红节点相邻黑路同。这个就比较复杂了你在看一眼黑色聚集的比较多的地方那些地方极有可能会出现黑色路径过长黑节点太多的问题左根右。这个也容易埋坑你要知道红黑树首先是一颗BST所以如果出题很阴会出在这里。 下面这道题很阴看哪个7好在这种情况一般是出现在前三条都失效的时候此时选择题里估计最多剩俩选项硬着头皮细心对比就行 红黑树性质
性质清单
黑高定义h给定h内部节点下界给定h内部节点上界红节点上界最长路径最多是最短路径的两倍给定n设H为总高度非黑高则高度上界 H ≤ 2 l o g 2 ( n 1 ) H≤2log_2(n1) H≤2log2(n1)
前面铺垫一大堆都是规定通过这些复杂的规定可以产生很多有趣的性质这才是红黑树高效率的开始。
首先从“黑路同”里衍生一个概念
黑高即从这个节点开始走到任意一个叶节点经过的黑节点个数不包括自己 根据黑路同逻辑一个节点的黑高一定是一个具体的值从一个特定节点开始无论是从那条路走黑高都是一致的因此用统一的值描述。 其实我们更深地考虑一下黑路同这个特性很好玩如果不考虑红节点的话纯黑情况下一定是满二叉树黑高就是内部节点的层数因此黑高为h的红黑树内部节点至少是 2 h − 1 2^h-1 2h−1 而红黑树是什么东西呢其实就是在一个满二叉黑树之间尽可能塞入不重复的红节点那么给定黑高为h极限情况下可以塞入 2 h 1 − 2 2^{h1}-2 2h1−2个红节点
这个的计算如下图给定h为黑高算上最顶上的那个×总共可以塞h1层红节点即 2 h 1 − 1 2^{h1}-1 2h1−1个然后你再去掉顶部×这个不能加的节点因此就是-2 其次再论两个性质
根节点到叶节点的极限路径长最多为两倍关系 最短路径为纯黑最长路径为从黑根节点开始红-黑-红-黑实际上路径就是一红一黑插入尽可能多的红节点也就是最短路径的两倍 给定内部节点N则极限高度为2logN1因此查找操作的ASL和AVL一致 红黑树的插入
如何构建一颗红黑树 或者说如何在插入的时候保持红黑特性 这就是本章研究的问题 插入一个节点操作如下
根节点染黑根叶黑非根节点染红能够保证黑路同 可能不平衡1,2条可以保证根叶黑黑路同而找节点的过程也满足BST特性因此唯一可能不满足定义的地方就是红节点连续而且不平衡只可能在非根节点时候发生因此不平衡红节点连续调整要看叔叔黑旋转染色 首先要找到旋转的极大不平衡根节点从下面插入的儿往上上层为父上上层为爷爷其实就对应AVL里面极大不平衡树的根节点对于LLRR型父爷换之后令交换的两个节点反色对于LRRL型把儿换到爷位之后令交换的两个节点爷儿反色父节点不反色 叔红反色判新不用调整结构 反色部分为父叔爷其实就是把上面两层反色判新指把爷当做新节点跳到第1步 下面这个例子是不平衡黑叔LL/RR型先单旋再反色 下面这个例子是不平衡红叔则反色上两层
然后以爷为新节点再判断一轮此时为根染黑 当红黑树逐渐变大你会发现红黑树有一个有趣的特性就是大部分情况下是不需要调整的其实AVL和红黑树的最终目标都是平衡那么AVL其实也差不了太多关键在于AVL需要去向上找最大不平衡根而红黑树的爷就是最大不平衡根寻根效率更高这才是红黑树碾压AVL的本质
下图是一种连锁反应这种连锁反应只可能在不平衡红叔时发生因为爷要当做新节点跳回1会触发连锁反应。 再来看一个LR的例子不平衡黑叔LR旋转反色
先旋转两下然后进行反色注意只反爷儿父不管 红黑树的删除
虽然视频没说但是我脑子里已经有一个大致的思路了因为删除的思路和插入其实一样。
首先按照BST删除思路进行删除 之后必然面对结构破坏的问题就要进行调整我们可以利用一个逆向思维假设自己是在进行插入操作就当他是插入操作导致的结构破坏然后我们用插入的思路来调整结构。
而这个思路的关键在于你要明确儿子节点到底是哪个又或者干脆就利用红黑树定义去修改颜色和位置
到时候凭感觉就行了真考出来咱们就大难临头各自飞我自己也不知道乐 B树
B树基础
B树插入和删除
B树
散列查找
