2

Im trying to insert into an array Based Binary Search tree.

I am not sure how i prevent overwriting data using left and right indexes...

Do i insert leftchild as tree[2 * i + 1] and rightchild as tree[2 * i + 2] ? I think it is for locating the position of a node given its name...

Thats my problem. Not knowing how to insert, recursively or iteratively(ive chosen recursively but it might be totally wrong).

BST::BST(int capacity) : items(new item[capacity]), size(0),
leftChild(0), rightChild(0), root_index(1)
{
 items->empty = true;
 maxSize = capacity-1;
}

Below is the insertion function. I have seen many that deal with Linked Lists implementations, But nothing array based! Here is my attempt:

void BST::insert(const data& aData)
{
if ( items[root_index].empty ) 
{
    items[root_index].theData = aData;// Get the data.
    items[root_index].empty = false;
    oldRoot.theData = aData;
} 
else  
{   
    if ( aData < items[root_index].theData )
    {
        leftChild = root_index * 2;
        if ( items[leftChild].empty )
        {
            items[leftChild].theData = aData;
            items[leftChild].empty = false;
        }//items->empty = true;
        else 
        {
            items[root_index].theData = items[leftChild].theData;
            this->insert(aData);
        }
    }
    else if ( items[root_index].theData < aData )
    {
        rightChild = root_index * 2 + 1;
        if ( items[rightChild].empty )
        {
            items[rightChild].theData = aData;
            items[rightChild].empty = false;
        }
        else//items->empty = true;
        {
            items[root_index].theData = items[rightChild].theData;      
            this->insert(aData);
        }

    }
    else return;
}
items[1].theData = oldRoot.theData;
}

What is correct?...Does anyone have any array based suggstions for inserting? I appear to be stuck in an infinite recursion

Improve this question
2
  • What's the actual goal you're trying to achieve? BST and a full-binary-tree-in-array (like in a binary heap) do not mix well unless you have the items to be inserted as a set and don't need to incrementally modify the BST. Commented Nov 15, 2009 at 22:45
  • I reposted and I think i am on a better track now. Thank you. Commented Nov 15, 2009 at 23:45

3 Answers 3

Reset to default
2
  • First have a look at what is the algorithm for inserting into BST (don't care about how it is implemented for arrays ...)
  • Once you understand how to insert, look at how you select left/right child of the current node and replace the algorithm with the way you need to access nodes in array based BST, meaning your (left,right) --> [2*i + 1],[2*i + 2] ... This calculation gives you the location of the node in the array

Have a look at the BST description at wikipedia, and the following example:

 /* Inserts the node pointed to by newNode into the subtree rooted at treeNode */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

Replace the way nodes and values are accessed in array, meaning replace treeNode->key, treeNode->left,treeNode->right with how you would access children nodes and the value in array (calculating the indexes of where in the array you store the values).

You will probably not need to pass Node* around because you'll be operating on an array, and probably you can pass around index to the current node and then just add to it to get the index for left/right children.

Btw (1), if it is array based it is probably not supposed to grow in memory, you create fixed size array at the beginning that is big enough to hold your elements and then you insert your elements into appropriate indexes of that array.

Btw (2), where did you get that comparison tree that you trying to achieve? How can Z be on left path from R? If you insert according to the same algorithm when you insert Z when R is already in tree you do (Z < R ? go left : go right) so Z would end up on right path from the root R (same as when you inserted the first A after R: (A < R ? go left : go right) you ended up inserting A on the left path ...)

Btw (3), it is correct as others mentioned, the final tree depends here on the order of insertion. The most inefficient way of generating tree would be to order elements and insert one by one because you would end up with linked list so traversal would take O(n) instead of O(logN). So if you have fixed set of elements you either pick random or consistently middle element.

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

Comments

1

I take it, then, that you want to be able to use elements in the array without having to re-arrange the array when you insert a new element?

Clearly, you would want to put the tree's root node at index zero. After that, you could use the path of descent to construct a number in binary. For instance, going down the tree left-left-right-left would give you the number 0b1011 = 11. (I used 1 for left and 0 for right) Add 1 to that, so this node would go at index 12. To descend further in the tree, use a logical or with the direction of descent.

Improve this answer

Comments

1

If you want to lay out a complete binary tree in an array, i_left=i_parent*2 and i_right=i_parent*2+1 works well (with i_root=1). BST are supposed to be efficiently updatable by modifying only the nodes along the path from the root to another node in the tree; location-independent explicit left and right subchild pointers (or indices) allow this, because shifting the location (or reuse of) of a subtree doesn't require a deep copy.

The only way it makes sense to have a packed binary search tree (with fixed locations for left and right subtrees based on parent's index, as above) is if the set is fixed; sort it and recurse, grabbing the middle of the sorted subrange and using it as the root of your BST-subtree.

Improve this answer

1 Comment

Take an implementation that uses pointers. Using explicit left/right subtree indices in the Node structure, instead of Node *left and n=n->left, you'd have int lefti and i=nodes[i].lefti. In other words, as long as you pass in the array base address, indices mean the same thing as pointers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.