2013/9/11

红黑树详解

红黑树是一种相当复杂的数据结构,我仔细研究并亲手实现了它,这是一个多月来阅读「算法导论」给我带来成就感最大的一次。

概述

红黑树有以下五条性质:

  1. 节点是红色或者黑色的。
  2. 根节点的黑色的。
  3. nil 节点时黑色的。
  4. 每个红节点的左子节点和右子节点必定是黑色的。
  5. nil 节点在任意位置黑深度都相等。

nil 节点就是空节点,在红黑树的实现中,nil 节点代替二叉树中的 NULL:叶子节点的左节点和右节点指针都指向 nil 节点;只一个子树的节点,其另外一个子节点指针也指向 nil 节点;根节点的父节点也指向 nil 节点。nil节点的父节点和右节点都是自己,左节点为红黑树的根节点。如果红黑树为空(没有根节点),那么nil节点的左节点就也是自己。nil节点的存在大大方便了很多操作。

红黑树

红黑树的这5条性质中,第4和第5条性质保证了红黑树是相对“平衡”的。

  • 第4条保证了:两个红节点不可能直接相连。
  • 第5条保证了:从 nil 节点开始,从上至下沿任意一条道路,再回到 nil 节点,经过的黑节点的数量是一样的。

这样,红黑树中的所有叶子节点到根节点的长度,在最坏情况下也不会大于最好情况下的两倍,所以红黑树就能保持「大致」的平衡。

将黑节点视为框架(骨骼),红节点视为填充物(血肉)。黑节点控制着红黑树的平衡,一棵黑高度是n的红黑树,根节点的左右子树的黑高度就都很整齐地是 n 而不会不一样,这样红黑树就不会失去平衡;红节点使红黑树能够容纳有限程度的不平衡,固定黑高度的子树,能够容纳的节点个数是有限的。

如果一棵子树中已经塞满了红节点,再试图向其中插入节点,就会导致树失去平衡,这是就要进行一些额外的处理(包括旋转根节点,将一棵子树中的节点移到另一棵子树中去)。红黑树的复杂就在于此:如何在插入节点(还有)删除节点后,保证树仍然具有上述五条性质,这其中包含一些精妙的设计。

二叉查找树部分

红黑树在二叉查找树的基础上修改而来。首先看一下节点类 node 的定义:

class node
{
public:
    node (int val): value(val), isRed(true) {};
    node (int val, node *le, node *ri, node *pa): value(val), left(le), 
        right(ri), parent(pa), isRed(true) {};
    int value;
    node *left;
    node *right;
    node *parent;
    bool isRed;
};

节点有四个属性,value 表示节点值,isRed 表示红色还是黑色,leftrightparent指向左子结点、右子结点和父节点,构造函数用来构造节点,节点构造出来默认是红色的。

二叉查找树的特点是,根节点左子树中的节点全部小于根节点,右子树中的节点全部大于根节点。二叉查找树的插入和删除操作都有所体现。红黑树 rbtree 类的定义如下,先看 public 部分

class rbtree
{
public:
    rbtree();
    void insertValue(int val);
    node *searchValue(int val);
    void removeValue(int val);
    void removeNode(node *n);
    void printTree();
private:
    node *nil;
    // 省略
};

rbtree 类提供这样一些函数,插入一个值 insertValue ,查询一个值 searchValue ,删除一个节点 removeNode 或删除一个值 removeValue (即先查询,然后再删除查询到的第一个节点),在控制台输出树 printTree

由于操作红黑树的函数经常用到递归,需要传入当前节点(从 nil 节点开始),所以上述函数都是通过调用 private 函数(调用这些函数是都要传入一个“当前节点”,以方便函数在当前节点的子结点上继续调用自己)来进行完成任务的:

rbtree::rbtree()
{
    // 构造空的红黑树,生成nil节点,其left,right,parent都指向自己
    nil = new node(0);
    nil->isRed = false;
    nil->left = nil->right = nil->parent = nil;
}

