Im stuck with filling my Array Based BST in C++

Question

Im trying to build an array based, "Binary Search Tree" by following the algorithm here.

Using the algorithm I came up with the following code:

void BST::insert(const data &aData)
{
    item *y = &items[root_index];   // Algorithm calls for NULL assignment..
    item *x = &items[root_index]; 

    while (!items[root_index].empty)
    {
        y->theData = x->theData; // Ptrs are required or else a crash occurs.
        if (aData < x->theData)
        {
            x->leftChild = aData;
        }
        else
        {
            x->rightChild = items[root_index].theData;
        } 

        // what is p[z] = y? is it outside the looping scheme?
    
        root_index++; // and make the new child the root?   
    }

    if (y->empty) 
    {
        items[root_index].theData = aData;
        items[root_index].empty = false;
    }
    else if (aData < y->theData)
    {
        y->leftChild = aData; 
        // If we already have a left/right child...make it the root? re-cmpr?
    }
    else
    {
        y->rightChild = items[root_index].theData;
    }
}

Questions:

I cannot figure out what p[z] <- y means. I'm just incrementing the root to imitate a traverse.

If I already have a left/right child then I should make that left/right child that I'm about to overwrite the root? Therein I should make it recursive so it will switch back to the original root, "R"?

Insertions

insert("R");
insert("A");
insert("F");
insert("L");
insert("B");
insert("C");
insert("T");

I edited my comment to add an example of my insert method which follows the pseudocode in Intro to Algorithms. The comments in the code should help with understanding the pseudocode. — Jim Schubert
– Jim Schubert, Commented Nov 15, 2009 at 0:37

Jim Schubert · Accepted Answer · 2009-11-15 00:36:12Z

my guess is that your if/else statement isn't comparing correctly:

aData->getName() < items[root_index].theData

why not do

(*aData) < items[root_index].theData

??

The getName method would have to essentially return a copy of the object for your comparison to work.

Here is the Insert method I wrote for BST:

    /* Insert by node */
    template<class T>
    void Tree<T>::Insert(Node<T> *insertingNode)
    {
        Node<T> *y = NULL;
        Node<T> *x = &this->Root;

        while( x != NULL)
        {
            // y is used as a temp
            y = x;

            // given value less than current
            if(insertingNode->value < x->value)
            {
                // move to left of current
                x = x->ptrLeft;
            }
            else
            {
                // move to right of current
                x = x->ptrRight;
            }
        }

        // now, we're in place
        // parent of inserting value is last node of loop
        insertingNode->ptrParent = y;

        // if there is no node here, insert the root
        if (y == NULL)
        {
            Root = *insertingNode;
        }
        else
        {
            // Place inserting value accordingly
            if(insertingNode->value < y->value)
            {
                // Goes on the left
                y->ptrLeft = insertingNode;
            }
            else
            {
                // Goes on the right
                y->ptrRight = insertingNode;
            }
        }

    };

I dont understand how just dereferencing would make the BST any more balanced..I reposed and thanks for the help :)
probably the next biggest obstacle for you is that for every insertion, you'll have to shift all values to the left or right, depending on where you insert, and update your "root index". In a way, what you're working on is half and implementation of a quicksort algorithm. see: en.wikipedia.org/wiki/Quicksort
OK. The algorithm you are describing is similar to a heap insert?
your logic is still wrong, unfortunately. Try following the pseudocode here: highered.mcgraw-hill.com/sites/0070131511/student_view0/… if you'd like, I could post my implementation of a BST. it is templated, so it's quite different from yours.
Also, MIT OpenCourseWare has a lecture on BST v QuickSort here: ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/…

Collectives™ on Stack Overflow

Im stuck with filling my Array Based BST in C++

1 Answer 1

9 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Linked

Related