How does an insert sort for an array BST work?

Question

I've tried to do it recursively..The parent integer varaible would is like i, conforming to the formula, 2*i +1 for leftChilds and 2*i +2 for the right.

void BST::insert(const data &aData)
{
    if ( items[Parent].empty ) 
    {
     items[Parent].theData = aData;
     items[Parent].empty = false;
    }
    else if ( aData < items[Parent].theData )
    {
     Parent = 2 * Parent + 1;
     if ( Parent >= maxSize ) this->reallocate();
     this->insert(aData);
    }
    else
    {
     Parent = (2 * rightChild++)+ 2;
     if ( Parent >= maxSize ) this->reallocate();
     this->insert(aData);
    }
}

It works fine when inserting items that are less than the original parent... But when i find something that is larger it all screws up :x

void BST::reallocate()
{
    item *new_array = new item[maxSize*2];

    for ( int array_index = 0; array_index < maxSize; array_index++ ) 
    {
     if ( ! items[array_index].empty )
     {
      new_array[array_index].theData = items[array_index].theData;
     }
    }
    maxSize *= 2;
    delete [] items;

    items = NULL;
    items = new_array;
}

Here is my ctor so no one gets anymore confused then i am:

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0),
leftChild(0), rightChild(0)
{
    items->empty = true;
    maxSize = capacity;
}
private:
    int size;  // size of the ever growing/expanding tree :)
    int Parent;
    int maxSize; 
    int leftChild;
    int rightChild;
    struct item
    {
     bool empty;
     data theData;
    };
    item *items;    // The tree array

The insertion function above is actually the best i can get..

                                 R
                                / \
                               /   \
                              /     \
                             L       X
                            / \     / \
                           J   V   K   T   <--The only out of place node.
                          / \   \
                         / NULL  \
                        G        /
                                P

When inserting, R, L, J, G, X, K, V, P, T in that order

Answer 1

I would suspect your problem is on this line:

    Parent = (2 * rightChild++)+ 2;

Why are you using rightChild here instead of (2 * Parent) + 2 ?

To make things clearer, you may want to add some simple inline functions to your class for computing the indexes of the left/right children and the parent, given an index:

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; }
inline int getRightChildIndex(int nodeNdx) { ... }
inline int getParentIndex(int nodeNdx) { ... }

You may also want to consider using the classes search() or find() method (I'm assuming it has one) to determine where to insert a new node. The search function should either return the index of an existing node (it's up to you to decide how to handle the insertion of duplicate values) or the index of where the new value should be inserted.