If you want to make money online : Register now

[Solved]: Worst case bisection of binary tree

, , No Comments
Problem Detail: 

My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.

Asked By : mkraemerx

Answered By : hengxin

Consider a simple binary tree $T$ with only 4 nodes: The root of $T$ is $A$. $A$ has a left child $B$ which has two children $C$ and $D$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42617

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback