《算法导论（原书第3版）》读书笔记

第五部分 高级数据结构-读书笔记
第十八章 B树
B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树，它在降低磁盘 IO 操作回数方面要更好一些，许多数据库系统使用 B树 或者 B树的变种来存储信息。

B树与红黑树不同点在于：

B树的结点可以有很多孩子，从数个到数千个。也就是说一个B树的“分支因子”可以相当大，尽管它通常依赖于所使用的磁盘单元特性。
因为分子因子大，所以树的高度比红黑树小很多，B树的高度为 O(logtn)O(logtn)，t 为分支因子数。
下面来看一棵简单的B树：如果 B树的一个内部结点 x 包含 x.n 个关键字，那么结点 x 就有 x.n+1 个孩子。结点 x 中的关键字就是分隔点，它把结点 x 中所处理的关键字的属性分隔为 x.n+1 个子域，每个子域都当 x 的一个孩子处理。

对存储在磁盘上的一树大的B树，通常看到分支因子在 50~2000 之间，具体取决于“一个关键字相对于一页的大小”（因为磁盘会一次读/写一个或多个页面“磁盘页面”内容，所以最理想的状况是把一个 key 对应的页面内容，都读进来）。一个大的分支因子可以大大降低树的高度，以及查找任何一个关键字所需要的磁盘存取次数。例如一树分支因子为 1001、高度为 2 的B树，它可以存储超过 10 亿个关键字。不过，由于根结点可以持久地保存在主存中，所以在这棵树中查找某个关键字至多只需要两次磁盘存取。

对于B树，在读取\修改结点时，都要读取\修改孩子结点的内容，所以读取一个页面内容就相当于读取一个孩子结点的内容，可能只需要一次。如果把这这些内容以“二叉树的方式”进行存储的话，假设读取/存储一个结点都要进行读/写磁盘的话，这样读/写磁盘的次数就会增加，效率变差。
那如果以“二叉树的方式”进行存储的时候，不一个结点读写一次，多个结点读写一次呢？这样读/写磁盘的次数就会减少，但树的高度就会增加到很大。可能在读/写磁盘时，以页的方式操作比较多，所以二叉树的结点不太适合。

18.1 B树的定义
一棵 B树 T 是具有以下性质的有根树（根为 T.root）：

每个结点 x 是具有下面属性：
x.n 存储结点 x 中关键字的个数
x.n 个关键字本身 x.key1,x.key2...x.keyx.nx.key1,x.key2...x.keyx.n，以非降序存放，使得 x.key1<=x.key2<=...<=x.keyx.nx.key1<=x.key2<=...<=x.keyx.n
x.leaf 是一个布尔值，如果 x 是叶结点，而为 true；如果为内部结点，而为 false
每个内部结点 x 包含 x.n+1 个指向孩子的指针 x.c1,x.c2...x.cx.n+1x.c1,x.c2...x.cx.n+1。叶子结点没有孩子，所以他们没有 x.c 属性。
如果 ki 是存储在以 x.ci 中关键字，那么 k1<=x.key1<=k2<=x.key2...<=x.keyx.n<=kx.n+1k1<=x.key1<=k2<=x.key2...<=x.keyx.n<=kx.n+1。也就是说，孩子结点的 key 小于父结点左边的 key，大于父结点右边的 key。
每个叶子结点有相同的深度，即树的高度 h
每个结点所包含的关键字个数有上界和下界，用一个被称为 B树的最小度数(minmum degree)的因字整数 t>=2 来表示这些界。：
除了根结点以外，每个结点必须至少有 t-1 个关键字。因此，除了根结点以外的每个内部结点至少有 t 个孩子。如果树非空，根结点至少有一个关键字。
每个结点至多可包含 2t-1 个关键字。因此，一个内部结点至多可有 2t 个孩子。当一个结点恰好有 2t-1 个关键字时，称该结点是满的(full)。t=2 时，B树是最简单的。
18.2 B树上的基本操作
在说基本操作之前，有下面两个约定：

