一、《算法—深入浅出》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树 的特性：
- 定义任意非叶子结点最多只有M个儿子；且M>2；
- 根结点的儿子数为[2, M]；
- 除根结点以外的非叶子结点的儿子数为[M/2, M]；
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
- 非叶子结点的关键字个数=指向儿子的指针个数-1；
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
- 所有叶子结点位于同一层；
B树 查找：
- B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束；
- 否则进入查询关键字所属范围的儿子结点；
- 重复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；
网友评论