CODEWITHSUNDEEP
c++red-black-tree
Technupe
Technupe

Reputation: 4961

Can someone please verify if RedBlack Tree successor is written correctly?

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



}

Upvotes: 0

Views: 2408

Answers (1)

James McNellis
James McNellis

Reputation: 355207

This code is incorrect. Consider the following tree:

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

The in-order successor of b is c. Your function thinks the in-order successor is f. To find the in-order successor you have to handle several cases; this example tree has an instance of each case that needs to be handled. Start at each node and write down the steps that you need to find the in-order successor for each.

If you're interested, you can find an implementation of the algorithm with a full explanation in an answer I gave to another question.

On an unrelated note, your function should almost certainly be returning a std::pair by value and you should not be dynamically allocating the std::pair.

Upvotes: 4

Related Questions