Binary Trees

[drakaza]

Hey,

I've got a question regarding BSP's
I have read a few documents on the internet that show how you make one with tips and all, but they say that an unbalanced tree is bad
and it grows or something like that....

How is this so?

If you are doing 1 polygon per node, then you are going to have 'N' nodes no matter how the tree is sorted...

Thanks for any input

[DFrey]

I think what they trying to say when they say an unbalanced tree grows, is that when making the tree, if it should become unbalanced, it will tend to grow faster on the unbalanced side. In other words, a slightly unbalanced tree at the beginning can very easily turn into an extremely unbalanced tree in the end.

Oh, and generally, each node of the BSP has 1 splitting plane not 1 polygon.



[This message has been edited by DFrey (edited 07-19-2000).]

[drakaza]

Thanks very much for replying

The question I was leading up to is:

Does the balance of the tree affect anything? Performance/Stability, or anything like that?
Or is it just the "appearance" of the tree?

[Kilam Malik]

An unbalanced tree has the problem of long access time. A balanced tree with 15 items has the depth of 4 walking from the root node. The worst case of a completely unbalanced tree has the depth of 15. So if you search for a specific position in tree it will be faster in a balanced tree.

[DFrey]

Ditto.

[drakaza]

Thanks heaps!!

It all makes sense to me now