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);
}
问问题
1726 次
1 回答
4
此代码不正确。考虑以下树:
b
/ \
a f
/ \
d g
/ \
c e
的有序后继b
是c
。您的函数认为有序后继是f
. 要找到有序的继任者,您必须处理几种情况;这个示例树有一个需要处理的每个案例的实例。从每个节点开始,写下为每个节点找到有序后继节点所需的步骤。
如果您有兴趣,可以在我对另一个问题的回答中找到该算法的实现,并提供完整的解释。
在不相关的说明中,您的函数几乎可以肯定是std::pair
按值返回 a并且您不应该动态分配std::pair
.
于 2011-04-14T23:06:30.977 回答