Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

ziruz

binary tree depth

This topic is 5769 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

is a max depth of ~22 ok for an binary tree with 1024 items (inserted in random order)? or is the tree way to deep? // ziruz ------------------------------------------------------------ XL is comming soon @ http://ziruz.cjb.net/

Share this post


Link to post
Share on other sites
Advertisement
You can determine the # of nodes that you can store in a binary tree of a given level with this simple formula:

Max. # nodes = 2^Level - 1


# Levels Max. # of nodes
-------- ---------------
1 1
2 3
3 7
4 15
10 1023
11 2047



-Mike

Share this post


Link to post
Share on other sites
ok, i could figure out that my self but...
is it "normal" that a tree with 1024 randomly inserted items
get that deep?

//ziruz

------------------------------------------------------------
XL is comming soon @ http://ziruz.cjb.net/

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I don''t understand what your asking.

The best case senario is listed above, for that many nodes it has to be atleast that deep. For an unbalance tree it will be deeper. Does that help??

Cheers
Chris

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If the tree doesn''t need to be dynamically modified, you can sort the items and then creating a perfectly balanced tree is trivial (just pick the middle item for the root, and recursively create subtrees from the left and right elements). If the tree does need to change as it is being used, then look into using a red-black tree or splay tree or something like that. The STL provides a good implementation of a tree, usually a red-black tree, with the map object. You didn''t say what type of binary tree it is, or what it is being used for...

Share this post


Link to post
Share on other sites
ok, again...
i just wrote an binary tree template class
mostly for practice and also because i soon
will need a tree... i might be able to catch
all the data an sort it and then create a perfect
three... but i would like to not do that because
of some differen reasons (speed, and more...)
and my question was if it is very bad with an
tree that get that deep with that many items
without any specific balancing algo.
so is a 22 level tree very bad for 1024 items?


------------------------------------------------------------
XL is comming soon @ http://ziruz.cjb.net/

Share this post


Link to post
Share on other sites
Hmmz... I don''t know what you are trying to do, but if things are compleatly random your tree could grow to the depth of 1024 (however unlikely). I should also recommend a balanced tree structure. It''s often not a bad tradeoff to balance your tree and the most common thing, finding particular elements in the tree, will become very fast.



// Javelin
-- Why do something today when you can do it tomorrow... --

Share this post


Link to post
Share on other sites
If your tree is a completely ordinary binary search tree then adding randomly generated nodes of some measure (say 1024) can create all from some 10/11 to 1024 levels in the tree. If you consistently get about 22 then... did you forget to seed your randomiser? :o)

On another account, if you want a generic binary tree framework where it is comparatively easy to add your own tree types (i.e. red-black trees, etc.) then you may want to look at my binary search tree framework and related article at http://www.unprompted.com/hstuart/prog/. I am currently working on a more robust version that can handle m-ary trees as well, which, in my opinion, is looking a good deal more apparent to use.

quote:
Original post by daerid
Look into making your b-tree a balanced tree (I'd suggest using a Red-Black algorithm)



A Btree is a whole other data structure. Beware how you abbreviate. :o)


--
I am not a church numeral, I'm a free variable!

[edited by - muer on February 1, 2003 7:32:04 AM]

Share this post


Link to post
Share on other sites
It''s worth noting that a binary tree with 22 levels can hold 2^22 = 4,194,304 items. Offhand, I''d say that such a tree holding only 1024 items probably doesn''t look all that balanced ... It may also be worth noting that barring situations where the data is specifically tailored to suit a BST, it is most suitable where the data is distributed randomly. Sequential data is the BST''s bane.

As for the comment that a perfect BST may be generated from an array of data if it need not be dynamically modified: If this is the case, then it might be more efficient to just leave the data in array form (or to store the pointers in an array), sort the array, and do a plain old binary search on it. (This is, of course, a terrible solution if dynamic insertion is involved as it involves continuously resorting the array.)

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!