二叉树向来都是一个极其重要的数据结构。此外，二叉树还衍生出众多数据结构，如：B树、B+树、红黑树等。本文将根据近期看到的一些讲解，对该专题进行一个归纳。

1. 二叉查找树（BST）

1.1 特点

  • 左子树上所有结点的值均小于或等于它的根结点的值。
  • 右子树上所有结点的值均大于或等于它的根结点的值。
  • 左、右子树也分别为二叉排序树。
    示例如图：

1.2 缺陷

单纯的二叉查找树不包含“调节功能”，这使得在一些极端情况下导致其查询效率大打折扣，甚至退回到线性查找，如图：

该示例虽然满足二叉查找树的特征，但显然其查询效率近似于线性查找。

2. 平衡二叉树

2.1 特点

平衡二叉树实质仍然是一棵二叉查找树。其采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：

  • 非叶子节点只能允许最多两个子节点存在；
  • 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；
  • 树的左右两边的节点层级相差不会大于1。

2.2 层级结构

因为平衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树。使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找；

2.3 小结

  • 非叶子节点最多拥有两个子节点；
  • 非叶子节值大于左边子节点、小于右边子节点；
  • 树的左右两边的层级数相差不会大于1;
  • 没有值相等重复的节点;

3 红黑树

3.1 红黑树特性

红黑树其实质是一棵平衡二叉树。只是红黑树增加了一些特性来保证其平衡性：

  • 结点是红色或黑色。
  • 根结点是黑色。
  • 每个叶子结点都是黑色的空结点（NIL结点）。
  • 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
  • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

P.s：正是由于上述规则的限制，才保证了红黑树的自平衡，并保证了红黑树上从根到叶子最长路径不超过最短路径的2倍。

3.2 红黑树的自平衡

正如之前我们所说，平衡二叉树的核心是：树的左右两边的节点层级相差不会大于1。红黑树作为一棵特殊的平衡二叉树，其在插入/删除节点时容易打破其规则约束，此时需要对树的结构进行一些调整来维护其仍然满足红黑素性质。
红黑树维护自平衡性的方法总结来看有两种：

  • 变色
  • 旋转：
    • 左旋
    • 右旋

由于红黑树的自平衡维护需要根据不同情况具体分析，参考文献：红黑树中对这一过程有具体的说明，此处便不详细展开了。

4. B树

B树和平衡二叉树稍有不同的是，B树属于多叉树又名平衡多路查找树（查找路径不只两个）。B树和B+树被广泛应用于数据库索引技术中。

4.1 B树特性

  • 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
  • 子节点数：**非叶节点的子节点数>1，且<=M **，且M>=2，空树除外（注：M代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
  • 关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()向上取整的函数 如ceil(1.1)结果为2);
  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

4.2 B树查询

其查询过程类似于二分查找

4.3 B树插入

例如：定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来；我们需要遵循以下规则：

  • 节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
  • 排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;

我们首先插入 3、8、31、11：

再插入23、29

再插入50、28

4.4 B树删除

当我们需要删除B树中的节点时，需遵循以下规则：

  • 节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
  • 满足节点本身比左边节点大，比右边节点小的排序规则;
  • 关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

4.5 B树小结

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制在充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;