Может кто-нибудь проверить, правильно ли написан преемник RedBlack Tree? - PullRequest
Новая
       5

Может кто-нибудь проверить, правильно ли написан преемник RedBlack Tree?

0 голосов
/ 15 апреля 2011 
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);



}

1 Ответ

4 голосов
/ 15 апреля 2011

Этот код неверен.Рассмотрим следующее дерево: 

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

Последовательный преемник b равен c.Ваша функция считает, что преемник в порядке f.Чтобы найти преемника по порядку, вам нужно разобраться с несколькими случаями;у этого дерева примеров есть экземпляр каждого случая, который должен быть обработан.Начните с каждого узла и запишите шаги, необходимые для поиска преемника по порядку для каждого узла.

Если вам интересно, вы можете найти реализацию алгоритма с полным объяснением в ответ, который я дал на другой вопрос .

Нанесвязанное примечание, ваша функция почти наверняка должна возвращать std::pair по значению , и вы не должны динамически выделять std::pair.

...