红黑树删除算法 [英] Red Black Tree deletion algorithm
本文介绍了红黑树删除算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
从算法导论第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]] ← BLACK
IMPLEMENTATION
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;
}
这篇关于红黑树删除算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
