定义

红黑树是一种自平衡二叉搜索树，又叫平衡二叉B树（Symmetric Binary B-tree）

约束

• 节点都是BLACK或者RED
• 根节点是BLACK
• 叶子节点都是BLACK(这里的叶子节点是 null节点都是黑色)
• Red节点的子节点必然是Black.
  a.RED节点父节点都是BLACK
  b.从根节点到叶子节点不能有连续两个RED节点
• 从任意一个节点到叶子节点的所有路径都包含相同数量的BLACK节点数

实例

红黑树.png