Binary Trees

[G'n'R]

Hi All,

I have been trying out the binary tree tutorial on this site. I ahve
got it working but i have a few questions/observations. Here is the thing:



1. I added 10000 elements using a for loop and used the loop
counter as key value. I got a stack overflow at 9960 each time.

2. I adden 1000000 elements using the rand function. This
work perfectly.

3. I went out on a limb and added 4000000 elements also
using the rand function. The program never finished.


I am wondering what one can expect out of binary trees and
if there are notible different ways in implementing them. I know
there is in linked list. e.g is 4000000 elements to much? or should they be able to handle that. And has any one got any tips or suggenstions on how to implement and use them.

G'n'R

[quzah]

Without seeing your code, one can only speculate. Binary trees are basicly just linked lists (or that's how I'd implement it anyway) where you have a left and a right pointer and some value.

struct node
{
    struct node *left, *right;
    <type> data;
};

Basicly you just go down the list, if you're greater than the value, you go to one side, if you're less than, you go to the other.

Quzah.

[Nick]

When you add the elements in increasing order
to a binary tree you get what basically is a list.
The stack on the delete tree method would have 100000 stack frames which could overflow.

2. I adden 1000000 elements using the rand function. This
work perfectly.

One of my books derives this but the average height of a
randomally built binary tree is about 2lg n so that
makes the height of this tree on average about 40.

The problem is inherent in the basic binary tree. You will
probably want to learn more about balenced trees.

[G'n'R]

Hello,

Thanks for the info. Balanced tree?? Sounds interesting. I'll see if i can find som good info and tutorials on it. The one in the tutorial on this site, what would you call that? (Trying to get everything perspective here )

Regards,
G'n'R