B树算法解析

主要梳理一下B树的插入和删除的方法和原理。 1. B树简介 又称多路平衡排序树 B树需要满足几个要求 节点的最多子树数量为B树的阶,通常用m表示 对每个节点,子树数量 = 关键字数量 – 1 每个节点至多有 m 棵子树,节点内的排列为 …

全文B树算法解析

二叉树遍历和用遍历结果确定二叉树

1.前序遍历 定义 对任意子树,优先访问根节点,再左子树,再右子树。 遍历 遍历时需使用栈保存根节点,用以未来访问右子树使用。 特征 第一个为整棵树的根 最后访问一定为叶节点。 2.中序遍历 定义:对任意子树,优先访问左子树,再访问根节点,再访问右子树。 遍历:遍历时需要使用栈保存根节点,用以未来访问根节点和右子树使用。 特征 中序遍历结果正好是将整棵树“压扁”之后得到的序列,所以也可以依据中序序列容易地对树进行切割划分。 第一为最左的节点 …

全文二叉树遍历和用遍历结果确定二叉树

数据结构重点-学习笔记

1. 基本概念 数据的逻辑结构 与存储无关的数据逻辑关系,仅对外业务逻辑关心。 如线性结构、一般线性表(有序表)、栈、队列、树、有向图、集合等等 数据的存储结构 计算机中的表示或者映像,也称物理结构,业务逻辑不用关心,实现业务逻辑时才关心。 如顺序存储(和线性、有序区别开)、链式存储、索引存储、散列存储 数据的运算 针对逻辑结构定义的运算 算法特性 有穷、确定、可行 原地工作法 算法需要的额外空间是常量 …

全文数据结构重点-学习笔记

红黑树C语言实现

1. 红黑树理解和推导详见 2. C语言代码 由于加了不少代码用于打印树和增改中的Log,所以整体会略长。 3. 测试运行结果 相关文章 KMP推导与C语言实现 红黑树理解和推导 Centos8中用Podman搭建 WordPress B树算法解析 数据结构重点-学习笔记

红黑树理解和推导

0. 前言 直接背红黑树的算法会比较难(由于情况较多),所以本文尝试用引导思路的方式去聊一聊红黑树,希望能在需要的时候,即使忘记也能将算法完整推导出来。 推导出来的代码和情况划分可能会有一些差异,但只要大思路一致,代码看着不同,执行效率上差异通常不大,这也是没必要强记各种情况的原因之一。 其实个人认为红黑树包含不少有趣的思维模式如递推、奇偶性、对称等等,知道其思想以后有可能也有助于其他问题的理解。 1.为什么要用红黑树 红黑树是二叉搜索树的一种。而二叉搜索树用于解决快速搜索的同时保持较高的改动效率(相对于有序数组)。 二叉搜索树也有很多种,相对来说最直观容易理解的是平衡二叉树,其整棵树或任意子树的左右子树深度差异不超过一。但为了这样的平衡,需要一点点代价:每次增删可能会要求更多的调整次数(具体为旋转)。并且为了提升增删的效率,往往需要为每个节点多记录一个深度值(通常这是小事)。 而红黑树则以牺牲绝对的平衡为代价,只要求其中的黑色节点完全平衡即可,以此换取了一些调整的便捷性空间,以此达到更高效的增删效率。 2.红黑树的要求 红黑树有几条要求(或者叫性质)。第一次看见往往都会一脸懵逼。但我们一条一条分析,就能知道每一条的意义。 (注:个人不把空的叶子结点视作叶子结点,能省一条对叶子结点的要求) 要求1 每个节点要不红黑要不黑色 …

全文红黑树理解和推导

KMP推导与C语言实现

0.说明 由于大部分文章直接从算法入手,即使配合丰富的动图,理解起来也有一些难度。在自己理解和实现后,用推导的思路聊一聊KMP。 当进行子字符串查找时,最简单的方法是尝试将母字符串的每一位依次看作首位,和目标字符串进行逐字符对比。这样非常易懂,但效率偏低。 如果母字符串长度为m,目标字符串长度为n,算法时间复杂度可能达到m*n。在基因工程等(字符集较少,相对容易大段重复,且目标串和母串都非常长)特殊情况下这样的时间复杂度是较难接受的。这时非常需要思考如何进行优化。 1.寻找可跳过的场景 相对容易想到(其实也很难)的一个方向是跳过一些无需重复的检查的场景,那我们先找一找有哪些场景可以跳过。 当我们有 开始,进行逐字符比较,从 对比至 发现不一致了。按最简单的做法,我们需要改变首字符位置重新匹配,如下 周而复始,可以发现迟早我们将对比至 而这个场景和当初场景1时的 是多么的相似啊(都将需要对比abc,且都能匹配上)。如果我们能跳过刚才这里已经对比过的abc。如果能避免重复对比,直接进行 至少能省下对比abc的时间。嗯,虽然看起来优化价值不大,如果能很低成本做,到至少还是稍有价值的(省了三次对比)。 …

全文KMP推导与C语言实现