构造函数构造一个空的红黑树,只有 nil 节点,nil 节点的左子结点还是 nil 节点自己,如果非空,则是树的根节点。

void rbtree::insertValue(int val)
{
    // 从nil节点开始,插入一个值
    insert(nil, val);
}

insertValue 插入一个数值,它调用 insert 函数并将 nil 传递作为当前节点传入。任何插入操作都会从nil节点开始,沿着红黑树向下搜寻合适的位置。如果是空树,那就直接插在nil->left(根节点)上。

node *rbtree::searchValue(int val)
{
    node *res = search(nil->left, val);
    return (res == nil) ? NULL : res;
}

searchValue 在红黑树中查询一个值,如果查到了,则返回查到的节点,如果没有查到,返回NULL(而不是nil,因为该函数是对外的接口,外面不知道红黑树中有一个 nil 节点这回事)。

void rbtree::removeNode(node *n)
{
    remove(n);
}

删除节点很简单,就是调用私有的 remove 方法。删除节点不需要从 nil 节点开始遍历,直接从待删除的节点开始操作就可以了,所以 remove 方法并不接受一个 「当前节点」参数。

void rbtree::removeValue(int val)
{
    node *tn = search(nil->left, val);
    if (tn == nil)
    {
        return;
    }
    else
    {
        removeNode(tn);
    }
}

删除一个值,就是先根据值查找节点,如果查到了,就删除该节点。

void rbtree::printTree()
{
    // 将红黑树打印出来:如果为空,则显示一条消息;
    // 如果不为空,则打印出来
    if (nil->left == nil)
    {
        cout << "Empty Tree";
    }
    else
    {
        output(nil->left, 1, 0);
    }
    cout << endl;
}

输出红黑树也很简单,先检查是不是空树,如果是,输出一条消息,如果不是,调用私有函数 output() 并传入根节点。

现在看一下上面用到的几个私有函数。先看声明:

class rbtree
{
public:
    // 省略
private:
    node *nil;
    void insert(node *n, int val);
    void remove(node *n);
    node *search(node *n, int val);
    void output(node *n, int level, int blevel);
    // 省略
};

几个方法的实现如下所示:

void rbtree::insert(node *n, int val)
{
    // 在以节点n为根的子树中插入值val,从根部开始查找,
    if (n == nil)   /*从nil开始,说明是一次插入操作的第一次调用*/
    {
        if (nil->left != nil)   /*非空树*/
        {
            insert(nil->left, val);
        }
        else    /*空树*/
        {
            node *tn = new node(val, nil, nil, nil);
            nil->left = tn;
            fixInsert(tn);
        }
    }
    else    /*n为普通节点(而不是nil)*/
    {
        node **pos = (val < n->value) ? &(n->left) : &(n->right);
        if (*pos != nil) /*待插入位置非空,需要在子树中寻找更具体的位置*/
        {
            insert(*pos, val);
        }
        else /*待插入的位置为空,将新节点插入到该位置上*/
        {
            node *tn = new node(val, nil, nil, n);
            *pos = tn;
            fixInsert(tn);
        }
    }
}

插入操作,首先检查传入的当前节点n是不是nil节点:

  1. 如果是,说明是插入操作的第一次调用,传入了nil节点。检查红黑树是不是空树:
    1. 如果是空树,就将其作为根节点,插入在nil->left处。
    2. 如果不是,就在根节点上调用自己。
  2. 如果不是,就说明已经下放到普通节点了,将待插入的值与自己比较,并选择合适的位置(左子树或右子树)。检查这个合适的位置是不是空:
    1. 如果不是空,就在这个子节点上继续调用自己。
    2. 如果是空,就使用这个值构造一个新节点,插入在这个位置上。

你可能注意到,在真正插入一个节点(而不是继续调用自己)后,我们都执行了一个fixInsert(),这是这篇博文的重点之一,稍后再讲。

