R-B Tree、AVL Tree、B Tree

1.R-B Tree

定义：

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

2.AVL Tree

定义：任一节点的左右子树高度之差不超过1。

AVL树是平衡二叉搜索树的鼻祖，它的平衡度也最好，左右高度差可以保证在「-1，0，1」，基于它的平衡性，它的查询时间复杂度可以保证是O（log n）。但每个节点要额外保存一个平衡值，或者说是高度差。

插入新节点的旋转次数是常数级的，不必旋转到根节点。（最后一点存疑）

3.B Tree

一个 m 阶的B树是一个有以下属性的树：

1. 每一个节点最多有 m 个子节点
2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
3. 如果根节点不是叶子节点，那么它至少有两个子节点
4. 有 k 个子节点的非叶子节点拥有 k − 1 个键
5. 所有的叶子节点都在同一层

4.R-B Tree 比 AVL Tree 高效？

这一点，无论在知乎和stackoverflow都有广泛的讨论。有人说两者差不多，有人说后者好，有的觉得AVL在大多数情况比R-B好(比不过的部分差距也不大)。其中有一个观点十分吸引我，就是R-B Tree更高效的原因是三节点的特性(R-B Tree 和2，3，4树可以互相转换，这是其本质)更高性能的利用了缓存，本质上是用空间换取了时间，但是我现在还没办法理解这个观点，保留，以后再回顾。

总的来说，AVL 比 R-B 在平衡度方面AVL树更优秀，所以查找的复杂度要稍稍由于R-B，但是牺牲了一些空间性能就是要维护一个高度差的值。在删除和插入操作方面，由于R-B没有严格定义高度差，在旋转次数树的调整上，旋转次数要少于AVL(存疑，有些人说差不多)。R-B Tree 在调整旋转次数上是常数级的。有观点称AVL树在插入时也是常数级别。

R-B Tree、AVL Tree、B Tree

原文：https://www.cnblogs.com/Royzzzzz/p/12985068.html