#### Archived

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

# binary tree and number of leafs.

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

## Recommended Posts

I read that for minimize the number of leafs of a BSP tree, the best way is to take the polygons that cut the least possible of other polygons. What is the same as to maximize the tree height (generally the chosen polygon put the remaining polygons in one side). I don''t agree with that. For a binary tree which have a height equal to n where n is the number of nodes, the number of leafs is n+1. For a balanced tree, the height is equal to E( ln n/ln 2) where E is the whole part. Then the number of leafs is equal to 2^E( ln n/ln 2). However E( ln n/ln 2) <= ln n/ln 2 then 2^E(ln n/ln 2) <= 2^(ln n/ln 2) then 2^E(ln n/ln 2) <= n (or n+1). Then I think the best way is to have a balanced tree (the best way between the two I consider). What do you think ? Do I make a mistake ? !o)

##### Share on other sites
There is n+1 leafs in a binary tree where n is the number of nodes. Sorry for the absurdity question...

!o)

EDIT: In fact, in a BSP tree, we must to minimize the number of polygons of the leafs.

[edited by - Chuck3d on April 16, 2004 5:51:05 AM]

##### Share on other sites
You are wrong in saying that choosing a polygon so that all other polygons are on one side only will minimize the number of cuts : cutting occurs when a polygon is on both sides of the separation plane, it has nothing to do with the side of the plane non-cut polygons are on.

Your best bet would be to set two goals in your sparation plane choice method : have a heuristic that chooses the plane depending on both the tree unbalance it causes and the number of cuts it causes.

Victor Nicollet, INT13 game programmer

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633731
• Total Posts
3013582
×