How to find an element in a binary search tree?

Question

I've been trying to build a 2-3 node. The adding function is working properly and has been confirmed by me so far. The only problem is the find function, which is called to find an element inside the 2-3 node. It does not seem to be working at all. The match pointer inside the it does not take the returned valued from the find_rec method at all, even though I already assigned it. It's just getting a new given address whenever the function is called and I have no idea why it does that. Can anyone help me out ? and tell me what I did wrong ? Thank you

**LValue and RValue**

E LValue() {return _first._value;}
E RValue() {return _second._value;}



**find function**

// Assuming this set contains an element y such that (x == y),
// return a reference to y. Such a y must exist; if it does not an
// assertion will fail. 
E& find(E& x) 
{
        // the match pointer is supposed to take
        // returned pointer from the find_rec function
        // Yet, it is not doing that at all.
    E* match = find_rec(x, _root);
    assert(match != nullptr);
    return *match;
}


**find_rec function**

// Helper function: find recursion
// function returns a pointer
E* find_rec(E& x, BNode<E>* root)
{
    if(root == nullptr)
        return nullptr;
    else
    {
        // 2-node
        if(!root->IsThree())
        {
            if(x == root->LValue())
                return &root->LValue();
            else if (x < root->LValue())
                return find_rec(x, root->GetLeft());
            else
                return find_rec(x, root->GetRight());
        }
        // 3-node
        else
        {
            if(x == root->LValue())
                return &root->LValue();
            else if(x == root->RValue())
                return &root->RValue();
            else if(x < root->LValue())
                return find_rec(x, root->GetLeft());
            else if(x < root->RValue())
                return find_rec(x, root->GetMiddle());
            else
                return find_rec(x, root->GetRight());
        }
    }
}

@RichardPlunkett: it looks correct to me as well, but it's not working as intended :( — Hoang Minh
– Hoang Minh, Commented Dec 26, 2013 at 13:56
those names starting with underscores bother me. Didn't C++ reserve those quite sometime ago. — RichardPlunkett
– RichardPlunkett, Commented Dec 26, 2013 at 14:13

RichardPlunkett · Accepted Answer · 2013-12-26 14:16:57Z

1

The code is clearly able to return a nullptr when the desired value is not present in the tree.

The moment it gets into that situation, the assert will trigger and the *match return would fail. I expect you need to change the function signature to provide a return type that allows for this case.

answered Dec 26, 2013 at 14:16

RichardPlunkett

2,98817 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

6502 · Accepted Answer · 2013-12-26 13:47:31Z

1

From the code seems you're returning the address of a local temporary.

I cannot be sure because the LValue() method declaration is not visible, but if it's returning the node content by value and not by reference then the find_rec function will just return garbage (the address of a temporary allocated on the stack).

A decent compiler should issue a warning for this, by the way.

answered Dec 26, 2013 at 13:47

6502

115k17 gold badges177 silver badges277 bronze badges

5 Comments

Hoang Minh Over a year ago

I just edit my post and put up the RValue and LValue. I'm using Visual Studio 2012, and it compiles successfully without any warnings at all. The program runs, but it crashes right at the assert checking, because matching is pointing to NULL....

6502 Over a year ago

As I suspected LValue and RValue are returning by value and the code would not work (and if VS2012 doesn't issue a warning about returning the address of a local it simply means VS2012 is not a decent compiler). If the function is returning NULL then the tree doesn't contain what you think or is not respecting the order invariant. Can't tell what the problem is without seeing all the code.

Hoang Minh Over a year ago

The tree does have the value, and the insert function is working properly as well. It's just that I cannot link the pointer to the value of the node in the find function.

6502 Over a year ago

If the result is nullptr then you're not finding the node. If instead you are finding the node then using &root->LValue() is wrong, because the result is a temporary and you should not return the address of a temporary to the caller (once you're back in the caller the temporary doesn't exist any more). To get this last part working you can just change LValue() and RValue() to return E& instead of E.

RichardPlunkett Over a year ago

definitely should fix this. I encourage returning a reference.

Collectives™ on Stack Overflow

How to find an element in a binary search tree?

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related