Thread: Question about binary tree & heaps
View Single Post
•
•
Join Date: Sep 2004
Posts: 55
Reputation: apcxpc is an unknown quantity at this point 
Solved Threads: 0
apcxpc's Avatar
apcxpc apcxpc is offline Offline
Junior Poster in Training

Re: Question about binary tree & heaps

 
0
  #3
Sep 27th, 2005
For the Binary Tree Question, I know that the equation is true, from having tried examples of it.

e.g. from the following sketch, the sum would be: 1/8 + 1/8 + 1/4 + 1/2 = 1.
And the equality is true whenever the binary tree is full/complete, i.e. each node has 0 or 2 children.

http://www.apcx.3rror.com/images/binaryTreeSketch.JPG


But I don't know how to make a formal proof of this. Would greatly appreciate some help with this.
If I were to use induction, what would the base case, and n-th case be? Do I use an example of a complete/incomplete binary tree?
Reply With Quote