CODEWITHSUNDEEP
c++data-structuresrecursioninsertred-black-tree
jordan
jordan

Reputation: 10722

Red-Black Tree Insert - Recursion Issue - C++

I have a recursive insert method that is being implemented in a Red-Black Tree. After returning from the recursive call, I am trying to see whether the local root's child is red. But what is actually happening is that I am checking on the root of the tree, not the subtree (where the most recent insert took place).

Here's the snippet of code that I'm looking at that is inside the insertNode method:

this->insertNode(root->right, value);
if(root->right->is_red) {
    cout << "color again & " << root->data << endl;
    root->right->is_red = false;
    root->is_red = true;
    this->rotateLeft(root);
}

How can I operate on the root of the subtree where the last insert took place? Do I need to make sure this is done before I come back from the recursive call?

Upvotes: 2

Views: 887

Answers (1)

Spook
Spook

Reputation: 25927

Modify the insertNode, such that it returns the actual inserted node. You'll be able to get to its parent easily after the insertion (assuming, that node knows its parent).

Upvotes: 1

Related Questions