Binary Search Tree Using an array

Hello, i am trying to add items to a tree. I am finding no information in my book or the web about BST and arrays.
Since all i can find is pointer based i am trying to convert
that to array based and implement that. I am checking
if ( aData < items[parent].instanceData)
then add to the left or right . However, it seems all the items to be adding to the right.
The indexes are not in the right order either. I was told i need a helper function that knows the index. I dont know why i would need one.

driver

Code:

data aData; cout << "Database Of Great Computer Scientists\n\n"; database.insert(data("Ralston, Anthony")); database.insert(data("Liang, Li")); database.insert(data("Jones, Doug")); database.insert(data("Goble, Colin")); database.insert(data("Knuth, Donald")); database.insert(data("Kay, Alan")); database.insert(data("Von Neumann, John"));

Code:

void BST::insert (const data& aData) { if ( items[parent].empty ) { items[parent].instanceData = aData; items[parent].empty = false; size++; } else if ( aData < items[parent].instanceData) { if ( parent >= maxsize ) { this->expand(); } parent = (2 * parent)+ 1; this->insert(aData); } } else { if ( parent >= maxsize ) { this->expand(); } parent = (2 * parent)+ 2; this->insert(aData); } }

Code:

bool operator< (const data& d1, const data& d2) { if ( strcmp( d1.getName(), d2.getName() ) == 1 ) { return true; } else if ( strcmp( d1.getName(), d2.getName() ) == -1 ) { return false; } return false; }

is my logic off in the operator< function? it seems to want to add all items to the right.
Also, parent goes from 0 to 2 to 6 to 14
any help is much appreciated

Your operator < would work, but it sorted descending and was far longer than it should be:

Code:

bool operator < (const data& d1, const data& d2) { return d1.getName() < d2.getName(); }

I mean, you are using std::strings right since this is C++?

Code:

0 / \ / \ / \ 1 2 / \ / \ / \ / \ 3 4 5 6 / \ / \ / \ / \ 7 8 9 10 11 12 13 14

0 -> 2 -> 6 -> 14 is indeed down the right hand side.

I am suppose to store the names as char *
i tried your suggestion and it didn't add correctly. That could be because of my insert function.

Well if you're forced to not use std::strings then you want just this:

Code:

bool operator < (const data& d1, const data& d2) { return strcmp(d1.getName(), d2.getName()) < 0; }

If that doesn't work then the problem is elsewhere.
I'm highly suspicious of where 'parent' comes from and what it is set to for starters. It doesn't seem to be declared locally.

Unfortunately I think the whole way you're doing it is basically doomed :(. You can't store a tree with more than about 25-30 levels in an array this way, which can mean that even 30 items total can break it (assuming no balancing).
If you drop the binary-heap style (child=2*parent+k) indexing and store child indexes within each node instead, then it can work. This however simply trades the concept of storing and using pointers for storing and using indexes instead. The array then is little more than a pool allocator.

The better option is to simply learn and use pointers. If you're going to be a programmer then learning pointers is unaviodable.
You can drop the "this->" bits throughout that code.

Awesome, That worked. I am only adding 9 items so using this array shouldn't
be a problem. My parent index starts at zero. When it adds "Goble, Colin" at index 7 like it suppose to, to the left. The next name is "knuth, Donald" that adds to the right like it suppose to. It suppose to go to index 8 however, parent goes
from 7 to 16 and thats not what i want. My problem might be in my expand function?

Am i suppose to always be comparing the new item with the first parent? or the last parent that was added?

this is the order i am hoping to achieve.

Code:

<< "Database Of Great Computer Scientists\n\n"; database.insert(data("Ralston, Anthony")); database.insert(data("Liang, Li")); database.insert(data("Jones, Doug")); database.insert(data("Goble, Colin")); database.insert(data("Knuth, Donald")); database.insert(data("Kay, Alan")); database.insert(data("Von Neumann, John")); database.insert(data("Trigoboff, Michael")); database.insert(data("Turing, Alan"));

Required output...

Quote:

Ralston, Anthony 0
Liang, Li 1
Von Neumann, John 2
Jones, Doug 3
Trigoboff, Michael 5
Goble, Colin leaf 7
Knuth, Donald 8
Turing, Alan leaf 12
Kay, Alan leaf 17

I changed the code a bit from the first post.

Code:

void BST::insert (const data& aData) { if ( items[parent].empty ) { items[parent].instanceData = aData; items[parent].empty = false; size++; } else if ( aData < items[parent].instanceData) { parent = (2 * parent)+ 1; if(parent > maxsize) { this->expand(); } this->insert(aData); } else { parent = (2 * parent)+ 2; if(parent > maxsize) { this->expand(); } this->insert(aData); }

expand array.

Code:

void BST::expand() { item *swap = new item[size+1]; for ( int index = 0; index < size*2; index++ ) { if ( !items[index].empty ) { swap[index].instanceData = items[index].instanceData; swap[index].empty = false; } } maxsize += size; delete [] items; items = NULL; items = swap; }

Code:

BST::BST(int capacity) : size(0), parent(0), items(new item[capacity]) { maxsize = capacity; items->empty = true; }

Each insertion should always start at the first parent (the root).

Don't you have a buffer overrun in your expand function?:

Code:

item *swap = new item[size+1]; for ( int index = 0; index < size*2; index++ ) { if ( !items[index].empty )

You're only allocating one more than 'size' items but 'maxsize' is increased by 'size' which will typically be more than one, and you don't expand again until 'maxsize' is exceeded. So most of the time you'd be using memory off the end of the array.

What would you propose i do about that then?

Quote:

item *swap = new item[size*2];

for ( int index = 0; index < size; index++ )
{
if ( !items[index].empty )

iMalc, thanks for helping me.. I got the insert working. I also got the recursive part of the add working.

Code:

item *swap = new item[maxsize*2]; for ( int index = 0; index < maxsize; index++ ) { if ( !items[index].empty ) {

Quote:

Originally Posted by mrsirpoopsalot

iMalc, thanks for helping me.. I got the insert working. I also got the recursive part of the add working.

Code:

item *swap = new item[maxsize*2]; for ( int index = 0; index < maxsize; index++ ) { if ( !items[index].empty ) {

Yeah that looks fine now.

Thats good

I am trying to display the contents of the tree i think inorder.
What i am trying to do is print "leaf" for the leafs.
For what i understand is that in order for it to be a leaf left child needs to be null and so does rightchild

problem is it only prints one leaf.
i commented out the code that prints way to many leafs.

Code:

void BST::displayArrayOrder (ostream& out) const { out << ">>> array order:" << endl; displayHeaders(out); for(int index=0; index < maxsize+1; index++) { if (!items[index].empty) { out << left << setw(37) << items[index].instanceData; if(items[2 * index + 1 ].empty && items[2 * index + 2].empty) { out << left << setw(17) << "leaf"; } out << setw(21) << index << ' '; out << endl; } // if(items[2 * index + 1 ].empty && items[2 * index + 2].empty) // print way too many leafs //{ // out << left // << setw(17) << "leaf"; //} } }

You have two options. Just make a single loop over all positions in the array and output every non-empty item. No fancy child-parent calculations needed at all - very short code for this option.

OR

Write a recursive tree processing function that follows only the calculated child node positions which have actual children, and ignores the fact that items are even stored sequentially in memory.

You can't do both at once!