RedBlackTree

Red Black Tree

Red Black Tree由Rudolf Bayer发明的,当时被称为平衡二叉B树。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了额外要求:

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 每个叶节点是黑色的
  4. 每个红色节点的两个子节点都是黑色
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长`。

RedBlackTree

Reference :

  1. Wiki 红黑树
  2. Wiki 平衡树