数据结构 - 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

我以前寫的.