c++ - 有人可以验证 RedBlack Tree 的后继者是否正确编写？

Question

pair<K,V> *RedBlackTree<K,V,Compare>::successor(K key) {

    Node *found = findNode(key, root);

    Node *p;
    Node *ch;
    Node *x;

    Node *y;
    if(found->right != sentinel)
        return new pair<K,V>(found->right->key, found->right->value);

    y = found->parent;
    /* if it does not have a left child,
    predecessor is its first left ancestor */
    while(y != NULL && found == y->right) {
            found = y;
            y = y->parent;
    }
    return new pair<K,V>(y->key, y->value);



}

Answer 1

此代码不正确。考虑以下树：

   b
  / \
 a   f
    / \
   d   g
  / \
 c   e

的有序后继b是c。您的函数认为有序后继是f. 要找到有序的继任者，您必须处理几种情况；这个示例树有一个需要处理的每个案例的实例。从每个节点开始，写下为每个节点找到有序后继节点所需的步骤。

如果您有兴趣，可以在我对另一个问题的回答中找到该算法的实现，并提供完整的解释。

---

在不相关的说明中，您的函数几乎可以肯定是std::pair 按值返回 a并且您不应该动态分配std::pair.