随想录（用好红黑树）

    红黑树作为一种特殊类型的二叉树，在软件中有很多的用处。但是在网络上面，讲解红黑树的文章和博客很多，可是真正找一份可以信赖的、方便使用的红黑树代码却不多。本篇文章的目的就是介绍如何正确使用红黑树的代码。

    本篇文章的红黑树代码主要来自linux kernel 2.6.7，其中实现文件保存在ib/rbtree.c，而头文件保存在include/linux/rbtree.h。当前的linux代码已经升级到3.0以上了，但是关于红黑树的代码内容却没有什么大的改变，这说明关于红黑树的代码是非常稳定的。

（1）红黑树的来源

    a）双向链表是二叉树的最初来源，虽然二叉树也可以做到基本有序，但是查找起来十分麻烦

    b）在双向链表的基础上，人们发明了二叉树，二叉树保证了数据可以像数组一样快速完成二分查找，极大地提高了查找效率

    c）二叉树存在各个数据查找效率不一致的情况，为了做到数据查找效率一致，人们设计了二叉平衡树，左子树和右子树的高度绝对值之差要小于1

    d）为了减少子树旋转的次数，人们设计了红黑树，进一步提高了数据插入和删除的效率

（2）红黑树的概念

    a）红黑树的每个节点必须是红色或者是黑色

    b）根节点到叶节点之间的路径不存在连续的红色节点

    c）根节点到叶节点之间的黑色节点数相同

（3）红黑树的基本结构定义

#ifndef _RBTREE_H
#define _RBTREE_H

#include <stdio.h>

struct rb_node
{
  struct rb_node *rb_parent;
  int rb_color;
#define RB_RED    0
#define RB_BLACK  1
  struct rb_node *rb_right;
  struct rb_node *rb_left;
};

struct rb_root
{
  struct rb_node *rb_node;
};

#define RB_ROOT { NULL }
#define rb_entry(ptr, type, member)         \
  ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(struct rb_node *);
extern struct rb_node *rb_prev(struct rb_node *);
extern struct rb_node *rb_first(struct rb_root *);

/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
          struct rb_root *root);

static void rb_link_node(struct rb_node * node, struct rb_node * parent,
        struct rb_node ** rb_link)
{
  node->rb_parent = parent;
  node->rb_color = RB_RED;
  node->rb_left = node->rb_right = NULL;

  *rb_link = node;
}

#endif  /* _RBTREE_H */

（4） 红黑树的实现

a） 完成内容

    1、调整插入节点rb_node的颜色

    2、在rb_root中删除指定rb_node

    3、获取首节点

    4、获取上一个节点

    5、获取下一个节点

    6、替换节点

    b）实现源代码

#include "rbtree.h"

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
  struct rb_node *right = node->rb_right;

  if ((node->rb_right = right->rb_left))
    right->rb_left->rb_parent = node;
  right->rb_left = node;

  if ((right->rb_parent = node->rb_parent))
  {
    if (node == node->rb_parent->rb_left)
      node->rb_parent->rb_left = right;
    else
      node->rb_parent->rb_right = right;
  }
  else
    root->rb_node = right;
  node->rb_parent = right;
}

static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
  struct rb_node *left = node->rb_left;

  if ((node->rb_left = left->rb_right))
    left->rb_right->rb_parent = node;
  left->rb_right = node;

  if ((left->rb_parent = node->rb_parent))
  {
    if (node == node->rb_parent->rb_right)
      node->rb_parent->rb_right = left;
    else
      node->rb_parent->rb_left = left;
  }
  else
    root->rb_node = left;
  node->rb_parent = left;
}

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
  struct rb_node *parent, *gparent;

  while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
  {
    gparent = parent->rb_parent;

    if (parent == gparent->rb_left)
    {
      {
        register struct rb_node *uncle = gparent->rb_right;
        if (uncle && uncle->rb_color == RB_RED)
        {
          uncle->rb_color = RB_BLACK;
          parent->rb_color = RB_BLACK;
          gparent->rb_color = RB_RED;
          node = gparent;
          continue;
        }
      }

      if (parent->rb_right == node)
      {
        register struct rb_node *tmp;
        __rb_rotate_left(parent, root);
        tmp = parent;
        parent = node;
        node = tmp;
      }

      parent->rb_color = RB_BLACK;
      gparent->rb_color = RB_RED;
      __rb_rotate_right(gparent, root);
    } else {
      {
        register struct rb_node *uncle = gparent->rb_left;
        if (uncle && uncle->rb_color == RB_RED)
        {
          uncle->rb_color = RB_BLACK;
          parent->rb_color = RB_BLACK;
          gparent->rb_color = RB_RED;
          node = gparent;
          continue;
        }
      }

      if (parent->rb_left == node)
      {
        register struct rb_node *tmp;
        __rb_rotate_right(parent, root);
        tmp = parent;
        parent = node;
        node = tmp;
      }

      parent->rb_color = RB_BLACK;
      gparent->rb_color = RB_RED;
      __rb_rotate_left(gparent, root);
    }
  }

  root->rb_node->rb_color = RB_BLACK;
}

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
           struct rb_root *root)
{
  struct rb_node *other;

