已解決430363個問題，去搜搜看，總會有你想問的

C++ 紅黑樹各種SegFault

首頁猿問 C++ 紅黑樹各種SegFault

C++ 紅黑樹各種SegFault

JavaScript

當年話下 2019-04-08 09:21:46

剛開始學習寫紅黑樹，是對著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功能的“虛節點”（話說寫平衡樹一般都有的吧）

反對回復 2019-04-08

2 回答
0 關注
451 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

C++ 紅黑樹各種SegFault

C++ 紅黑樹各種SegFault

2 回答

添加回答