B树的根结点始终在主内存中，这样需对根做 DISK-READ 操作；然而，当根结点被改变后，需要对根结点做一次 DISK_WRITE 操作。
任何被当做参数的结点在被传递之前，都要对他们先做一次 DISK-READ 操作。
搜索B树
搜索B树和搜索二叉搜索树很相似，只不过B树是多路分支选择。搜索的主要思想：和结点中的每个 key 进行比较，在 x小于等于key 或 key的下标越界 时停下来。停下来后，看看找没找到，或者还能否继续找。如果能继续找，就再对 小于key 的孩子结点继续找；如果不能继续找，就返回空。具体如下：

和结点中的每个 key 进行比较，在 x小于等于key 或 key的下标越界 时停下来
停下来后，如果 key 的下标没有越界 并且 key和要找的值相等，就返回
停下来后，如果 x 是叶子结点的话，说明无法继续向下找了，就返回空
如果上面都不符合的话，就对小于 key 的孩子结点继续找

（上图中亮的部分，就是被查找过的部分）
创建一棵空树

向B树中插入一个关键字
插入关键后可能B树就不是一棵合法的B树了，所以插入时要注意一下。注意的点就是：
如果要插入的结点已满，就需要把要插入的结点进行分裂

分裂的方法是：将一个满的结点y(有2t-1个关键字)按其中间关键字y.keyty.keyt，分裂为两个各含 t-1 个关键字的结点。中间关键结点被提升到 y 的父结点。如果父结点也是满的，就必须在新的关键字之前，将其分裂，最终满结点的分裂会沿着树向上传播。

这个过程中，CPU时间为 Θ(t)Θ(t)，是由 56 和 89 行做的（去掉了变量2）。过程执行了 O(1) 次磁盘操作（3次的磁盘操作可以看成常数时间，所以是O(1)）

注意点：

i 是指 x 结点的第 i 个孩子
y 是 x.ci 孩子结点，把这个结点的一半（具体来说是后一半）给 z 结点
y 结点是满的，所以有 2t-1 个关键字，和 2t 个孩子，t 是所有关键字中的中间那个关键字。所以 4~9 进行赋值时候，都是 +t 。
以沿树单程下行方式向B树插入关键字
在一棵高度为 h 的B树 T 中，以以沿树单程下行方式插入关键字 k 的操作需要 O(h) 次磁盘存取（每取一个结点，就要读一次，所以最多是 h 次读取，还可能比 h 多，因为还有存储）。所需要的 CPU 时间为 O(th)=O(tlogtn)O(th)=O(tlogtn)。

为了处理“如果父结点也是满的，就必须在新的关键字之前，将其分裂，最终满结点的分裂会沿着树向上传播”的情况，每遇到满的结点，就进行分裂。
注意点：

else 部分是处理 x 结点是“非叶子结点（即内部结点）”时的处理。如果 x 是非叶子结点，就找到合适的叶子结点，插入到叶子结点中去，也就是 if x.leaf 部分。
15行，是因为分裂后，当前结点的关键字又加了1（新加的关键在 i 处，i+1是原来的 i 的关键字），所以要判断一下。
这个程序看来是，必须把新的关键字保存到“叶子结点”上，不知道为什么要这样做。

18.3 从B树上删除关键字
要比插入复杂一点，省略

B树是自平衡的
B树是一种自平衡树，那它是如何做到的呢？
看了 这篇文章 中的插入过程，应该就会知道了。B树在增加层数时，都是把根结点进行分裂，分裂成一个新的根结点和两个孩子结点。这样就不会影响根结点下面的结点的层次了。

补充：B树变种
参考：从B树、B+树、B*树谈到R 树

B+树
B+树和B树的异同点在于：

