完全二叉树 平衡二叉树 二叉查找树 B树 B+树

1. 3分钟理解完全二叉树、平衡二叉树、二叉查找树

完全二叉树： 叶子节点只能分布在树的倒数第1层和倒数第二层，倒数第二层的节点必须是满的，倒数第一层的节点可以不全是满的，但是所有的节点都只能集中在树的左侧。这也说明，倒数第二层的节点肯定不会出现只有右子树，没有左子树的情况。在构建完全二叉树时，插入节点一定先插入左子树，再插入右子树。

满二叉树： 除了叶子节点，每个节点都必须同时拥有左子树和右子树

完全二叉树与满二叉树的区别

当我们用数组实现一个完全二叉树时，叶子节点可以按从上到下、从左到右的顺序依次添加到数组中，然后知道一个节点的位置，就可以轻松地算出它的父节点、孩子节点的位置。以上面图中完全二叉树为例，标号为 2 的节点，它在数组中的位置也是 2，它的父节点就是 (k/2 = 1)，它的孩子节点分别是 (2k=4) 和 (2k+1=5)，别的节点也是类似。

完全二叉树的特点是：“叶子节点的位置比较规律”。因此在对数据进行排序或者查找时可以用到它，比如堆排序就使用了它.

二叉树的提出其实主要就是为了提高查找效率，比如我们常用的 HashMap（每个元素为<key, value>，通过key的值计算存储位置） 在处理哈希冲突严重时，拉链过长（为了解决冲突，哈希数组内存储链表头结点，若冲突数过多，会导致链表长度过长）导致查找效率降低，就引入了红黑树（与2-3树比较类似，但是给节点加入了颜色属性，在插入的过程中通过颜色变换和节点旋转调平衡）。

二叉查找树（又叫二叉排序树、二叉搜索树），它是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（说明二叉搜索树可以没有左子树，只有右子树）
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉搜索树。（这里还需要注意跨层比较的问题。二叉搜索树的左右子树里，左子树上的所有节点应该小于根节点，右子树上的所有节点应该大于根节点。）

注意：二叉查找树也可以是空树。此外，二叉查找树可以只有左子树或者只有右子树。

因此，二叉排序树的中序遍历一定是从小到大的。

在最好的情况下，二叉排序树的查找效率比较高，是 O(logn)，其访问性能近似于折半查找；
但最差时候会是 O(n)，比如插入的元素是有序的，生成的二叉排序树就是一个链表，这种情况下，需要遍历全部元素才行（见下图 b）。

二叉排序树，不同的插入操作会造成不同的查找性能

为了避免构建二叉排序树时，形成链表的情况。引入了平衡二叉树。平衡二叉树在插入和删除元素的过程中，就通过旋转的方法保证每个节点的左右子树高度差不大于1.

平衡二叉树定义如下：

• 平衡二叉树要么是一棵空树
• 要么保证左右子树的高度之差不大于 1
• 子树也必须是一颗平衡二叉树

平衡二叉树内，根节点与其左子树、右子树上节点的值的大小没有限制。

平衡二叉树在添加和删除时需要进行旋转保持整个树的平衡，内部做了这么复杂的工作后，我们在使用它时，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。

2. 重温数据结构：理解 B 树、B+ 树特点及使用场景 ----掘金 // 漫画：什么是B-树？

B树：即B-树，又名平衡多路查找树。

1) B树与平衡二叉树的不同点有：

• 平衡二叉树节点最多有两个子树，而 ，M 阶 B 树表示该树每个节点最多有 M 个子树
• 平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而 B 树每个中间节点有 k-1 个关键字（可以理解为数据）和 k 个子树（ k 介于 M/2 和 M 之间，M/2 向上取整）
• ，并且叶子节点只有关键字，指向孩子的指针为 null

2) B树与平衡二叉树的相同点有：

• B 树的节点数据大小也是按照左小右大，子树与节点的大小比较决定了子树指针所处位置。

3) 一棵 B 树必须满足以下条件：

• 根结点至少有两个子女。
• 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
• 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
• 所有的叶子结点都位于同一层。
• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B树在插入和删除元素时，需要严格按照定义进行，必要时可以拆分节点/旋转以保证平衡。

平衡二叉树与B树对比图。可以看到，B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度。

因为 B 树的子树大小排序规则，因此在 B 树中查找数据时，一般需要这样：
(1). 从根节点开始，如果查找的数据比根节点小，就去左子树找，否则去右子树
(2). 和子树的多个关键字进行比较，找到它所处的范围，然后去范围对应的子树中继续查找
(3). 以此循环，直到找到或者到叶子节点还没找到为止

B+树

一个m阶的B+树具有如下几个特征：

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。（无论插入/删除多少元素，最大元素值都要出现在根节点中）

B+树示例

B+树的所有非叶子节点，都只是提供 子树最大值 与 根节点到叶子节点的索引，不存储实际的数据，而B-树的所有非叶子节点，都存储了子树的索引和真实数据。因此，B+树相对B-树来说更加矮胖。此外，相同大小的磁盘页，可以存储更多的B+树节点，查询时可以减少B+树的查询次数。

B+树与B-树的查询性能对比：

1. 单元素查询
   @ B+树相比B-树，磁盘IO次数更少
   @ B+树一直会查询到叶子节点才停止查询；而B-树查找到对应元素立刻停止查询，除非无对应元素才会查找到叶子节点。相对来说，B+树的查找更加稳定。
2. 范围查询
   B-树依靠中序遍历来进行范围查询（由于B-树的特性，其中序遍历一定是递增序列），需要从叶子节点向根节点层层遍历；而B+树所有的数据都存储在叶子节点，而且通过链表连接起来，因此只需查找叶子节点即可得到一个范围的数据。

综上所述，B+树相对于B树来说优势在于：
(1). 单一节点存储更多的元素，使得查询的IO次数更少
(2). 所有查询都要查找到叶子节点，查询性能稳定
(3). 所有叶子节点形成有序链表，便于范围查询

B树和B+树的应用场景：
1). B树主要应用于文件系统及部分数据库索引，如著名的非关系型数据库MongoDB
2). 大部分关系型数据库如mySQL，都使用B+树作为索引

若不考虑磁盘IO的读取时间，m阶B树的时间复杂度为O(log (m^n))

红黑树

红黑树的原理比较复杂，先记住红黑树的查找，插入和删除时间复杂度都可达到 O(log2^n)

红黑树通过下列性质来维持自平衡：

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是NIL节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。