cari

Rumah  >  Soal Jawab  >  teks badan

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

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

有几个问题,

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

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

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

PHP中文网PHP中文网2808 hari yang lalu552

membalas semua(3)saya akan balas

  • PHPz

    PHPz2017-04-17 11:54:13

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

    首先,说说我自己写平衡树时的一些技巧;最简单的,比如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功能的“虚节点”(话说写平衡树一般都有的吧)

    balas
    0
  • 黄舟

    黄舟2017-04-17 11:54:13

    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的= =...

    balas
    0
  • 怪我咯

    怪我咯2017-04-17 11:54:13

    https://github.com/braydenCN/rbtree

    我以前写的.

    balas
    0
  • Batalbalas