红黑树（Red Black Tree）也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树（Symmetric Binary B-tree）；

红黑树的特点

红黑树必须满足以下5条性质

  • 节点是 RED 或者 BLACK ；
  • 根节点是 BLACK；
  • 叶子节点（外部节点，空节点）都是 BLACK；
  • RED 节点的子节点都是 BLACK；
    • RED 节点的parent都是 BLACK；
    • 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
  • 从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点

image.png

红黑树的等价性

红黑树和4阶B树（2-3-4树）具有等价性；
BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点；
红黑树的 BLACK 节点个数与4阶B树的节点总个数相等（红黑树 BLACK 节点 = B树总节点）；
image.png
image.png
注：如果上图最底层的 BLACK 节点是不存在的，则整棵B树只有1个节点，而且是超级节点；