node *rbtree::search(node *n, int val)
{
    if (n == nil)
    {
        return nil;
    }
    else if (n->value == val)
    {
        return n;
    }
    else
    {
        return (val < n->value) ? search(n->left, val) : search(n->right, val);
    }
}

查询操作相对简单,就是比较查询值和当前节点值是否相等,如果相等,就返回当前节点,否则,就根据查询值与当前值的大小关系,在左子树或右子树中继续查询。

void rbtree::remove(node *n)
{
    // 如果有两个非空子树,就将待删除节点与左子树中最大节点交换值,
    // 然后删除左子树中的那个“最大节点”
    if (n->left != nil && n->right != nil)
    {
        node *target = n->right;
        while (target->left != nil)
        {
            target = target->left;
        }
        switchValue(n, target);
        remove(target);
    }
    else /*至少有一个子树为空*/
    {
        node *c = (n->left == nil) ? n->right : n->left;
        (*getSelfFromParent(n)) = c;
        if (c != nil)
        {
            c->parent = n->parent;
        }
        // 如果删掉的是红节点,什么都不做
        if (n->isRed == true)
        {
            return;
        }
        // 如果删除的节点是黑色,而删除节点的子节点是红色,那就将子节点染黑
        if (c->isRed == true)
        {
            c->isRed = false;
        }
        else
        {
            // 如果删除节点是黑色,删除节点的子节点也是黑色,麻烦来了
            fixRemove(c, c->parent);
        }
    }
}

删除操作,稍微复杂一些。二叉查找树中删除一个节点是这样的。

  1. 如果待删除的节点没有子节点或者只有一个子节点,那就直接将其删除,将子节点(如果有的话)代替自己接在父节点上。
  2. 如果待删除的节点有两个子节点(就是有两个非空子树),那就将该节点和左子树中的最大节点交换节点值,然后将左子树中的最大节点删除(该节点既然是左子树中的最大节点,就不可能有右子结点,所以不会有两个非空子树)。而且,左子树中的最大节点,一定比左子树中的其余所有节点都大(因为它是最大节点),又比右子树中的所有节点都小(它在左子树中),所以让该节点坐在原来待删除节点的位置上,不会破坏二叉查找树的属性。

你可能注意到,在真正删除一个节点后,在某些特定条件下,我们需要进行一些额外的处理,甚至调用 fixRemove() 函数。这是本篇博文的另一个重点,将在后面详细解释。

void rbtree::output(node *n, int level, int blevel)
{
    if (n == nil)
    {
        return;
    }
    int tb = (n->isRed) ? 0 : 1;
    output(n->left, level + 1, blevel + tb);
    for (int i = 1; i < level; i++)
    {
        cout << "   ";
    }
    cout << n->value << ((n->isRed) ? "R" : "");
    if (n->left == nil || n->right == nil)
    {
        cout << "(" << blevel + tb << ")";
    }
    cout << endl;
    output(n->right, level + 1, blevel + tb);
}

输出一个子树,传入的是当前节点,其深度与黑深度。printTree()函数调用该函数。该函数负责控制缩进,体现节点的深度;负责用字符R标记红节点,还负责输出叶子节点的黑深度。如下就是一个简单地五个元素的红黑树的输出。

>> g++ rbtree.cpp
>> ./a.out
   5(2)
      8R(2)
10
      15R(2)
   17(2)
>>

红节点打上了字符R标记,而且所有具有指向nil节点指针的节点的黑深度也输出在括号中(本例中为2)。

旋转

为了进行 fixInsert()fixRemove() ,我们定义旋转操作还有一些其他的辅助函数。先看类中的函数声明:

class rbtree
{
public:
    // 省略
private:
    // 省略
    bool rotateLeft(node *n);
    bool rotateRight(node *n);
    node **getSelfFromParent(node *n);
    node **getSiblingFromParent(node *n);
    void switchColor(node *n1, node *n2);
    void switchValue(node *n1, node *n2);
    bool isLeft(node *n);
    // 省略
};

