概述

  • 从根节点到叶子的最长的可能路径不多于最短的可能路径的两倍长。

  • 本质应该是二三树

    性质

  • 每个节点要么是红色，要么是黑色。

  • 根节点是黑色。
  • 每个叶节点（NIL节点、空节点）是黑色的。
  • 不能有两个相邻接的红色节点。
  • 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

特点

  • 每个节点需要一个布尔值的额外空间，标识当前节点是红色还是黑色。（相较于平衡二叉树需要一个数值有了巨大的进步）
  • 对于平衡的容忍度，比平衡二叉树稍高，最长路径可以为最短路径的两倍，也就意味着增删的旋转操作会少一些。