数据结构 - C++ 红黑树各种SegFault

Question

刚开始学习写红黑树，是对着CLRS撸的，但是完全照抄的话会各种出现SegFault，

有几个问题，

1.书本上写的“T.nil"是不是用nullptr代替？还是有什么处理方法？
2.我觉得我各种出现SegFault主要是在insertfixup种，node->parent 和node->parent->parent不一定存在，如果不存在，就会出错，但是我加了判断是否存在之后错误仍然是存在=.=

求巨巨们帮帮忙解决一下。。

ps:能发一个红黑树的范例是再好不过了……

Answer 1

好吧，离提问时间有点久了，不过还是回答一下。

首先，说说我自己写平衡树时的一些技巧；最简单的，比如Splay，每个结点需要记录father,child_left,child_right，那么在旋转之后update时会需要更新子树大小size=child_left child_right 1，如果此时左右儿子为NULL，则会报错；解决方法通常是自己增设一个结点null，并令其左右儿子和父亲均为null(指向自己),这样所有访问到的空节点均为null而非NULL,就不会报错了

猜想你所说的T.nil就是我在实现中所用的null，这样你的第二个问题也就解决了；

话说STL的set和map底层就是用RB-Tree实现的，可以参考那玩意的代码；顺便一提，那玩意也有类似null功能的“虚节点”（话说写平衡树一般都有的吧）

Answer 2

1. 可以
2. 在1.的情况下写一个access宏处理掉null
3. 初见调试的时候不停的把树输出出来有奇效。之后请考虑压代码以减少误码率。
4. 看啥STL，挑短的rbt代码看。。如果有空的话我周末写一个。。吧？

大概是这样吧... 好久没写了= =!

cpp#include <cstdio>

using namespace std;

const int MaxN = 50000;

struct node{
    node *ch[2], *p;
    int v, sz; bool color; // 1 red 0 black
    int getDir() { return p->ch[1] == this; }
    void update() { sz = (ch[0]?(ch[0]->sz):(0)) + (ch[1]?(ch[1]->sz):(0)) + 1; }
} pool[MaxN], *cur = pool;

node *newNode(int v){
    node *_ = cur++;
    _->color = 1; _->sz = 1; _->p = _->ch[0] = _->ch[1] = NULL; _->v = v;
    return _;
}

node* rotate(node *cur){
    if (!cur->p) return cur;
    int dir = cur->getDir(); node* f = cur->p;
    cur->p = f->p;
    if (f->p) 
        f->p->ch[f->getDir()] = cur;
    f->ch[dir] = cur->ch[dir^1];
    if (cur->ch[dir^1]) cur->ch[dir^1]->p = f;
    f->p = cur;cur->ch[dir^1] = f;
    f->update();cur->update();
    return f;
}

node* maintain(node *cur){
    while (cur->p && cur->p->p && cur->p->color) {
        int dir = cur->p->getDir();
        node * y = cur->p->p->ch[dir^1];
        if (y && y->color){
            cur->p->color = y->color = 0;
            cur->p->p->color = 1;
            cur->p->update(); cur->p->p->update();
            cur = cur->p->p;
        } else {
            if (cur->getDir() != cur->p->getDir()) { cur = rotate(cur); }
            cur->p->color = 0; cur->p->p->color = 1;
            rotate(cur->p);
        }
    }
    while (cur->p) {cur = cur->p; cur->update();}
    cur->color = 0;
    return cur;
}

node* insert(node *cur, int v){
    node *p = NULL, *np = newNode(v);
    while (cur) {
        p = cur;
        cur = cur->ch[v > cur->v];
    }
    cur = p; np->p = cur;
    if (cur) cur->ch[v > cur->v] = np;
    return maintain(np);
}

至少看起来是work的= =...

Answer 3

https://github.com/braydenCN/rbtree

我以前写的.