20220601数据结构绿皮书读书笔记

11 多叉树

11.1 定义

数学定义上的树有着广泛的概念，它是任意顶点的集合以及不同顶点对的集合（叫做边，或者树杈）
计算机应用中我们通常不需要这么免费自由的树，为了强调区别称之为free trees
计算机里的树几乎都是有一个特定的根节点，称之为rooted tree

所以其实依照数学定义来说，只要能记录下所有顶点的信息以及顶点之间的关系就能还原一棵树

即便如此同级顶点之间没有左右顺序，所以称之为无序树

因此我们可以定义有序树：有序树是一种子节点被赋予顺序的有根树（rooted tree)

注意二路有序树和二叉树依然是不一样的，如果一个节点只有一个子节点，在二叉树里在左侧或者右侧是不一样的。但这两种分布在二路有序树中是相同的

有序树可以用链表实现，也可以用三元组数组实现。
链表可以同级节点从左到右串联，然后把每个子树的顶点连起来
节点的第一个指针指向first_child，第二个指向next_sibling

11.2 字典树

拆分成26路树来做字母的搜索，重复部分合并到父节点

11.3 外搜B树

前面的都是数据在内存，这里开始考虑磁盘

多路搜索树

二叉搜索树泛化后就是多路搜索树，任意整数m称之为树的阶,每个节点最多有m个孩子。如果孩子的数量k（k ≤ m），那么这个节点则包含k − 1个key并把所有子树节点分割为k个子集，如果子集为空则子节点为空

多路平衡(搜索)树

Balanced Multiway Trees
B-tree就是B树，有的时候被叫做B-树，垃圾的翻译为啥要把英文的连字符也翻译过来啊啊啊啊

