从算法导论第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]<键[X]
6,则x←左[X]
7别人进行x←权[X]
8 P [Z]←ÿ
9如果y =零[T]
10再根[T]←ž
11否则,如果关键[Z]<键[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
实施
枚举颜色{黑,红};
模板<类重点>
结构节点
{
关键* KEY_;
颜色color_;
节点* PARENT_;
节点* left_;
节点* right_;
节点(密钥K,节点*父= nullptr,节点*左= nullptr,节点*右= nullptr):KEY_(新的关键[2]),
color_(红),
PARENT_(父),
left_(左),
right_(右)
{
KEY_ [0] = K表;
KEY_ [1] =' 0';
}
};
模板<类重点>
类树
{
节点< Key与GT; * head_;
类型定义键* key_pointer;
类型定义节点< Key与GT; *指针;
类型定义节点<关键 - GT; value_type的;
上市:
树(密钥K):head_(新value_type的(K))
{
头_-> color_ =黑色;
}
〜树()
{
删除head_;
}
指针根()const的
{
自动根= head_;
而(根 - > PARENT_)
{
根=根 - > PARENT_;
}
返回根;
}
空根(指针根)
{
head_ =根;
}
指针父()const的
{
返回头_-> PARENT_;
}
无效的父(母指针)
{
头_-> PARENT_ =父母;
}
指针向左()const的
{
返回头_-> left_;
}
空左侧(指针左)
{
头_-> left_ =左;
}
指针向右()const的
{
返回头_-> right_;
}
空权(指针右)
{
头_-> right_ =权利;
}
key_pointer键()const的
{
返回头_-> KEY_;
}
};
模板<分类,类节点>
无效left_rotate(树* T,节点* X)
{
自动Y = X轴和GT; right_;
X-> right_ = Y-GT; left_;
如果(Y-GT; left_)
{
Y-GT;左_-> PARENT_ = X;
}
Y-GT; PARENT_ = X-> PARENT_;
如果(X->!PARENT_)
{
T->根(Y);
}
否则,如果(X == X->母公司_-> left_)
{
X->母公司_-> left_ = Y;
}
其他
{
X->母公司_-> right_ = Y;
}
Y-GT; left_ = X;
X-> PARENT_ = Y;
}
模板<分类,类节点>
无效right_rotate(树* T,节点* X)
{
自动Y = X轴和GT; left_;
X-> left_ = Y-GT; right_;
如果(Y-GT; right_)
{
Y-GT;右_-> PARENT_ = X;
}
Y-GT; PARENT_ = X-> PARENT_;
如果(X->!PARENT_)
{
T->根(Y);
}
否则,如果(X == X->母公司_-> right_)
{
X->母公司_-> right_ = Y;
}
其他
{
X->母公司_-> left_ = Y;
}
Y-GT; right_ = X;
X-> PARENT_ = Y;
}
模板<分类,类Node_Value>
无效插入(树* T,Node_Value N)
{
自动Z = make_node(N);
汽车X = T->根();
decltype(Z)Y = nullptr;
而(X)
{
Y = X;
如果(* Z-> KEY_< * X-> KEY_)
{
X = X-> left_;
}
其他
{
X = X-> right_;
}
}
Z-> PARENT_ = Y;
如果(!Y)
{
T->根(Z);
}
其他
{
如果(* Z-> KEY_< * Y-GT; KEY_)
{
Y-GT; left_ = Z;
}
其他
{
Y-GT; right_ = Z;
}
}
Z-> left_ = nullptr;
Z-> right_ = nullptr;
Z-> color_ =红;
insert_fix_up(T,Z);
}
模板<分类,类节点>
无效insert_fix_up(树* T,节点* Z)
{
而(Z->母公司_-> color_ ==红)
{
如果(Z-> PARENT_ == Z->母公司_->母公司_-> left_)
{
自动Y = Z->母公司_->母公司_-> right_;
如果(Y-GT; color_ ==红)
{
Z->母公司_-> color_ =黑色;
Y-GT; color_ =黑色;
Z->母公司_->母公司_-> color_ =红;
Z = Z->母公司_-> PARENT_;
}
否则,如果(Z == Z->母公司_-> right_)
{
Z = Z-> PARENT_;
left_rotate(T,Z);
}
Z->母公司_-> color_ =黑色;
Z->母公司_->母公司_-> color_ =红;
right_rotate(T,Z->母公司_-> PARENT_);
}
其他
{
自动Y = Z->母公司_->母公司_-> left_;
如果(Y-GT; color_ ==红)
{
Z->母公司_-> color_ =黑色;
Y-GT; color_ =黑色;
Z->母公司_->母公司_-> color_ =红;
Z = Z->母公司_-> PARENT_;
}
否则,如果(Z == Z->母公司_-> left_)
{
Z = Z-> PARENT_;
right_rotate(T,Z);
}
Z->母公司_-> color_ =黑色;
Z->母公司_->母公司_-> color_ =红;
left_rotate(T,Z->母公司_-> PARENT_);
}
}
T->根() - > color_ =黑色;
}
模板<类节点>
节点* tree_minimum(节点* X)
{
而(X-> left_)
{
X = X-> left_;
}
返回X;
}
模板<类节点>
节点* tree_successor(节点* X)
{
如果(X-> right_)
{
返回tree_minimum(X-> right_);
}
自动Y = X轴和GT; PARENT_;
而(Y&安培;&放大器,X == Y-GT; right_)
{
X = Y;
Y = Y-GT; PARENT_;
}
返回是;
}
模板<分类,类节点>
节点* rb_delete(树* T,节点* Z)
{
节点* X = nullptr;
节点* Y = nullptr;
如果(Z->!left_ || Z-> right_)
{
Y = Z;
}
其他
{
Y = tree_successor(Z);
}
如果(Y-GT; left_)
{
X = Y-GT; left_;
}
其他
{
X = Y-GT; right_;
}
X-> PARENT_ = Y-GT; PARENT_;
如果(Y-GT;!PARENT_)
{
T->根(X);
}
否则,如果(Y == Y-GT;母公司_-> left_)
{
Y-GT;母公司_-> left_ = X;
}
其他
{
Y-GT;母公司_-> right_ = X;
}
如果(Y!= Z)
{
Z-> KEY_ = Y-GT; KEY_;
}
如果(Y-GT; color_ =黑)
{
rb_delete_fix_up(T,X);
}
返回是;
}
模板<分类,类节点>
无效rb_delete_fix_up(树*& T公司,节点*放大器,X)
{
而(X =叔>!根()&安培;&安培; x轴与GT; color_ ==黑色)
{
节点* W = nullptr;
如果(X == X->母公司_-> left_)
{
W = X轴和GT;母公司_-> right_;
如果(W-> color_ ==红)
{
W-> color_ =黑色;
X->母公司_-> color_ =红;
left_rotate(T,X轴和GT; PARENT_);
W = X轴和GT;母公司_-> right_;
}
如果(W->左_-> color_ ==黑色&安培;&安培; W->右_-> color_ ==黑)
{
W-> color_ =红;
X = X-> PARENT_;
}
否则,如果(W->右_-> color_ ==黑)
{
W->左_-> color_ =黑色;
W-> color_ =红;
right_rotate(T,W);
W = X轴和GT;母公司_-> right_;
}
W-> color_ = X->母公司_-> color_;
X->母公司_-> color_ =黑色;
W->右_-> color_ =黑色;
left_rotate(T,X轴和GT; PARENT_);
X = T->根();
}
其他
{
W = X轴和GT;母公司_-> left_;
如果(W-> color_ ==红)
{
W-> color_ =黑色;
X->母公司_-> color_ =红;
right_rotate(T,X轴和GT; PARENT_);
W = X轴和GT;母公司_-> left_;
}
如果(W->右_-> color_ ==黑色&安培;&安培; W->左_-> color_ ==黑)
{
W-> color_ =红;
X = X-> PARENT_;
}
否则,如果(W->左_-> color_ ==黑)
{
W->右_-> color_ =黑色;
W-> color_ =红;
left_rotate(T,W);
W = X轴和GT;母公司_-> left_;
}
W-> color_ = X->母公司_-> color_;
X->母公司_-> color_ =黑色;
W->左_-> color_ =黑色;
right_rotate(T,X轴和GT; PARENT_);
X = T->根();
}
}
X-> color_ =黑色;
}
模板<类重点>
节点<钥匙及GT * make_node(密钥k)的
{
返回新的节点<钥匙及GT;(K);
}
INT _tmain(INT ARGC,_TCHAR * argv的[])
{
自动T =新树< INT>(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] = ' ';
}
};
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;
}
相关推荐
最新文章