《算法—深入浅出》N叉树的介绍

一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转

一、前言

计算机科班生肯定在大一/大二就学过《数据结构》或类似的这样的书，书里有很多最基础的数据结构与算法，如：

• 排序算法
• 队列与栈
• 二叉树、多叉树；
• 无向图与有向图；

等等......

要想学好，或者弄清楚市面上的各种树：

• 二叉搜索树（BST => Binary Search Tree）
• 平衡二叉树（AVL，这里的 AVL 是由三个人创建，取自他们的名字）
• 红黑树（R-B Tree）
• B 树（B-Tree => Balance-Tree），它不是二叉树，是多叉搜索树（有些人也叫 B- 树）
• B+ 树，它是 B 树的变体
• B* 树，它是 B+ 树的变体

二、二叉搜索树（BST）

特点：

• 所有非叶子结点至多拥有两个儿子（Left和Right）；
• 所有结点存储一个关键字；
• 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如下图：

BST.png

• 它的左子树上的节点的值，都小于根节点的值；
• 它的右子树上的节点的值，都大于根节点的值；
• 至多只有两个儿子节点；

优点：

• 查找方便：
  • 当前节点值 == 查找的值，查找结束，返回；
  • 当前节点值大于查找的值，则进入左子树；
  • 当前节点值小于查找的值，则进入右子树；
• 插入节点、删除节点同查找过程

当树的左右子树高度接近时，查找的时间效率接近 O(n) = logN，基于没有空间开销 O(1)

但是，在极端情况下，B树会退化成一棵线性树：

BST-Line.png

此时，B树的查找、新增、删除时间复杂度都是 O(n) = N

三、平衡二叉树（AVL）

AVL树的性质：

• 完全满足一棵二叉搜索树（BST）所有特性；
• 左右子树高度差小于等于1；

还是拿BST中的图来阐明：

BST.png

• 根节点的左、右子树高度分别为：3 和 2，因此高度相差 1，满足 AVL 第2点；
• 同理，我们也可以发现，其它子树，其左、右子树高度也相差 1；

基于 AVL 的特点，在搜索/查找方面，其时间复杂度 O(n) = logN；

但是，由于严苛的平衡要求，当插入或删除节点时，可能会不满足左右子树高度差，因此需要递归调整，可能引起整棵树的递归 + 旋转操作。

四、红黑树（R-B Tree）

红黑树满足 BST 的特性，它不需要像 AVL 那样，要完全的平衡（左右子树高度差不超过1）。
下图中，列出了满足红黑树的 5 条性质，其中，第5点，是针对 AVL 完全平衡的一个宽松条件。

RBT.png

之后会有一系列专门介绍红黑树，以及如何旋转、插入、删除节点来调整红黑树。

五、多叉搜索树 B 树（ B-Tree ）

B树是 BST 树的一个优化，BST 树只能有最多两棵子树，因此当节点很多时，树的高度就会很高。

大家可能会说，高就高呗，但是效率快！

嗯....确实，但这些都是在内存中操作，当然没有问题；如果是 TB 级数据呢，内存还放的下么？或者数量级更大点？

这时我们可能就需要将数据存到文件中，而文件是在硬盘上，硬盘又有盘片、磁道（柱面）、扇区，硬盘的读写效率取决于数据的连续性（通常一个扇区 128 * 2N次方 字节），如果数据不连续，都是指针控制，那硬盘的磁头需要来回反复切换盘片、磁道（柱面）、扇区，因此，效率就会很低。

B 树以及后面我们会说的 B+ 树，都会应用于数据库中，海量级的数据，都以文件的方式来存储，因此，需要考虑内存、文件、磁盘等因素导致的效率问题。

首先，给出几个概念，B / B+ / B* 都会涉及到：

• M：代表叉数，M = 2 即 二叉，M = 3 即 三叉；
• K：关键字（可以理解为节点的值）；
• P：指针（指向其它节点的指针）；

先来看一下 B 树，如下图（M = 3）：

B.png

好了，概念就这 么多，下面来介绍下 B树 的特性：

1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；

B树 查找：

1. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束；
2. 否则进入查询关键字所属范围的儿子结点；
3. 重复1 / 2，直到所对应的儿子指针为空，或已经是叶子结点；

六、B+ 树

B+ 树与 B- 树基本概念相同，除了：

• 非叶子结点的子树指针与关键字个数相同；
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
• 为所有叶子结点增加一个链指针；
• 所有关键字都在叶子结点出现；

B+ 树如下图（M = 3）：

B+.png

再讲 B+ 树特性，再强调一下：
上图中的非叶子节点，其关键字只是告诉你该去哪里去找真正的数据，仅做查找比较使用，真实数据都在叶子节点中。

B+ 树的特性：

• 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
• 不可能在非叶子结点命中；
• 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
• 更适合文件索引系统；

七、B* 树

B* 树是基于 B+ 树再次升级，特点是：在B+树的非根和非叶子结点再增加指向兄弟的指针。

B*.png

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

所以，B* 树分配新结点的概率比 B+ 树要低，空间使用率更高；

八、总结

• 二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
• B（B-）树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
• B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
• B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；