它们的实现如下所示:

bool rbtree::rotateLeft(node *n)
{
    if (n->right == nil)
    {
        return false;
    }
    else
    {
        node *x = n;
        node *y = n->right;
        node *p = y->left;
        (*getSelfFromParent(x)) = y;
        y->parent = x->parent;
        y->left = x;
        x->parent = y;
        x->right = p;
        if (p != nil)
        {
            p->parent = x;
        }
        return true;
    }
}

rotateLeft 左旋节点n。左旋的示意图如下所示:节点X左旋之后,由X的右子节点Y代替X成为X的父亲的子节点,X成为Y的左子结点,原先Y的左子结点成为了X的右子结点。旋转后,Y占据了X的位置,原先该位置上的左子树和右子树中的节点个数得到了调整,左子树中新加入了X节点,右子树中去除了Y节点,而β子树也离开了右子树,转到左子树中。实际上,红黑树就是通过这种调整来保持本身的大致平衡的。

旋转

bool rbtree::rotateRight(node *n)
{
    if (n->left == nil)
    {
        return false;
    }
    else
    {
        node *y = n;
        node *x = y->left;
        node *p = x->right;
        (*getSelfFromParent(y)) = x;
        x->parent = y->parent;
        x->right = y;
        y->parent = x;
        y->left = p;
        if (p != nil)
        {
            p->parent = y;
        }
        return true;
    }
}

右旋与左旋对称。

还有一些其他的辅助函数,可以使后面修复插入和删除的逻辑代码更加易读:

node **rbtree::getSelfFromParent(node *n)
{
    node *p = n->parent;
    return p->left == n ? (&(p->left)) : (&(p->right));
}
node **rbtree::getSiblingFromParent(node *n)
{
    node *p = n->parent;
    return p->left == n ? (&(p->right)) : (&(p->left));
}

getSelfFromParentgetSiblingFromParent 函数分别获取一个指针,该指针指向父节点中指向自己的指针和指向兄弟的指针。函数返回的是指针的指针,而不是直接指向自己或兄弟的指针,是因为这样可以用来改变指向的指针所指的内容。比如,*getSelfFromParent(n1)=n2 就可以将节点n1的父亲节点中,指向n1的指针(leftright)改成指向n2。

bool rbtree::isLeft(node *n)
{
    // 判断节点是否为父节点的左子结点
    return n->parent->left == n;
}
void rbtree::switchColor(node *n1, node *n2)
{
    bool tmp = n1->isRed;
    n1->isRed = n2->isRed;
    n2->isRed = tmp;
}
void rbtree::switchValue(node *n1, node *n2)
{
    int tmp = n1->value;
    n1->value = n2->value;
    n2->value = tmp;
}

这三个函数都比较简单实用,isLeft() 函数用来判断某个节点它是父亲的左子结点还是右子结点,switchColor() 函数用来交换两个节点的颜色,switchValue 用来交换两个节点的值。

修复插入

交代了这么多,总算进入重点了。

那么,为什么要修复插入呢?之前说到,在插入一个节点之后,我们执行 fixInsert() 。实际上,新插入了节点,该节点可能会破坏红黑树的性质1或5。

