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

Question

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

有几个问题，

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

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

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

Answer 1

Okay, it’s been a while since the question time, but I’ll answer it anyway.

First of all, let me talk about some of my own skills in writing balanced trees; the simplest ones, such as Splay, each node needs to record father, child_left, child_right, which will be needed when updating after rotation. Update the subtree size size=child_left+child_right+1. If the left and right sons are NULL at this time, an error will be reported; the solution is usually to add a node null yourself, and make its left and right sons and father null (pointing to yourself). In this way, all empty nodes visited are null instead of NULL, and no error will be reported

I guess the T.nil you are talking about is the null I used in the implementation, so your second problem will be solved;

STL's set and map bottom layers are implemented using RB-Tree. You can refer to the code of that thing; by the way, that thing also has a "virtual node" with a similar null function (which is generally available when writing balanced trees, right? )

Answer 2

1. Yes
2. Write an access macro to handle null in case 1.
3. For the first time, I saw that continuously outputting the tree worked wonders when debugging. Please consider code compression later to reduce the bit error rate.
4. When looking at STL, pick out the short rbt code. . I'll write one on the weekend if I have time. . Bar?

That’s probably it... I haven’t written for a long time = =!

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);
}

At least it looks like it works = =...

Answer 3

https://github.com/braydenCN/rbtree

I wrote it before.