有n棵子树的结点中含有n-1 个关键字； (此处颇有争议，B+树到底是与B 树n棵子树有n-1个关键字 保持一致，还是不一致：B树n棵子树的结点中含有n个关键字，待后续查证。暂先提供两个参考链接：①wikipedia http://en.wikipedia.org/wiki/B%2B_tree#Overview；②http://hedengcheng.com/?p=525。而下面B+树的图尚未最终确定是否有问题，请读者注意)
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？
1，B+tree的内部结点并没有指向关键字具体信息的指针，因此其内部结点相对 B 树更小。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘块。而B+ 树内部结点只需要1个盘块。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2，B+tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3，B+树方便扫库

B+树还有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。

比如要查 5-10之间的，B+树一把到5这个标记，再一把到10，然后串起来就行了，B树就非常麻烦。B树的好处，就是成功查询特别有利，因为树的高度总体要比B+树矮。不成功的情况下，B树也比B+树稍稍占一点点便宜。B树比如你的例子中查，17的话，一把就得到结果了，有很多基于频率的搜索是选用B树，越频繁query的结点越往根上走，前提是需要对query做统计，而且要对key做一些变化。另外B树也好B+树也好，根或者上面几层因为被反复query，所以这几块基本都在内存中，不会出现读磁盘IO，一般已启动的时候，就会主动换入内存。–走进搜索引擎的作者梁斌

B*树
和B+树相似，在非叶子结点上，多了一个指向兄弟结点的指针。

特点是，B*树分配新结点的概率比B+树要低，空间使用率更高，因为：

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

B树、B+树、B树 特点总结
B树：有序数组+平衡多叉树；数据存在于非叶子节点上。
B+树：有序数组链表+平衡多叉树；数据只存在于叶子上。
B树：一棵丰满的B+树（多了指向兄弟结点的指针）。
关于R树
R树用于地图搜索，请参看上面的参考文章内容

第十九章 斐波那契堆
斐波那契堆有两种用途：

支持一系列操作，这些操作构成了所谓的“可合并堆”
一些操作可以在常数摊还时间内完成，这使得这种数据结构非常适合于需要频繁调用这些操作的应用
操作的时间复杂度如下：

如果没有 UNION 操作的话，就像使用二项堆。但如果要支持 UNION 操作，二项堆的性能就很差。通过把两个包含要被合并的二项堆的数据进行连接（可能是放到一个大数组里），然后运行 BUILD-MIN-HEAP 的方式来实现 UNION 操作，最坏情形需要 Θ(n)Θ(n) 时间。

理论上的斐波那契堆
从理论角度来看，当 EXTRACT-MIN 和 DELETE 数目相比其它操作小得多的时候，斐波那契堆尤其适用。例如，

一些图问题算法可能每条边调用一次 DECREASE-KEY。对于有很多边的稠密图，每次调用 DECREASE-KEY 需要 Θ(1)Θ(1) 摊还时间，相比二项堆的最坏情况 Θ(n)Θ(n) 是很大的进步。
一些问题（计算最小生成树 和 寻找单源最短路径）的快速算法必不可少地要用到斐波那契堆。
实际上的斐波那契堆
除了某些需要管理大量数据的应用外，对于大多数应用，斐波那契堆的常数因子和编程复杂度使得它比起普通二项（或 k 项）堆并不那么适用。因此，对斐波那契堆研究主要出于理论兴趣。如果能开发出一个简单得多的数据结构，而且它的摊还时间界比斐波那契堆相同，那么它将非常实用。

二项堆和斐波那契堆对于 SERACH 操作的支持均比较低效，可能需要花费一段时间才能找到具有给定关键字的元素。

19.1 斐波那契堆结构
一个斐波那契堆是一系列最有最小堆（min-heap ordered）的有根树的集合。也就是说，每棵树均遵循最小堆性质：每个结点的关键字大于或等于它的父结点的关键字
数据结构内容如下：

关键字(键值)
度数：堆节点拥有的孩子数(注意，不包括孩子的孩子)
左兄弟（指针）
右兄弟（指针）
第一个孩子节点（指针）
父节点（指针）
mark：结点 x 自从上一次成为另一个结点的孩子后，是否失去过孩子。新生产的结点是未被标记的，并且当结点 x 成为另一个结点的孩子后，它便成为未被标记结点。
在数据结构中，使用了环形双向链表，有两个优点：

可以在 O(1) 时间内从一个环形双向链表的任何位置插入一个结点或删除一个结点
给定两个这种链表，可以用 O(1) 时间把它们链接在成一个环形双向链表。
其它，H.min 指向具有最小关键字的树的根结点。D(n) 表示在一个 n 个结点的斐波那契堆中任何结点的最大度数，那么 D(n) <= ceiling(lgn)（也就是说，结点的孩子数 <= 树的层高）。

19.2 可合并堆
斐波那契堆上的一些“可合并堆”操作要尽可能长地延后执行，不同的操作可以进行性能平衡。

创建一个新的斐波那契堆
MAKE-FIB-HEAP 返回一个斐波那契堆对象 H，H.n=0 并且 H.min =nil，H 中不存在树。

插入一个结点
假设 x.key 已经被赋值。

寻找最小结点
可以通过 H.min 得到

两个斐波那契堆的合并
简单地将 H1 和 H2 的根链表链接，然后确定新的最小结点。

抽取最小结点
在抽取最小结点时，有一个“合并（consolidate）”操作。做这个操作时，要针对一个性质做操作，就是：根结点的度不能一样，一样的话就要合并。例如上面的图中，3 的度为 3（因为有18，53，38等 3 个结点），17 的度为 1，24 的度为 2，这些根结点的度都不一样（度为0的根结点不考虑）。

如果在合并时候，出现了度一样的根结点，就要合并度一样的根结点。合并的方法是，把根结点小的树 A，当做另一棵树 B 的子树。当树B已经有多个孩子时，就按孩子结点的 key 值，进行排序，最小的放到最左边。

这个文章上的图非常容易明白：斐波那契堆(Fibonacci heap)原理详解(附java代码实现)

减小结点值 和 删除结点
参考：斐波那契堆(一)之 图文解析 和 C语言的实现

总结
1，斐波那契堆不像二项堆，二项堆只有一棵树，所以上层的元素一定比下层元素大。而斐波那契堆有多棵树，所以每棵树的上层的元素，不一定比其它树下层的元素大，那它是如何取得最小的呢？
在取走最小元素后，把最小元素那棵树的孩子都放到根链表里，这样就可以在根链表中取得最小元素了。

2，合并的作用是什么呢？
减少子树的数量，这样在取得最小元素时候的时间复杂度就小。

3，为什么没有搜索方法
因为斐波那契堆的作用是“优先级队列”，不需要使用搜索功能。所以，替换值的方法，是需要把要被替换的元素的指针传进来的，是无法搜索的。

4，如何把结点插入到孩子结点的链表中？
是无法直接插入到孩子结点的链表，只能插入到根结点的链表中。每取走最小结点后，会对堆进行合并，来减少根结点链表中的数量。

第二十章 van Emde Boas 树
使用条件：用在优先及队列，关键子必须是 0 ~ n-1 的数，而且不能重复。（和计数排序的条件有点像）

时间复杂度是：O(lg(lgn))

在排序中，比较排序的下界是 Ω(nlgn)Ω(nlgn)。因为至少有一个操作是Ω(lgn)Ω(lgn)的时间，这是为什么呢？因为中如果 INSERT 和 EXTRACT-MIN 操作需要 o(lgn)时间，可以通过先执行 n 次 INSERT 操作，再接着执行 n 次 EXTRACT-MIN 操作来实现 o(nlgn) 时间内对 n 个关键字的排序。

下面说一下 van Emde Boas 树 的演变过程：

20.1 基本方法
直接寻址
就是声明一个数组来存储 u 位数。如果有值，数组那位就是 1，否则是 0。
下面说一下各种方法的时间复杂度：

INSERT、DELETE、MEMBER：O(1)
MINIMUM、MAXIMUN、SUCCESSOR、PREDECESSOR：最坏是Θ(u)Θ(u)
叠加二叉对结构
结构图如下，就是一个二叉树，不同点是：如果子结点有一个是 1，那么内部结点就是 1。

查找集合中的最小值，从树根开始，依次指向叶结点，总是走到最左边包含1的结点。
查找集合中的最大值，从树根开始，依次指向叶结点，总是走到最右边包含1的结点。
查找x的后继，从x所在的叶结点开始，向上指向树根，直到从左侧进入一个结点，其右孩子结点z为1,。然后从结点z出发依次指向叶结点，始终走最左边包含1的结点。
查找x的后驱，从x所在的叶结点开始，向上指向树根，直到从右侧进入一个结点，其左孩子结点z为1,。然后从结点z出发，依次指向叶结点，始终走最右边包含1的结点。
插入一个值，从该叶结点到根的简单路径上每个结点都置为1。
删除一个值，从该叶结点出发到根，重新计算这个简单路径上每个内部结点的位值，该值为其两个孩子的逻辑或。
这种方法比红黑树好一点。MEMBER 操作时间只有 O(1)，而红黑树需要花 O(lgn)。另外，如果存储的元素个数 n 比全域大小 u 小得多，那么对于其它操作，红黑树要快些。

叠加的一棵高度恒定的树
假设全域大小为 u，我们在根结点 和 所有的叶子结点中间，加一层个数为 u−−√u 的内部结点。每个内部结点的叶子结点个数也是 u−−√u。

查找最大(最小)值，在summary数组中查找最左(最右)包含1的项。
查找x的后驱(前驱)，先在x的簇中向右(左)查找。如果发现1，则返回这个位置作为结构；否则，令i=x/√u，然后从下标i开始在summary数组中向右(左)查找。
删除值x，设i=x/√u。将A[x]置为0，然后置summary[i]为第i个簇中所有位的逻辑或。
上述的每个操作，花费时间为 O(u−−√)O(u)。看起来并没有取得好的效果，叠加二叉树时间为 O(lgu)，其泊近时间快于“叠加高度恒定树”的 O(u−−√)O(u)。但度为 u−−√u 的树是产生 van Emde Boas 树的关键思想。

20.2 1 原型 van Emde Boas 结构
和“叠加高度恒定树”相比，就是每个结点都是一个类型似于“叠加高度恒定树”。
时间复杂度接近：O(lg(lgn))，因为很多地方需要递归，所以时间复杂度还不是 O(lg(lgn))。
程序中一些函数没有说明，内容如下：

high(x) =x / √u
low(x) =x mod √u
index(x,y) =x√u ＋ y

20.3.1 van Emde Boas 树
van Emde Boas 树 是在上面的 proto-vEB 树基础上修改过来的。不同在于：增加了 min 和 max 属性。

min：存储 vEB 树中最小的元素
max：存储 vEB 树中最大的元素
min 和 max 属性是减少 vEB 树上这些操作的递归调用次数的关键。这两个属性有4方面作用：

MINIMUX 和 MAXIMUM 操作甚至不需要递归，因为可以直接返回 min 和 max 的值。
SUCCESSOR 操作可以避免一个用于判断值 x 的后继是否位于 high(x) 中的递归调用。这是因为 x 的后续位于 x 簇中，当且仅当 x 严格小于 x 簇 的 max。对于 PREDECESSOR 和 min 情况，可以对照得到。
通过 min 和 max 的值，可以在常数时间内告知一棵 vEB 树是否为空、仅含一个元素或两个以上的元素。这种能力在 INSERT 和 DELETE 操作中发挥作用。如果 min 和 max 都为 NIL，那么 vEB 树为空。如果 min 和 max 不为NIL，但彼此相等，那么 vEB 树仅含一个元素。如果 min 和 max 都不为 NIL 且不等，那么 vEB 树包含两个或两个以上元素。
如果一棵 vEB 树为空，那么可以仅更新他的 min 和 max 值来实现插入一个元素。因此，可以在常数时间内向一棵空 vEB 树中插入元素。类似地，如果一棵 vEB 树仅含一个元素，也可以仅更新 min 和 max 值，在常数时间内删除这个元素。这些性质可以缩减递归调用链。