我们知道,新插入的节点n是红色的:

  1. 如果n的父节点p是黑色的
    1. 如果p是nil(也就是说,n是根节点),那么将n染成黑色,插入完成了(case1)。
    2. 如果p不是nil,而那么什么也不用做,插入就完成了(case2)。——如果它的父亲在插入前是叶子节点,那么插入之后n成为叶子节点,n本身是红色的,所以它的黑深度和p一样。如果在插入之前,p就有一个子节点s,那么s一定是红色的叶子节点(如果s是黑色的,而p的另一个子树为空,就违反了性质5),n插入之后,s就是n的兄弟节点。s和n都会具有与p一致的黑深度,也不会破坏性质。
  2. 如果n的父节点p是红色的,再插入一个红色子节点就违反了性质4,所以需要进行处理:
    1. 如果n的叔叔u是红色的,那么将u和p染成黑色,将n的爷爷节点g染成红色,然后执行fixInsert(g)(case3)。——如图所示,叔叔u是红色的,爷爷g一定是黑色的。这是p和n是连续的红节点,违反了性质4。处理之后,g变成了红色,又有可能违反性质4(g的父节点又是红色的)或者性质1(g就是根节点了)。这是再次对g调用fixInsert()
    2. 如果n的叔叔u是黑色:
      1. 如果n为左子节点且p为左子节点(如图) / n为右子节点且p为右子结点(与图对称),那么右旋/左旋g并交换p和g的颜色(case3)。
        2.如果n为右子结点且p为左子结点(如图) / n为左子结点且p为右子结点(与图对称),那么左旋/右旋p转化为上述情形(case4)。

修复插入case1:

修复插入Case2

修复插入case2:

修复插入Case3

修复插入case3:

修复插入Case4

代码如下所示:

void rbtree::fixInsert(node *n)
{
    if (n->parent == nil)
    {
        fixInsertCase1(n);
        return;
    }
    // 父节点P为黑色,则什么都不做
    if (n->parent->isRed == false)
    {
        fixInsertCase2(n);
    }
    else // 父节点P为红色
    {
        node *p = n->parent;
        node *u = *getSiblingFromParent(p);

        if (u->isRed == true)   /*叔叔节点U为红色*/
        {
            fixInsertCase3(n);
        }
        else    /*叔叔节点U为黑色*/
        {
            fixInsertCase4(n);
        }
    }
}
void rbtree::fixInsertCase1(node *n)
{
    n->isRed = false;
}
void rbtree::fixInsertCase2(node *n)
{
    return;
}
void rbtree::fixInsertCase3(node *n)
{
    node *p = n->parent;
    node *u = *getSiblingFromParent(p);
    node *g = p->parent;
    p->isRed = u->isRed = false;
    g->isRed = true;
    fixInsert(g);
}
void rbtree::fixInsertCase4(node *n)
{
    node *p = n->parent;
    node *u = *getSiblingFromParent(p);
    node *g = p->parent;
    if (isLeft(n) && isLeft(p))
    {
        rotateRight(g);
        switchColor(p, g);
    }
    else if (!isLeft(n) && !isLeft(p))
    {
        rotateLeft(g);
        switchColor(p, g);
    }
    else if (!isLeft(n) && isLeft(p))
    {
        rotateLeft(p);
        rotateRight(g);
        switchColor(n, g);
    }
    else // isLeft(n) && !isLeft(p)
    {
        rotateRight(p);
        rotateLeft(g);
        switchColor(n, g);
    }
}

修复删除

按照二叉查找树的删除方法,删除节点的操作都能转化为删除至多具有一个子节点的节点。如果被删除节点是红色的,那肯定不会对红黑树的性质造成影响,所以,完全不用在意。我们在意的是被删除节点是黑色的情况:如果被删除节点的子节点是红色的,那也好办,将子节点直接染黑就行,因为子节点代替了被删除节点的位置,它原来是红色的,对黑深度就没有贡献,染黑它,就可以起到被删除节点的作用。

最难办的是,如果被删除节点是黑色的,而且他的子节点还是黑色的(其实这时子节点只能是nil节点了),这时这条路径上就少了一个黑节点,此时就需要调用 fixRemove() 来修复。实际上,调用该函数的时机是,某一个节点由于某种变化(这里就是删除了一个黑节点且接上来的子节点也是黑色),导致通过该节点的路径少了一个黑节点。

