刚开始学习写红黑树，是对着CLRS撸的，但是完全照抄的话会各种出现SegFault，有几个问题，1.书本上写的“T.nil"是不是用nullptr代替？还是有什么处理方法？2.我觉得我各种出现SegFault主要是在insertfixup种，node->parent和node->parent->parent不一定存在，如果不存在，就会出错，但是我加了判断是否存在之后错误仍然是存在=.=求巨巨们帮帮忙解决一下。。ps:能发一个红黑树的范例是再好不过了……
2 回答
阿晨1998
TA贡献2037条经验 获得超6个赞
好吧，离提问时间有点久了，不过还是回答一下。首先，说说我自己写平衡树时的一些技巧；最简单的，比如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功能的“虚节点”（话说写平衡树一般都有的吧）
添加回答
举报
0/150
提交
取消