c++ - 红黑树删除算法(CLR第3版)

Question

我正在尝试使用 CLR Introduction to Algorithms 3rd edition 提供的算法来实现红黑树。在我测试删除之前一切正常:算法中似乎存在错误。我在网上找不到任何解决方案:所有其他解决方案(基于第二版算法)在仔细检查时也失败了。

算法可以在这里查看:

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;
}

有人破解过这个问题吗？

Answer 1

您对 C++ 的翻译是错误的。

您几乎在所有地方都将函数调用语义从按值传递更改为按引用传递。
这不是保留语义的更改。
(CLR 从不使用引用传递。)

特别是，min——它只应该定位一个特定的节点——最终将它的参数指向那个节点。

按值而不是按引用传递和返回所有指针会使您的错误消失。