2
我試圖使用算法提供的算法實現紅黑樹，算法第3版。一切工作正常，直到我測試刪除：似乎有算法中的錯誤。我無法找到網絡上的解決方案：其他解決方案（基於第二版算法）在仔細檢查時也失敗。紅黑樹刪除算法（CLR第3版）
算法在這裏可以看到：
Red-Black-Tree: Introduction to Algorithms (3rd edition)
不工作的算法：
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.left)
else
y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y
else // ISSUE
RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
當執行進入區域標記爲 「ISSUE」 以上時，它產生一種循環迴路：最終右子與其父項相同（打印到STDOUT顯示）。
全碼：
#include <vector>
template<typename T>
struct comparator {
int operator()(T& left, T& right) const {
return 0;
}
};
template<>
struct comparator<long> {
int operator()(const long& left, const long& right) const {
if(left<right) return -1;
else if (left>right) return 1;
else return 0;
}
};
template<typename _KEY, typename _VALUE>
struct MapEntry {
_KEY key;
_VALUE value;
};
enum TreeMapEntryColor { RED, BLACK };
template<typename _KEY, typename _VALUE>
struct TreeMapEntry {
MapEntry<_KEY,_VALUE> data;
TreeMapEntry<_KEY,_VALUE>* left;
TreeMapEntry<_KEY,_VALUE>* right;
TreeMapEntry<_KEY,_VALUE>* parent;
TreeMapEntryColor color;
};
template<typename _KEY, typename _VALUE>
class TreeMap {
public:
TreeMap() {
nil = new TreeMapEntry<_KEY,_VALUE>;
nil->color = BLACK;
nil->left = nil->right = nil->parent = nil;
root = nil;
}
void set(const _KEY& key, const _VALUE& value) {
TreeMapEntry<_KEY,_VALUE>* y = nil;
TreeMapEntry<_KEY,_VALUE>* x = root;
while(x!=nil) {
y = x;
int comparison = keyComparator(key, x->data.key);
if(comparison<0) {
x = x->left;
} else if(comparison==0) {
x->data.value = value;
return;
} else {
x = x->right;
}
}
TreeMapEntry<_KEY,_VALUE>* z = new TreeMapEntry<_KEY,_VALUE>;
z->data.key = key;
z->data.value = value;
z->parent = y;
if(y==nil) {
root = z;
} else if(keyComparator(key, y->data.key)<0) {
y->left = z;
} else {
y->right = z;
}
z->left = nil;
z->right = nil;
z->color = RED;
insertFixup(z);
}
void removeKey(const _KEY& key) {
TreeMapEntry<_KEY,_VALUE>* foundElement = nullptr;
TreeMapEntry<_KEY,_VALUE>* x = root;
while(x!=nil) {
int comparison = keyComparator(key, x->data.key);
if(comparison<0) {
x = x->left;
} else if(comparison==0) {
foundElement = x;
break;
} else {
x = x->right;
}
}
if(foundElement!=nullptr) {
deleteNode(foundElement);
}
}
void show() {
show(root);
}
~TreeMap() {
clear(root);
delete nil;
}
private:
void show(TreeMapEntry<_KEY,_VALUE>* const& h) {
std::cout << "Element: " << h->data.key << " Color: " << h->color << std::endl;
if(h->left!=nil) std::cout <<"Left: " << h->left->data.key << std::endl;
if(h->right!=nil) std::cout <<"Right: " << h->right->data.key << std::endl;
if(h->left!=nil) {
show(h->left);
}
if(h->right!=nil) {
show(h->right);
}
}
void clear(TreeMapEntry<_KEY,_VALUE>* const& h) {
if(h==nil) return;
clear(h->left);
clear(h->right);
delete h;
}
void deleteNode(TreeMapEntry<_KEY,_VALUE>*& z) {
TreeMapEntry<_KEY,_VALUE>* x = nil;
TreeMapEntry<_KEY,_VALUE>* y = z;
TreeMapEntryColor yOriginalColor = y->color;
if(z->left == nil) { // ok
x = z->right;
transplant(z, z->right);
} else if (z->right == nil) {
x = z->left;
transplant(z, z->left);
} else {
y = min(z->right);
yOriginalColor = y->color;
x = y->right;
if(y->parent == z) { // ok
x->parent = y;
} else {
// FIXME
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
transplant(y, y->right);
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
std::cout << __LINE__ << "#" << z->parent->data.key << ":" << z->data.key << ":" << z->left->data.key << ":" << z->right->data.key << std::endl;
y->right = z->right;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->right->parent = y;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
}
transplant(z, y);
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->left = z->left;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->left->parent = y;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->color = z->color;
}
delete z;
if(yOriginalColor == BLACK) {
deleteFixup(x);
}
}
void leftRotate(TreeMapEntry<_KEY,_VALUE>* x) {
TreeMapEntry<_KEY,_VALUE>* y = x->right;
x->right = y->left;
if (y->left != nil) {
y->left->parent=x;
}
y->parent=x->parent;
if(x->parent == nil) {
root=y;
} else if (x == x->parent->left) {
x->parent->left=y;
} else {
x->parent->right=y;
}
y->left=x;
x->parent=y;
}
void rightRotate(TreeMapEntry<_KEY,_VALUE>* x) {
TreeMapEntry<_KEY,_VALUE>* y = x->left;
x->left = y->right;
if (y->right != nil) {
y->right->parent=x;
}
y->parent=x->parent;
if(x->parent == nil) {
root=y;
} else if (x == x->parent->right) {
x->parent->right=y;
} else {
x->parent->left=y;
}
y->right=x;
x->parent=y;
}
void insertFixup(TreeMapEntry<_KEY,_VALUE>*& z) {
TreeMapEntry<_KEY,_VALUE>* y = nullptr;
while(z!=root && z->parent->color == RED) {
if(z->parent == z->parent->parent->left) {
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;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else {
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;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}
void transplant(TreeMapEntry<_KEY,_VALUE>*& u, TreeMapEntry<_KEY,_VALUE>*& v) {
if(u->parent == nil) {
root = v;
} else if(u==u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}
TreeMapEntry<_KEY,_VALUE>*& min(TreeMapEntry<_KEY,_VALUE>*& x) {
while(x->left != nil) {
x = x->left;
}
return x;
}
void deleteFixup(TreeMapEntry<_KEY,_VALUE>*& x) {
TreeMapEntry<_KEY,_VALUE>* w = nullptr;
while(x!=root && x->color == BLACK) {
if(x == x->parent->left) {
w = x->parent->right;
if(w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
leftRotate(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;
rightRotate(w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
w = x->parent->left;
if(w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rightRotate(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;
leftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
comparator<_KEY> keyComparator;
comparator<_VALUE> valueComparator;
TreeMapEntry<_KEY,_VALUE>* root;
TreeMapEntry<_KEY,_VALUE>* nil;
};
試驗循環迴路：
int main() {
TreeMap<long,long> tm;
tm.set(5,5);
tm.set(1,1);
tm.set(3,3);
tm.set(4,4);
tm.set(2,2);
tm.set(6,6);
tm.set(9,9);
tm.set(7,7);
tm.set(8,8);
// tm.removeKey(9); WORKS!
// tm.removeKey(7); DOESN'T WORK
tm.removeKey(5); // ROOT
tm.show();
std::cout << "OK" << std::endl;
return 0;
}
是否有任何人誰破解這個問題？
當您使用調試器時，哪個語句導致該問題？ –
您的書籍/頁面/＆c的鏈接。是不存在的。 – callyalater
你看過關於紅黑樹刪除算法的其他問題嗎？ – hatchet