目标是设计多路搜索树来最小化文件读取，因此我们希望让树高尽可能的小。
我们可以强制要求如下：
1，除叶子节点外不存在空的子树(因此key的子集分割能尽可能的高效
2.所有叶子节点必须在同层次(因此搜索次数可以保证在同样的次数内结束)
3.每个非叶子节点至少要持有n个子节点，n为最大值的一半（向上取整）以上

树上操作的整体思想就是多级索引，和你翻目录意思是一样的

B+树是B树的变体，加在了
1.子节点的孩子数量从最多是阶数m/2改为等于m
2.所有数据均出现在叶子节点，非叶子节点保留最小值的指针和值

B*树也是B树的变体，变在了
1.子节点的孩子数量从最少是阶数m/2改成了最少(2/3)m
2.插入的时候如果需要可以在兄弟节点中移动数据, 当两个兄弟节点都满了的时候再分割节点

B+ B* 都可以为了方便在同级节点中串联指针方便访问，国内文章说B+是在叶子节点加指针，B*是在B+的基础上给非叶子加指针，这个定义无从考证，不知道是国内哪个版本教材上说的。待考察

11.4 红黑树

在上一节我们使用线性表存储B树内部的节点，因为一个节点通常相对比较小并且是模拟磁盘操作，所以这样做是ok的。实际上这个结构需要顺序存储在磁盘上
然而一般来说我们可以使用任何有序的数据结构才存储B树中的每一个节点（二叉树节点）
小的二叉搜索树是一个不错的选择，我们需要小心的区分这两种连接
1.B树一个节点内部的连接
2.B树内部节点之间的连接
对于1用红色线连接
对于2用黑色线连接

除了根节点外，直连节点线段的颜色赋予这个节点，根节点无父节点，强行定义为黑色

因为树高一致，所以从根到叶子节点经过的B树节点数量一样，这些赋予黑色
因为前面定义的限制，一个4阶的B树 显然B树节点内部的节点的key一定在[2,4]之间，排除黑色节点，也就还剩下[1,3]

定义：
红黑树是一种二叉搜索树，每个节点有红色或黑色区分：条件如下
black condition 1. 从根到空的子树通过的相同数量节点为黑色
red condition 2. 如果父节点存在并且是黑色，则这个节点是红色

后面再找时间总结限制，国内翻译的一堆衍生性质和限制其实没啥必要，可以理解为推论。核心的限制其实非常少，红黑的定义只是为了方便区分这个二叉树节点实际表示的是B树节点的内部还是B树节点之间的分界点

明天继续图
mark 目前是569页 ，pdf是586页

20220531数据结构绿皮书读书笔记

10 二叉树

10.1 定义

递归定义
二叉树是空的，或者由一个根节点和两个称作左右子树的二叉树构成的

前序中序后序遍历，也称先根中根或后根遍历

10.2 二叉搜索树

我们能否找到一个线性表的实现可以很快的搜搜，同时方便的修改呢？
二叉搜索树是个很好的解决方案，定义如下：
二叉搜索树是满足条件的二叉树，可以为空或者每个节点都有一个key，条件如下：
1.根节点的key比其他任意左子树中的节点大
2.根节点的key比其他任意右子树中的节点小
3.左右子树均是二叉搜索树

关于key的大小，可以延展下离散数学的偏序关系

10.3 构建二叉搜索树

自底向上构建，记录最顶的值，最后串起来

10.4 AVL树

调整子树高度使其平衡的一种二叉搜索树
子树高度相差不超过1

插入和删除时动态调整节点，使其始终满足这个条件，怎么旋转都是细节，如果你编程语言足够扎实，给出算法后应当能准确的实现，即使效率不高也没关系，反正一般情况的开发不需要自己造轮子

10.5 延展树

使旧数据放的远点，新数据更容易被访问到
在AVL的基础上，调整的时候做一些trick

拓展话题，树的布局算法
https://blog.hylstudio.cn/archives/917
https://llimllib.github.io/pymag-trees/

明天继续多路树
mark 目前是520页 ，pdf是538页

20220530数据结构绿皮书读书笔记

9 表格和信息检索

9.1 简介

第七章我们证明过，仅仅使用比较的方式从n个元素中搜索1个元素，不可能小于lgn次的比较次数

事实上我们通常这么做，如果有500个不同的记录，每个的索引分别是0-499，我们可以使用这个索引快速的定位

基于表的不同形状，获取一个记录的动作是不一样的，但是最低可以是O(1)，所需的时间不随着表的增大而增加

9.2 矩形表格

行优先表、列优先表。大部分编译器都使用行优先存储，假如行标是1、2，列标是5、6、7，基于行优先的存储就是15\16\17\25\26\27，基于列优先的存储就是15\25\16\26\17\27

这种存储的定位算法（index function）就是简单的线性函数，ni+j即可。如果从0开始或从1开始就+1或者-1

9.3 其他异形表格

9.3.1 三角表

可以使用额外的一个数组(Access table)记录每行或者每列的offset，其余位置都是0，或者没值

9.3.2 参差不齐锯齿状表格

三角形退化一点就是参差不齐的表格

9.3.3 倒排表

考虑到实际情况，比如电话本，需要同时按姓名、地址、电话查找，在这种情况下就需要倒排表。通过排好序的access table可以很快的定位原始数据，注意，access table里不会含有原始数据，只有下标，就像字典或者其他任何书的目录一样

9.4 表格

新的抽象数据类型
一个table由以下部分组成：
1.索引的集合I
2.基础类型T
3.一个从I到T的函数映射
4.Table读取：评估任意I中index元素的操作
5.Table写入：修改任意I中index元素位置的值

注意区分table和array的概念区别，一个是抽象数据类型，一个是具体实现table或者顺序表的语言特性

9.5 应用，基数排序

radix sort又称桶排
不废话直接上代码
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.0.c
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.1.c
https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/BucketSortBug V1.2.c

9.6 哈希

当table的key不再是一个index的情况下，如何把key和index一一关联？
hash table允许我们把很多不同分布的key映射到我们想要的分布上
哈希函数可以把一个key映射到数组的某个索引上，另外我们需要一些方法来解决映射结果相同，也就是碰撞

1.寻找好的hash函数
便于快速运算，结果有着良好的均匀分布
如果我们事先精确知道key如何分布，那就有可能构造一个足够高效的哈希函数，但实际上不可能。因此通常的方法是把key的一部分信息混合其他的方式来生成均匀分布的函数。注意：这里没有任何随机成分，如果相同的key多次执行hash函数，结果应当是一致的，否则将无法从表中再取出数据

常用套路1：truncation，忽略部分key，举个例子一个8位整数需要映射到1000个位置，直接使用其中3位数字即可，剩余的丢弃。这种方式生成的分布取决于key原始的分布，并不是非常均匀
常用套路2：folding，折叠，举个例子，21296876->212+968+76->1256，折叠通常会比truncation有效
常用套路3：modular，取模，n % x 的结果服从 0 ~ x – 1的分布
这里需要提下概率论与梳理统计hhhh但愿你们还记得，反正我记得的不多了

2.决定如何处理碰撞
常用套路1：线性探测，如果第一个位置不可用，则依照预定义的函数尝试下一个位置
常用套路2：聚簇，把多个碰撞的元素放到同一个位置直接存下来，例如拉链法
常用套路3：再哈希，把结果再过一次hash函数
常用套路4：二次探测，如果第一个位置h不可用，则尝试h+i^2的位置，h+1\h+4+h+9
常用套路5：key独立的增长，基于发生碰撞的key的自身数据决定下一个探测的位置
常用套路6：猴子探测（随机）

一般都会说因为泊松分布，所以loadfactor设置的0.75，但这么说一般能应付面试。如果深挖泊松分布的原理，其实是还挺不好解释的
下面的文章仅供参考
https://zhuanlan.zhihu.com/p/395174872
https://zhuanlan.zhihu.com/p/396019103
https://blog.csdn.net/weixin_43883685/article/details/109809049

9.9 应用：Life模拟

因为Life开局就是稀疏矩阵，大部分概率下也就是稀疏矩阵了，因此可以考虑使用压缩存储的办法进行处理

明天继续二叉树
mark 目前是429页 ，pdf是446页

20220527数据结构绿皮书读书笔记

8 排序

各种排序算法来咯
插入排序、选择排序、希尔排序、快排、堆排

8.1 简介

和搜索一样，排序的主流算法也都是主要基于key的比较

8.2 插入排序

两个不是基于index的基本操作
retrieval by key，通过key查找record
insertion by key，通过key插入record

注意插入并不是唯一的，如果key相同，其中一个可能靠后

第一个操作就是搜索，没什么好说的，可以利用各种已知的搜索操作
第二个操作的关键是找到需要插入的位置，这个位置一定处于有序和无序的界限之前
学习个好的变量命名，position=first_unsorted
对于基于数组实现的列表，需要移动后面所有元素后再插入，对于基于链表实现的列表直接修改指针即可

8.3 选择排序

从所有的中找出极值，放到有序范围内的对应端点位置，每轮仅需要一次插入，移动次数相比插入排序大大降低

8.4 希尔排序

也叫增量递减排序
结合了前两种排序的优点，每轮遍历进行多次比较和交换，当比较的跨度减小到1的那次遍历结束，整个排序算法完成
增量的跨度从最大值开始迭代increment = increment/3 + 1
增量的选择并没有什么人能证明一个好的方式，唯一的限制就是最后要是1（待查证，不知道如今有没有理论突破）

8.5 下界分析

结论，比较次数最少为 lg(n!)向上取整，最坏情况下至少也是lg(n!)
套路还是画比较树，然后计算树的高度，显然和树有关的情况下都是大概率结果都是lg

8.6 分治排序

递归切分，切到最后大小是2分出结果

8.7 链表的归并排序

归并排序在外排中非常有用，在低速磁盘中排序效率比较好
二路归并是练习
多路归并需要用到多叉树

8.8 快排

核心思想，pivot入中位，让pivot找到合适的位置。然后分支左右两侧递归这个过程

8.9 堆排

完全二叉树或者二叉树，因节点位置和2的幂次有固定的公式关系，因此可以通过数组直接存储，通过公式运算还原实际的节点位置
这里注意区分物理实现和逻辑位置的关系，物理上可能是数组的第k个，但逻辑上并不一定是树上的k

满足固定顺序的二叉树，就可以称作堆

下周继续第九章
mark 目前是379页 ，pdf是396页

20220526数据结构绿皮书读书笔记

7 搜索

7.1 简介

记录(record)的一小部分称之为键(key)，我们允许有一个以上的record包含相同的key或没有record包含指定的key

external搜索和internal搜索，区分的是内存的里和外

在链表上搜索并不会有很高的效率，后面默认讨论的是基于数组的实现列表，这个列表应该满足最小要求：
1.每个record都有关联的key
2.key之间可以被相对或绝对的比较
3.record之间可以被比较，或者可以被转成key比较

7.2 顺序搜索

最简单的过程，从开始的元素逐一比较
平均比较次数 (1+2+…+n)/n–>(n+1)/2

7.3 二分搜索

有序数据集上，pivot入中位，看是往前还是往后
容易写错的是，比较完成的中位如果不是要找的，需要丢掉，pivot需要+1或者-1后再继续二分

7.4 比较/搜索/决策树

每个节点代表一次key的比较，节点的值放入被比较key的index，树的树杈连接的代表下次可能的比较位置，树杈上标明条件，叶子节点放置搜索终止状态，失败或者是成功。叶子节点有时也被乘坐终节点或者外部节点，其余节点称作树的内部节点

压缩画法，可以使用二叉树来画出三路比较，叶子节点均为失败，非叶子节点为查找成功

二叉树&完全二叉树，有一堆公式，可以现用现查。但一定要知道什么能算得出来什么算不出来，看高数基础了
吐个槽，感觉玩算法就是拼数学水平，人家数学好的直接知道公式和模板，不知道的我们只能傻乎乎的模拟计算结果

说明下后面为啥可能出现log2(n)，因为比较次数是树的高度，二叉树的高度刚好和n有对数关系，所以会出现很多以2为底的log，一般如果写lg数学上是以10为底的，但这里底数一般是2

二叉搜索比较次数：(2(n+1)/n)*lg(n+1)-3

7.5 下界

1.打磨程序，俗称优化
2.寻找任意搜索算法
能否找到一个再最坏和平均情况下比较次数都少于二分搜索的算法呢？答案是不可能的，数学证明略，总之为了从n个值里搜索1个指定值是存在数学上的下界的
3.通过观察搜索树可以得知
假设T是一个有k个叶子节点的二叉树，那么它的高度h一定满足h ≥ lgk向上取整，external路径长度E(T)满足E(T) ≥ k*lgk h和E(T)的最小值出现在所有叶子节点在同一层或者在两个相邻的层
4.结论
lgn向上取整 + 1
5.其他搜索方式
当基于比较进行搜索的时候，无法快于上述情况，但不是所有的搜索都是基于比较key进行的，举个例子：数组里放着一堆数字刚好是0~n-1，我们知道index=x的情况下可以直接取出index=x的值而不需要搜索。
这种搜索叫做插值搜索，我们假设所有的key都是数字或者就是信息本身，比如单词可以被记录为数字。同时这种方法要求数据均匀分布
当我们想从500页的书中翻到345的时候，你会直接取寻找三分之二的位置，大概就和这个原理类似

7.6 函数的阶、级数、无穷级数

高数概念：函数的阶，函数之间的同阶（极限比为0）、等阶（为非零有穷）、高阶（为无穷）

算这玩意需要求极限，略

直接记结论如下
O(g(n))表示f(n)的阶小于或等于g(n)的阶，极限比为有穷
o(g(n))表示f(n)的阶严格小于g(n)的阶，极限比为0
Theta(g(n))表示f(n)与g(n)的阶相等，极限比为非零且有穷
Omega(g(n))表示f(n)的阶大于或等于g(n)的阶

按我理解通常来说寻找高阶的函数比寻找低阶函数要容易口算，因此描述一个算法的时空复杂度通常会用大O，O(n)表示这个算法的时空复杂度函数f(x)的阶小于或等于f(x)=n

明天继续第8章 排序
mark 目前是317页 ，pdf是334页