fixRemove() 的逻辑是这样的(实际上,第一次删除节点后,节点的子节点n都是 nil ,只有开始递归调用自己之后,n才是正常的节点):

  1. 如果被删除节点的子节点n就是根节点(case1),那么结束。
  2. 如果n不是根节点:
    1. n的兄弟节点s是红节点(case2),那么N的父节点p和s互换颜色,并左旋(如图)/右旋(与图对称)p,转入case4,case5或case6。
    2. n的兄弟节点s为黑节点,s的左右节点都是黑节点(case3),那就将s染成红色,再对p执行 fixRemove() 。将s染成红色导致所有通过s的路径少了一个黑节点,这样就与通过n的路径一致了。现在通过p节点的所有路径都少了一个黑节点,所以要继续对p做 fixRemove()
    3. s与s的两个子节点都是黑色,但是p是红色(case4)。这时只需要交换p和s的颜色即可。原先通过p的路径上的黑节点数目没有变,但是通过n的节点数目补回来了。
    4. n是左节点(否则对称)的情况下,s是黑,s的左子节点是红,右子结点是黑(case5)。这时右旋s,这样n就有了一个右子节点为红色的兄弟,转入case6。
    5. n是左节点(否则对称)的情况下,s是黑,s的右子节点是红(case6)。这时左旋p,然后交换s和p的颜色,并且将是s的右节点染黑。这样,不管p原先是红色还是黑色,通过n的路径都增加了一个黑节点,而通过sr的路径保持不变。

修复删除case2:

修复删除Case2

修复删除case3:

修复删除Case3

修复删除case4:

修复删除Case4

修复删除case5:

修复删除Case5

修复删除case6:

修复删除Case6

代码如下所示:

void rbtree::fixRemove(node *n, node *p)
{
    if (p == nil)
    {
        fixRemoveCase1(n, p);
        return;
    }
    node *s = *getSiblingFromParent(n);
    if (s->isRed == true)
    {
        fixRemoveCase2(n, p);
        return;
    }
    // s为黑色
    if (p->isRed == false && s->left->isRed == false && s->right->isRed == false)
    {
        fixRemoveCase3(n, p);
        return;
    }
    if (p->isRed == true && s->left->isRed == false && s->right->isRed == false)
    {
        fixRemoveCase4(n, p);
        return;
    }
    if ((isLeft(n) && s->left->isRed == true && s->right->isRed == false) ||
            (!isLeft(n)  && s->right->isRed == true && s->left->isRed == false))
    {
        fixRemoveCase5(n, p);
        return;
    }
    if ((isLeft(n) &&  s->right->isRed == true) ||
            (!isLeft(n) && s->left->isRed == true))
    {
        fixRemoveCase6(n, p);
    }
}
void rbtree::fixRemoveCase1(node *n, node *p)
{
    return;
}
void rbtree::fixRemoveCase2(node *n, node *p)
{
    node *s = *getSiblingFromParent(n);
    if (isLeft(n))
    {
        rotateLeft(p);
    }
    else
    {
        rotateRight(p);
    }
    switchColor(p, s);
    fixRemove(n, p);
}
void rbtree::fixRemoveCase3(node *n, node *p)
{
    node *s = *getSiblingFromParent(n);
    s->isRed = true;
    fixRemove(p, p->parent);
}
void rbtree::fixRemoveCase4(node *n, node *p)
{
    node *s = *getSiblingFromParent(n);
    switchColor(s, p);
}
void rbtree::fixRemoveCase5(node *n, node *p)
{
    node *s = *getSiblingFromParent(n);
    if (isLeft(n))
    {
        rotateRight(s);
    }
    else
    {
        rotateLeft(s);
    }
    fixRemove(n, p);

}
void rbtree::fixRemoveCase6(node *n, node *p)
{
    node *s = *getSiblingFromParent(n);
    if (isLeft(n))
    {
        s->right->isRed = false;
        rotateLeft(p);
    }
    else
    {
        s->left->isRed = false;
        rotateRight(p);
    }
    switchColor(p, s);
}

这样就实现了红黑树。

(完)