[初等算法]--红黑树

红黑树的定义

红黑树是一种自平衡二叉搜索树。通过对节点进行着色和旋转,红黑树可以很容易地保持树的平衡。我们需要在二叉搜索树上增加一个额外的颜色信息。节点可以被涂成红色或黑色。如果一棵二叉搜索树满足下面的全部5条性质,我们称之为红黑树。

• 任一节点要么是红色,要么是黑色。
• 根节点为黑色。
• 所有的叶节点(NIL节点)为黑色。
• 如果一个节点为红色,则它的两个子节点都是黑色。
• 对任一节点,从它出发到所有叶子节点的路径上包含相同数量的黑色节点。 为什么这5条性质能保证红黑树的平衡性呢?因为它们有一个关键的特性:从根节点出发到达叶节点的所有路径中,最长路径不会超过最短路径两倍。注意到第四条性质,它意味着不存在两个连续的红色节点。因此,最短的路径只含有黑色的节点,任何比最短路径长的路径上都分散有一些红色节点。根据性质五,从根节点出发的所有的路径都含有相同数量的黑色节点,这就最终保证了没有任何路径超过最短路径长度的两倍。图3.4的例子展示了一棵红黑树。
  
  红黑树沿用所有二叉搜索树中不改变树结构的操作,包括查找、获取最大、最小值等。只有插入和删除操作是特殊的。
  由于只增加了一个颜色信息,我们可以复用二叉搜索树的节点定义。如下面的C++代码所示:

  enum Color {Red, Black};
  template <class T>
  struct node {
      Color color;
      T key;
      node* left;
      node* right;
      node* parent;
  };