  while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
  {
    if (parent->rb_left == node)
    {
      other = parent->rb_right;
      if (other->rb_color == RB_RED)
      {
        other->rb_color = RB_BLACK;
        parent->rb_color = RB_RED;
        __rb_rotate_left(parent, root);
        other = parent->rb_right;
      }
      if ((!other->rb_left ||
           other->rb_left->rb_color == RB_BLACK)
          && (!other->rb_right ||
        other->rb_right->rb_color == RB_BLACK))
      {
        other->rb_color = RB_RED;
        node = parent;
        parent = node->rb_parent;
      }
      else
      {
        if (!other->rb_right ||
            other->rb_right->rb_color == RB_BLACK)
        {
          register struct rb_node *o_left;
          if ((o_left = other->rb_left))
            o_left->rb_color = RB_BLACK;
          other->rb_color = RB_RED;
          __rb_rotate_right(other, root);
          other = parent->rb_right;
        }
        other->rb_color = parent->rb_color;
        parent->rb_color = RB_BLACK;
        if (other->rb_right)
          other->rb_right->rb_color = RB_BLACK;
        __rb_rotate_left(parent, root);
        node = root->rb_node;
        break;
      }
    }
    else
    {
      other = parent->rb_left;
      if (other->rb_color == RB_RED)
      {
        other->rb_color = RB_BLACK;
        parent->rb_color = RB_RED;
        __rb_rotate_right(parent, root);
        other = parent->rb_left;
      }
      if ((!other->rb_left ||
           other->rb_left->rb_color == RB_BLACK)
          && (!other->rb_right ||
        other->rb_right->rb_color == RB_BLACK))
      {
        other->rb_color = RB_RED;
        node = parent;
        parent = node->rb_parent;
      }
      else
      {
        if (!other->rb_left ||
            other->rb_left->rb_color == RB_BLACK)
        {
          register struct rb_node *o_right;
          if ((o_right = other->rb_right))
            o_right->rb_color = RB_BLACK;
          other->rb_color = RB_RED;
          __rb_rotate_left(other, root);
          other = parent->rb_left;
        }
        other->rb_color = parent->rb_color;
        parent->rb_color = RB_BLACK;
        if (other->rb_left)
          other->rb_left->rb_color = RB_BLACK;
        __rb_rotate_right(parent, root);
        node = root->rb_node;
        break;
      }
    }
  }
  if (node)
    node->rb_color = RB_BLACK;
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
  struct rb_node *child, *parent;
  int color;

  if (!node->rb_left)
    child = node->rb_right;
  else if (!node->rb_right)
    child = node->rb_left;
  else
  {
    struct rb_node *old = node, *left;

    node = node->rb_right;
    while ((left = node->rb_left))
      node = left;
    child = node->rb_right;
    parent = node->rb_parent;
    color = node->rb_color;

    if (child)
      child->rb_parent = parent;
    if (parent)
    {
      if (parent->rb_left == node)
        parent->rb_left = child;
      else
        parent->rb_right = child;
    }
    else
      root->rb_node = child;

    if (node->rb_parent == old)
      parent = node;
    node->rb_parent = old->rb_parent;
    node->rb_color = old->rb_color;
    node->rb_right = old->rb_right;
    node->rb_left = old->rb_left;

    if (old->rb_parent)
    {
      if (old->rb_parent->rb_left == old)
        old->rb_parent->rb_left = node;
      else
        old->rb_parent->rb_right = node;
    } else
      root->rb_node = node;

    old->rb_left->rb_parent = node;
    if (old->rb_right)
      old->rb_right->rb_parent = node;
    goto color;
  }

  parent = node->rb_parent;
  color = node->rb_color;

  if (child)
    child->rb_parent = parent;
  if (parent)
  {
    if (parent->rb_left == node)
      parent->rb_left = child;
    else
      parent->rb_right = child;
  }
  else
    root->rb_node = child;

 color:
  if (color == RB_BLACK)
    __rb_erase_color(child, parent, root);
}

/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(struct rb_root *root)
{
  struct rb_node  *n;

  n = root->rb_node;
  if (!n)
    return 0;
  while (n->rb_left)
    n = n->rb_left;
  return n;
}

struct rb_node *rb_next(struct rb_node *node)
{
  /* If we have a right-hand child, go down and then left as far
     as we can. */
  if (node->rb_right) {
    node = node->rb_right; 
    while (node->rb_left)
      node=node->rb_left;
    return node;
  }

  /* No right-hand children.  Everything down and left is
     smaller than us, so any 'next' node must be in the general
     direction of our parent. Go up the tree; any time the
     ancestor is a right-hand child of its parent, keep going
     up. First time it's a left-hand child of its parent, said
     parent is our 'next' node. */
  while (node->rb_parent && node == node->rb_parent->rb_right)
    node = node->rb_parent;

  return node->rb_parent;
}

struct rb_node *rb_prev(struct rb_node *node)
{
  /* If we have a left-hand child, go down and then right as far
     as we can. */
  if (node->rb_left) {
    node = node->rb_left; 
    while (node->rb_right)
      node=node->rb_right;
    return node;
  }

  /* No left-hand children. Go up till we find an ancestor which
     is a right-hand child of its parent */
  while (node->rb_parent && node == node->rb_parent->rb_left)
    node = node->rb_parent;

  return node->rb_parent;
}

void rb_replace_node(struct rb_node *victim, struct rb_node *new,
         struct rb_root *root)
{
  struct rb_node *parent = victim->rb_parent;

  /* Set the surrounding nodes to point to the replacement */
  if (parent) {
    if (victim == parent->rb_left)
      parent->rb_left = new;
    else
      parent->rb_right = new;
  } else {
    root->rb_node = new;
  }
  if (victim->rb_left)
    victim->rb_left->rb_parent = new;
  if (victim->rb_right)
    victim->rb_right->rb_parent = new;

  /* Copy the pointers/colour from the victim to the replacement */
  *new = *victim;
}