CODEWITHSUNDEEP
c++binary-search-tree
Nguyen Tran
Nguyen Tran

Reputation: 95

Insert a duplicate key value into binary tree

I'm trying to write an insert method for my binary search tree class. I want it to be able to insert a new value into a tree that already has an existing node with this same data value must cause a new node to be created in the right subtree of the existing node. Here's my code. I'm getting an unhandled exception error while trying to compile. I don't know what I did wrong there. If someone can explain the reason why the compiler is giving me error, it would be great. Thanks :)

template <class elemType>
void bSearchTreeType<elemType>::insert
                 (const elemType& insertItem)
{
    nodeType<elemType> *current; //pointer to traverse the tree
    nodeType<elemType> *trailCurrent; //pointer behind current
    nodeType<elemType> *newNode;  //pointer to create the node

    newNode = new nodeType<elemType>;
    newNode->info = insertItem;
    newNode->lLink = NULL;
    newNode->rLink = NULL;

    if (root == NULL)
        root = newNode;
    else
    {
        current = root;

        while (current != NULL)
        {
            trailCurrent = current;

            if (current->info == insertItem)
            {
                current = current->rLink;
                trailCurrent->rLink = newNode;
                if (newNode->info <= current->info) //this is where the compiler say the error is
                    newNode->rLink = current;
                else
                    newNode->lLink = current;
            }
            else if (current->info > insertItem)
                current = current->lLink;
            else
                current = current->rLink;
        }//end while

        if (trailCurrent->info < insertItem)
            trailCurrent->rLink = newNode;
        else if (trailCurrent->info > insertItem)
            trailCurrent->lLink = newNode;
    }
}//end insert

Upvotes: 1

Views: 1333

Answers (3)

WhozCraig
WhozCraig

Reputation: 66194

I'm fairly certain this is what you're trying to do:

template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
    nodeType<elemType> **pp = &root;
    while (*pp)
    {
        if (insertItem < (*pp)->info)
            pp = &(*pp)->lLink;
        else if ((*pp)->info < insertItem)
            pp = &(*pp)->rLink);
        else break;
    }

    // note: this is cleaner if the the nodeType constructor
    //  is parameterized. (hint hint)
    nodeType<elemType> *p = new nodType<elemType>;
    p->info = insertItem;
    p->lLink = NULL;

    if (*pp)
    {
        p->rLink = (*pp)->rLink;
        (*pp)->rLink = p;
    }
    else
        *pp = p;
}

How it works

The basics of finding an insertion point for a new non-existing key are mundane, so I'll not cover them. The case of locating an existing key is, however, interesting. We use a pointer-to-pointer to hold the address of each node pointer we encounter while walking down the tree. When we have a match the loop will exit and *pp will not be null. When that happens, our new node has it's right-pointer set to the matched right-pointer, and the matched node's right-pointer becomes the new node. The remainder of the tree remains as-is.

I.e. adding a second 7 in this:

        5
   3        7
2     4  6     8

results in 

        5
   3        7
2     4  6     7
                 8

then adding another 3 results in:

         5
   3           7
2     3     6     7
        4           8

All of this, of course, assuming i understood the problem.No attempt at rotations or balancing is done. That I leave to you.

Upvotes: 0

simpPLee
simpPLee

Reputation: 1

Not sure if this is correct but

trialCurrent = current;

trialCurrent is equal to current

if(current->info == insertItem)
    current = current->rLink;
    trialCurrent->rlink = newnode;

current is equal to current->rLink, then wouldn't trialCurrent->rLink be equal to current?

Upvotes: 0

gsamaras
gsamaras

Reputation: 73366

You should make a deal with yourself. This deal can be like this:

The left subtree will have values less or equal than the one in the root and so on.

In code you have:

if (trailCurrent->info < insertItem)
  trailCurrent->rLink = newNode;

which after the deal would be like this:

if (trailCurrent->info <= insertItem)
  trailCurrent->rLink = newNode;

Upvotes: 1

Related Questions