从算法导论第2版我得到这个删除算法：
/ * RB-DELETE（T，Z） 1如果离开[Z] =零[T]或右边的[Z] =零[T] 2，则y←ž 3其他Ÿ←树后继（Z） 4如果离开[Y]≠零[T] 5，则x←离开[Y] 6别人进行x←权[Y] 7 P [X]←P [Y] 8如果p [Y] =零[T] 9然后根[T]←x 10否则如果y =左侧[P [Y] 11然后左键[P [Y]←x 12其他人的权利[P [Y]←x 13如果y！= Z 14然后键[Z]←键[Y] 15副本ÿ的卫星数据引入到z 16，如果颜色[Y] =黑色 17则RB-DELETE-FIXUP（T，X） 18返回是 * /现在一些问题，这个算法，一是主要的问题是，如果你尝试建立树（你可以做到这一点的 ）与节点1,2,3,4,5,6（放在这个顺序），然后删除节点2，行4,5和6这个算法返回nullptr（X == nullptr）。谁能帮我这个？
下面是辅助性的算法（来自同一本书）：
TREE后继（X） 1，如果权[X]≠NIL 2然后返回树最小（右[X]） 3根Y←P [X] 4而在Y≠NIL和X =正确的[Y] 5先去做x←ÿ 6 Y←P [Y] 7返回是 树最小（X） 1，而离开[X]≠NIL 2先去做x←左[X] 3返回X RB-DELETE-FIXUP（T，X） 1能够在X≠根[T]和颜色[X] =黑色 2做当x =左[P [X] 3则W←权[P [X] 4，如果颜色[W] = RED 然后5颜色[W]←BLACK▹案例1 6色[P [X]←RED▹案例1 7左旋转（T，P [X]）▹案例1 8瓦特←权[P [X]]▹案例1 9，如果颜色[离开[W] =黑色和彩色[右[W] =黑色 那么10色[W]←RED▹案例2 11 XP [X]▹案例2 12否则，如果颜色[右[W] =黑色 13则颜色[离开[W]←BLACK▹案例3 14颜色[W]←RED▹案例3 15 RIGHT-旋转（T，W）▹案例3 16瓦特←权[P [X]]▹案例3 17色[W]←颜色[P [X]]▹案例4 18色[P [X]←BLACK▹案例4 19颜色[右[W]←BLACK▹案例4 20左旋转（T，P [X]）▹案例4 21×←根[T]▹案例4 22其他（同然后用权利和第左交换） 23颜色[X]←黑 左旋转（T，X） 1年←权[X]▹设置年。 2右[X]←左[Y]▹转个Y左子树为X的右子树。 3 P [离开[Y]←x 4 P [Y]←P [X]▹链接X的父母为y。 5如果p [X] =零[T] 6然后根[T]←ÿ 7否则，如果X =左[P [X] 8然后左键[P [X]←ÿ 9其他权[P [X]←ÿ 10左[Y]←x▹放置X Y上的左边。 11 P [X]←ÿ RB-INSERT（T，Z） 1年零←[T] 2×←根[T] 3能够在X≠零[T] 4做ÿ←x 5，如果键[Z]＆LT;键[X] 6，则x←左[X] 7别人进行x←权[X] 8 P [Z]←ÿ 9如果y =零[T] 10再根[T]←ž 11否则，如果关键[Z]＆LT;键[Y] 12然后离开[Y]←ž 13别的吧[Y]←ž 14左[Z]←为零[T] 15右[Z]←为零[T] 16色[Z]←RED 17 RB-INSERT-FIXUP（T，Z） RB-INSERT-FIXUP（T，Z） 1，而颜色[P [Z] = RED 2做，如果P [Z] =左[P [P [Z]]] 3，则y←权[P [P [Z]]] 4，如果颜色[Y] = RED 5，然后颜色[P [Z]]←BLACK▹案例1 6色[Y]←BLACK▹案例1 7彩[P [P [Z]]]←RED▹案例1 8ž←P [P [Z]]▹案例1 9否则，如果Z =右[P [Z] 10则z←P [Z]▹案例2 11左旋转（T，Z）▹案例2 12色[P [Z]←BLACK▹案例3 13色[P [P [Z]]]←RED▹案例3 14 RIGHT-旋转（T，P [P [Z]）▹案例3 15其他（同then子句 与右和左的交换） 16色[根[T]←BLACK
实施
枚举颜色{黑，红}; 模板＆LT;类重点＆GT; 结构节点 { 关键* KEY_; 颜色color_; 节点* PARENT_; 节点* left_; 节点* right_; 节点（密钥K，节点*父= nullptr，节点*左= nullptr，节点*右= nullptr）：KEY_（新的关键[2]）， color_（红）， PARENT_（父）， left_（左）， right_（右） { KEY_ [0] = K表; KEY_ [1] ='\ 0'; } }; 模板＆LT;类重点＆GT; 类树 { 节点＆lt; Key与GT; * head_; 类型定义键* key_pointer; 类型定义节点＆lt; Key与GT; *指针; 类型定义节点＆lt;关键 - GT; value_type的; 上市： 树（密钥K）：head_（新value_type的（K）） { 头_-＆GT; color_ =黑色; } 〜树（） { 删除head_; } 指针根（）const的 { 自动根= head_; 而（根 - ＆GT; PARENT_） { 根=根 - ＆GT; PARENT_; } 返回根; } 空根（指针根） { head_ =根; } 指针父（）const的 { 返回头_-＆GT; PARENT_; } 无效的父（母指针） { 头_-＆GT; PARENT_ =父母; } 指针向左（）const的 { 返回头_-＆GT; left_; } 空左侧（指针左） { 头_-＆GT; left_ =左; } 指针向右（）const的 { 返回头_-＆GT; right_; } 空权（指针右） { 头_-＆GT; right_ =权利; } key_pointer键（）const的 { 返回头_-＆GT; KEY_; } }; 模板＆LT;分类，类节点＆GT; 无效left_rotate（树* T，节点* X） { 自动Y = X轴和GT; right_; X-＆GT; right_ = Y-GT; left_; 如果（Y-GT; left_） { Y-GT;左_-＆GT; PARENT_ = X; } Y-GT; PARENT_ = X-＆GT; PARENT_; 如果（X-＆GT;！PARENT_） { T-＆GT;根（Y）; } 否则，如果（X == X-＆GT;母公司_-＆GT; left_） { X-＆GT;母公司_-＆GT; left_ = Y; } 其他 { X-＆GT;母公司_-＆GT; right_ = Y; } Y-GT; left_ = X; X-＆GT; PARENT_ = Y; } 模板＆LT;分类，类节点＆GT; 无效right_rotate（树* T，节点* X） { 自动Y = X轴和GT; left_; X-＆GT; left_ = Y-GT; right_; 如果（Y-GT; right_） { Y-GT;右_-＆GT; PARENT_ = X; } Y-GT; PARENT_ = X-＆GT; PARENT_; 如果（X-＆GT;！PARENT_） { T-＆GT;根（Y）; } 否则，如果（X == X-＆GT;母公司_-＆GT; right_） { X-＆GT;母公司_-＆GT; right_ = Y; } 其他 { X-＆GT;母公司_-＆GT; left_ = Y; } Y-GT; right_ = X; X-＆GT; PARENT_ = Y; } 模板＆LT;分类，类Node_Value＆GT; 无效插入（树* T，Node_Value N） { 自动Z = make_node（N）; 汽车X = T-＆GT;根（）; decltype（Z）Y = nullptr; 而（X） { Y = X; 如果（* Z-＆GT; KEY_＆LT; * X-＆GT; KEY_） { X = X-＆GT; left_; } 其他 { X = X-＆GT; right_; } } Z-＆GT; PARENT_ = Y; 如果（！Y） { T-＆GT;根（Z）; } 其他 { 如果（* Z-＆GT; KEY_＆LT; * Y-GT; KEY_） { Y-GT; left_ = Z; } 其他 { Y-GT; right_ = Z; } } Z-＆GT; left_ = nullptr; Z-＆GT; right_ = nullptr; Z-＆GT; color_ =红; insert_fix_up（T，Z）; } 模板＆LT;分类，类节点＆GT; 无效insert_fix_up（树* T，节点* Z） { 而（Z-＆GT;母公司_-＆GT; color_ ==红） { 如果（Z-＆GT; PARENT_ == Z-＆GT;母公司_-＆GT;母公司_-＆GT; left_） { 自动Y = Z-＆GT;母公司_-＆GT;母公司_-＆GT; right_; 如果（Y-GT; color_ ==红） { Z-＆GT;母公司_-＆GT; color_ =黑色; Y-GT; color_ =黑色; Z-＆GT;母公司_-＆GT;母公司_-＆GT; color_ =红; Z = Z-＆GT;母公司_-＆GT; PARENT_; } 否则，如果（Z == Z-＆GT;母公司_-＆GT; right_） { Z = Z-＆GT; PARENT_; left_rotate（T，Z）; } Z-＆GT;母公司_-＆GT; color_ =黑色; Z-＆GT;母公司_-＆GT;母公司_-＆GT; color_ =红; right_rotate（T，Z-＆GT;母公司_-＆GT; PARENT_）; } 其他 { 自动Y = Z-＆GT;母公司_-＆GT;母公司_-＆GT; left_; 如果（Y-GT; color_ ==红） { Z-＆GT;母公司_-＆GT; color_ =黑色; Y-GT; color_ =黑色; Z-＆GT;母公司_-＆GT;母公司_-＆GT; color_ =红; Z = Z-＆GT;母公司_-＆GT; PARENT_; } 否则，如果（Z == Z-＆GT;母公司_-＆GT; left_） { Z = Z-＆GT; PARENT_; right_rotate（T，Z）; } Z-＆GT;母公司_-＆GT; color_ =黑色; Z-＆GT;母公司_-＆GT;母公司_-＆GT; color_ =红; left_rotate（T，Z-＆GT;母公司_-＆GT; PARENT_）; } } T-＆GT;根（） - ＆GT; color_ =黑色; } 模板＆LT;类节点＆GT; 节点* tree_minimum（节点* X） { 而（X-＆GT; left_） { X = X-＆GT; left_; } 返回X; } 模板＆LT;类节点＆GT; 节点* tree_successor（节点* X） { 如果（X-＆GT; right_） { 返回tree_minimum（X-＆GT; right_）; } 自动Y = X轴和GT; PARENT_; 而（Y＆安培;＆放大器，X == Y-GT; right_） { X = Y; Y = Y-GT; PARENT_; } 返回是; } 模板＆LT;分类，类节点＆GT; 节点* rb_delete（树* T，节点* Z） { 节点* X = nullptr; 节点* Y = nullptr; 如果（Z-＆GT;！left_ || Z-＆GT; right_） { Y = Z; } 其他 { Y = tree_successor（Z）; } 如果（Y-GT; left_） { X = Y-GT; left_; } 其他 { X = Y-GT; right_; } X-＆GT; PARENT_ = Y-GT; PARENT_; 如果（Y-GT;！PARENT_） { T-＆GT;根（X）; } 否则，如果（Y == Y-GT;母公司_-＆GT; left_） { Y-GT;母公司_-＆GT; left_ = X; } 其他 { Y-GT;母公司_-＆GT; right_ = X; } 如果（Y！= Z） { Z-＆GT; KEY_ = Y-GT; KEY_; } 如果（Y-GT; color_ =黑） { rb_delete_fix_up（T，X）; } 返回是; } 模板＆LT;分类，类节点＆GT; 无效rb_delete_fix_up（树*＆amp; T公司，节点*放大器，X） { 而（X =叔＆GT;！根（）＆安培;＆安培; x轴与GT; color_ ==黑色） { 节点* W = nullptr; 如果（X == X-＆GT;母公司_-＆GT; left_） { W = X轴和GT;母公司_-＆GT; right_; 如果（W-＆GT; color_ ==红） { W-＆GT; color_ =黑色; X-＆GT;母公司_-＆GT; color_ =红; left_rotate（T，X轴和GT; PARENT_）; W = X轴和GT;母公司_-＆GT; right_; } 如果（W-＆GT;左_-＆GT; color_ ==黑色＆安培;＆安培; W-＆GT;右_-＆GT; color_ ==黑） { W-＆GT; color_ =红; X = X-＆GT; PARENT_; } 否则，如果（W-＆GT;右_-＆GT; color_ ==黑） { W-＆GT;左_-＆GT; color_ =黑色; W-＆GT; color_ =红; right_rotate（T，W）; W = X轴和GT;母公司_-＆GT; right_; } W-＆GT; color_ = X-＆GT;母公司_-＆GT; color_; X-＆GT;母公司_-＆GT; color_ =黑色; W-＆GT;右_-＆GT; color_ =黑色; left_rotate（T，X轴和GT; PARENT_）; X = T-＆GT;根（）; } 其他 { W = X轴和GT;母公司_-＆GT; left_; 如果（W-＆GT; color_ ==红） { W-＆GT; color_ =黑色; X-＆GT;母公司_-＆GT; color_ =红; right_rotate（T，X轴和GT; PARENT_）; W = X轴和GT;母公司_-＆GT; left_; } 如果（W-＆GT;右_-＆GT; color_ ==黑色＆安培;＆安培; W-＆GT;左_-＆GT; color_ ==黑） { W-＆GT; color_ =红; X = X-＆GT; PARENT_; } 否则，如果（W-＆GT;左_-＆GT; color_ ==黑） { W-＆GT;右_-＆GT; color_ =黑色; W-＆GT; color_ =红; left_rotate（T，W）; W = X轴和GT;母公司_-＆GT; left_; } W-＆GT; color_ = X-＆GT;母公司_-＆GT; color_; X-＆GT;母公司_-＆GT; color_ =黑色; W-＆GT;左_-＆GT; color_ =黑色; right_rotate（T，X轴和GT; PARENT_）; X = T-＆GT;根（）; } } X-＆GT; color_ =黑色; } 模板＆LT;类重点＆GT; 节点＆lt;钥匙及GT * make_node（密钥k）的 { 返回新的节点＆lt;钥匙及GT;（K）; } INT _tmain（INT ARGC，_TCHAR * argv的[]） { 自动T =新树＆LT; INT＆GT;（1）; 插入（T，2）; 插入（T，3）; 插入（T，4）; 插入（T，5）; 插入（T，6）; rb_delete（T，T-和GT;左（））; 返回0; }解决方案
对于一个版本RB树的不哨兵删除操作实现如下：
SWRedBlackNode删除（SWRedBlackTree树，SWRedBlackNode节点）{ SWRedBlackNodeÿ; 如果（node._left == NULL || node._right == NULL）{ Y =节点; } 其他 { Y = node.getSuccessor（）; } SWRedBlackNode X; 如果（y._left！= NULL）{ X = y._left; } 其他 { X = y._right; } 如果（X！= NULL）{ x._parent = y._parent; } SWRedBlackNode xParent = y._parent; 布尔yIsLeft = FALSE; 如果（y._parent == NULL）{ tree._root = X; }否则，如果（Y == y._parent._left）{ y._parent._left = X; yIsLeft = TRUE; } 其他 { y._parent._right = X; yIsLeft = FALSE; } 如果（Y！=节点）{ node._value = y._value; } 如果（！y._isRed）{ deleteFixUp（树，X，xParent，yIsLeft）; } 返回是; } 私人无效deleteFixUp（SWRedBlackTree树，SWRedBlackNode节点，SWRedBlackNode nodeParent，布尔nodeIsLeft）{ 而（节点= tree._root和放大器;！＆安培; isBlack（节点））{ SWRedBlackNode瓦; 如果（nodeIsLeft）{ W = nodeParent._right; 如果（isRed（瓦特））{ w._isRed = FALSE; nodeParent._isRed = TRUE; leftRotate（树，nodeParent）; W = nodeParent._right; } 如果（isBlack（w._left）及＆安培; isBlack（w._right））{ w._isRed = TRUE; 节点= nodeParent; nodeParent = node._parent; nodeIsLeft =（节点== nodeParent._left）; } 其他 { 如果（isBlack（w._right））{ w._left._isRed = FALSE; w._isRed = TRUE; rightRotate（树，W）; W = nodeParent._right; } w._isRed = nodeParent._isRed; nodeParent._isRed = FALSE; 如果（w._right！= NULL）{ w._right._isRed = FALSE; } leftRotate（树，nodeParent）; 节点= tree._root; nodeParent = NULL; } }其他{/ * nodeIsLeft ==假* / W = nodeParent._left; 如果（isRed（瓦特））{ w._isRed = FALSE; nodeParent._isRed = TRUE; rightRotate（树，nodeParent）; W = nodeParent._left; } 如果（isBlack（w._right）及＆安培; isBlack（w._left））{ w._isRed = TRUE; 节点= nodeParent; nodeParent = node._parent; nodeIsLeft =（节点== nodeParent._left）; } 其他 { 如果（isBlack（w._left））{ w._right._isRed = FALSE; w._isRed = TRUE; leftRotate（树，W）; W = nodeParent._left; } w._isRed = nodeParent._isRed; nodeParent._isRed = FALSE; 如果（w._left！= NULL）{ w._left._isRed = FALSE; } rightRotate（树，nodeParent）; 节点= tree._root; nodeParent = NULL; } } } node._isRed = FALSE; }
这是在Java中，但可以很容易地移植到任何语言。
下面code是不同的关于您的实现：
嵌套在这里：
}其他{ 如果（isBlack（w._right））{
这里：
}其他{ 如果（isBlack（w._left））{
如果没有哨兵的东西在这里：
如果（X！= NULL）{ x._parent = y._parent; } SWRedBlackNode xParent = y._parent; 布尔yIsLeft = FALSE; 如果（y._parent == NULL）{ tree._root = X; }否则，如果（Y == y._parent._left）{ y._parent._left = X; yIsLeft = TRUE; } 其他 { y._parent._right = X; yIsLeft = FALSE; }
然后在这里：
deleteFixUp（树，X，xParent，yIsLeft）;
和 deleteFixUp（） - 只认准使用 nodeParent 和 nodeIsLeft ，终于在这个地方：
如果（w._right！= NULL）{ w._right._isRed = FALSE; }和这样的：
如果（w._left！= NULL）{ w._left._isRed = FALSE; }From "Introduction to Algorithms 2nd edition" I got this deletion algorithm:
/* RB-DELETE(T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ nil[T] 5 then x ← left[y] 6 else x ← right[y] 7 p[x] ← p[y] 8 if p[y] = nil[T] 9 then root[T] ← x 10 else if y = left[p[y]] 11 then left[p[y]] ← x 12 else right[p[y]] ← x 13 if y != z 14 then key[z] ← key[y] 15 copy y's satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return y */Now few problems with this algorithm, one main problem is that if you try to build tree ( you can do it here) with nodes 1,2,3,4,5,6 (placed in this order), and then delete node 2, lines 4,5 and 6 of this algorithm returns nullptr (x == nullptr). Can anyone help me with this?
Here are the helper algorithms (from same book):
TREE-SUCCESSOR(x) 1 if right[x] ≠ NIL 2 then return TREE-MINIMUM (right[x]) 3 y ← p[x] 4 while y ≠ NIL and x = right[y] 5 do x ← y 6 y ← p[y] 7 return y TREE-MINIMUM (x) 1 while left[x] ≠ NIL 2 do x ← left[x] 3 return x RB-DELETE-FIXUP(T, x) 1 while x ≠ root[T] and color[x] = BLACK 2 do if x = left[p[x]] 3 then w ← right[p[x]] 4 if color[w] = RED 5 then color[w] ← BLACK ▹ Case 1 6 color[p[x]] ← RED ▹ Case 1 7 LEFT-ROTATE(T, p[x]) ▹ Case 1 8 w ← right[p[x]] ▹ Case 1 9 if color[left[w]] = BLACK and color[right[w]] = BLACK 10 then color[w] ← RED ▹ Case 2 11 x p[x] ▹ Case 2 12 else if color[right[w]] = BLACK 13 then color[left[w]] ← BLACK ▹ Case 3 14 color[w] ← RED ▹ Case 3 15 RIGHT-ROTATE(T, w) ▹ Case 3 16 w ← right[p[x]] ▹ Case 3 17 color[w] ← color[p[x]] ▹ Case 4 18 color[p[x]] ← BLACK ▹ Case 4 19 color[right[w]] ← BLACK ▹ Case 4 20 LEFT-ROTATE(T, p[x]) ▹ Case 4 21 x ← root[T] ▹ Case 4 22 else (same as then clause with "right" and "left" exchanged) 23 color[x] ← BLACK LEFT-ROTATE(T, x) 1 y ← right[x] ▹ Set y. 2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree. 3 p[left[y]] ← x 4 p[y] ← p[x] ▹ Link x's parent to y. 5 if p[x] = nil[T] 6 then root[T] ← y 7 else if x = left[p[x]] 8 then left[p[x]] ← y 9 else right[p[x]] ← y 10 left[y] ← x ▹ Put x on y's left. 11 p[x] ← y RB-INSERT(T, z) 1 y ← nil[T] 2 x ← root[T] 3 while x ≠ nil[T] 4 do y ← x 5 if key[z] < key[x] 6 then x ← left[x] 7 else x ← right[x] 8 p[z] ← y 9 if y = nil[T] 10 then root[T] ← z 11 else if key[z] < key[y] 12 then left[y] ← z 13 else right[y] ← z 14 left[z] ← nil[T] 15 right[z] ← nil[T] 16 color[z] ← RED 17 RB-INSERT-FIXUP(T, z) RB-INSERT-FIXUP(T, z) 1 while color[p[z]] = RED 2 do if p[z] = left[p[p[z]]] 3 then y ← right[p[p[z]]] 4 if color[y] = RED 5 then color[p[z]] ← BLACK ▹ Case 1 6 color[y] ← BLACK ▹ Case 1 7 color[p[p[z]]] ← RED ▹ Case 1 8 z ← p[p[z]] ▹ Case 1 9 else if z = right[p[z]] 10 then z ← p[z] ▹ Case 2 11 LEFT-ROTATE(T, z) ▹ Case 2 12 color[p[z]] ← BLACK ▹ Case 3 13 color[p[p[z]]] ← RED ▹ Case 3 14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 15 else (same as then clause with "right" and "left" exchanged) 16 color[root[T]] ← BLACKIMPLEMENTATION
enum Color {Black,Red}; template<class Key> struct Node { Key* key_; Color color_; Node* parent_; Node* left_; Node* right_; Node(Key k,Node* parent = nullptr, Node* left = nullptr,Node* right = nullptr):key_(new Key[2]), color_(Red), parent_(parent), left_(left), right_(right) { key_[0] = k; key_[1] = '\0'; } }; template<class Key> class Tree { Node<Key>* head_; typedef Key* key_pointer; typedef Node<Key>* pointer; typedef Node<Key> value_type; public: Tree(Key k):head_(new value_type(k)) { head_->color_ = Black; } ~Tree() { delete head_; } pointer root()const { auto root = head_; while (root->parent_) { root = root->parent_; } return root; } void root(pointer root) { head_ = root; } pointer parent()const { return head_->parent_; } void parent(pointer parent) { head_->parent_ = parent; } pointer left()const { return head_->left_; } void left(pointer left) { head_->left_ = left; } pointer right()const { return head_->right_; } void right(pointer right) { head_->right_ = right; } key_pointer key()const { return head_->key_; } }; template<class Tree,class Node> void left_rotate(Tree* t, Node* x) { auto y = x->right_; x->right_ = y->left_; if (y->left_) { y->left_->parent_ = x; } y->parent_ = x->parent_; if (!x->parent_) { t->root(y); } else if(x == x->parent_->left_) { x->parent_->left_ = y; } else { x->parent_->right_ = y; } y->left_ = x; x->parent_ = y; } template<class Tree,class Node> void right_rotate(Tree* t, Node* x) { auto y = x->left_; x->left_ = y->right_; if (y->right_) { y->right_->parent_ = x; } y->parent_ = x->parent_; if (!x->parent_) { t->root(y); } else if(x == x->parent_->right_) { x->parent_->right_ = y; } else { x->parent_->left_ = y; } y->right_ = x; x->parent_ = y; } template<class Tree, class Node_Value> void insert(Tree* t, Node_Value n) { auto z = make_node(n); auto x = t->root(); decltype(z) y = nullptr; while(x) { y = x; if (*z->key_ < *x->key_) { x = x->left_; } else { x = x->right_; } } z->parent_ = y; if (!y) { t->root(z); } else { if (*z->key_ < *y->key_) { y->left_ = z; } else { y->right_ = z; } } z->left_ = nullptr; z->right_ = nullptr; z->color_ = Red; insert_fix_up(t,z); } template<class Tree, class Node> void insert_fix_up(Tree* t, Node* z) { while (z->parent_->color_ == Red) { if (z->parent_ == z->parent_->parent_->left_) { auto y = z->parent_->parent_->right_; if (y->color_ == Red) { z->parent_->color_ = Black; y->color_ = Black; z->parent_->parent_->color_ = Red; z = z->parent_->parent_; } else if(z == z->parent_->right_) { z = z->parent_; left_rotate(t,z); } z->parent_->color_ = Black; z->parent_->parent_->color_ = Red; right_rotate(t,z->parent_->parent_); } else { auto y = z->parent_->parent_->left_; if (y->color_ == Red) { z->parent_->color_ = Black; y->color_ = Black; z->parent_->parent_->color_ = Red; z = z->parent_->parent_; } else if(z == z->parent_->left_) { z = z->parent_; right_rotate(t,z); } z->parent_->color_ = Black; z->parent_->parent_->color_ = Red; left_rotate(t,z->parent_->parent_); } } t->root()->color_ = Black; } template<class Node> Node* tree_minimum(Node* x) { while (x->left_) { x = x->left_; } return x; } template<class Node> Node* tree_successor(Node* x) { if (x->right_) { return tree_minimum(x->right_); } auto y = x->parent_; while (y && x == y->right_) { x = y; y = y->parent_; } return y; } template<class Tree, class Node> Node* rb_delete(Tree* t,Node* z) { Node* x = nullptr; Node* y = nullptr; if (!z->left_ || !z->right_) { y = z; } else { y = tree_successor(z); } if (y->left_) { x = y->left_; } else { x = y->right_; } x->parent_ = y->parent_; if (!y->parent_) { t->root(x); } else if (y == y->parent_->left_) { y->parent_->left_ = x; } else { y->parent_->right_ = x; } if (y != z) { z->key_ = y->key_; } if (y->color_ = Black) { rb_delete_fix_up(t,x); } return y; } template<class Tree, class Node> void rb_delete_fix_up(Tree*& t,Node*& x) { while (x != t->root() && x->color_ == Black) { Node* w = nullptr; if (x == x->parent_->left_) { w = x->parent_->right_; if (w->color_ == Red) { w->color_ = Black; x->parent_->color_ = Red; left_rotate(t,x->parent_); w = x->parent_->right_; } if (w->left_->color_ == Black && w->right_->color_ == Black) { w->color_ = Red; x = x->parent_; } else if(w->right_->color_ == Black) { w->left_->color_ = Black; w->color_ = Red; right_rotate(t,w); w = x->parent_->right_; } w->color_ = x->parent_->color_; x->parent_->color_ = Black; w->right_->color_ = Black; left_rotate(t,x->parent_); x = t->root(); } else { w = x->parent_->left_; if (w->color_ == Red) { w->color_ = Black; x->parent_->color_ = Red; right_rotate(t,x->parent_); w = x->parent_->left_; } if (w->right_->color_ == Black && w->left_->color_ == Black) { w->color_ = Red; x = x->parent_; } else if(w->left_->color_ == Black) { w->right_->color_ = Black; w->color_ = Red; left_rotate(t,w); w = x->parent_->left_; } w->color_ = x->parent_->color_; x->parent_->color_ = Black; w->left_->color_ = Black; right_rotate(t,x->parent_); x = t->root(); } } x->color_ = Black; } template<class Key> Node<Key>* make_node(Key k) { return new Node<Key>(k); } int _tmain(int argc, _TCHAR* argv[]) { auto t = new Tree<int>(1); insert(t,2); insert(t,3); insert(t,4); insert(t,5); insert(t,6); rb_delete(t,t->left()); return 0; }解决方案
For a version of rb-tree without sentinels the delete operation implementation is as follows:
SWRedBlackNode delete(SWRedBlackTree tree, SWRedBlackNode node) { SWRedBlackNode y; if (node._left == null || node._right == null) { y = node; } else { y = node.getSuccessor(); } SWRedBlackNode x; if (y._left != null) { x = y._left; } else { x = y._right; } if (x != null) { x._parent = y._parent; } SWRedBlackNode xParent = y._parent; boolean yIsLeft = false; if (y._parent == null) { tree._root = x; } else if (y == y._parent._left) { y._parent._left = x; yIsLeft = true; } else { y._parent._right = x; yIsLeft = false; } if (y != node) { node._value = y._value; } if (!y._isRed) { deleteFixUp(tree, x, xParent, yIsLeft); } return y; } private void deleteFixUp(SWRedBlackTree tree, SWRedBlackNode node, SWRedBlackNode nodeParent, boolean nodeIsLeft) { while (node != tree._root && isBlack(node)) { SWRedBlackNode w; if (nodeIsLeft) { w = nodeParent._right; if (isRed(w)) { w._isRed = false; nodeParent._isRed = true; leftRotate(tree, nodeParent); w = nodeParent._right; } if (isBlack(w._left) && isBlack(w._right)) { w._isRed = true; node = nodeParent; nodeParent = node._parent; nodeIsLeft = (node == nodeParent._left); } else { if (isBlack(w._right)) { w._left._isRed = false; w._isRed = true; rightRotate(tree, w); w = nodeParent._right; } w._isRed = nodeParent._isRed; nodeParent._isRed = false; if (w._right != null) { w._right._isRed = false; } leftRotate(tree, nodeParent); node = tree._root; nodeParent = null; } } else { /* nodeIsLeft == false */ w = nodeParent._left; if (isRed(w)) { w._isRed = false; nodeParent._isRed = true; rightRotate(tree, nodeParent); w = nodeParent._left; } if (isBlack(w._right) && isBlack(w._left)) { w._isRed = true; node = nodeParent; nodeParent = node._parent; nodeIsLeft = (node == nodeParent._left); } else { if (isBlack(w._left)) { w._right._isRed = false; w._isRed = true; leftRotate(tree, w); w = nodeParent._left; } w._isRed = nodeParent._isRed; nodeParent._isRed = false; if (w._left != null) { w._left._isRed = false; } rightRotate(tree, nodeParent); node = tree._root; nodeParent = null; } } } node._isRed = false; }It's in Java but can easily be ported to any language.
The following code is different in respect to your implementation:
Nesting here:
} else { if (isBlack(w._right)) {and here:
} else { if (isBlack(w._left)) {Without-sentinel stuff here:
if (x != null) { x._parent = y._parent; } SWRedBlackNode xParent = y._parent; boolean yIsLeft = false; if (y._parent == null) { tree._root = x; } else if (y == y._parent._left) { y._parent._left = x; yIsLeft = true; } else { y._parent._right = x; yIsLeft = false; }then here:
deleteFixUp(tree, x, xParent, yIsLeft);and in deleteFixUp() - just look for usage of nodeParent and nodeIsLeft, and finally at this place:
if (w._right != null) { w._right._isRed = false; }and this:
if (w._left != null) { w._left._isRed = false; }