algorithm - Mathematical proof for a binary tree -
i not hiding part of homework i've tried enough before posting here.
so...
need prove binary tree node k have left child on 2k , right child on 2k + 1 position. i've proved induction.
now need prove binary tree node k have parent on (floor)(k/2)
position. took 2 cases.
tried induction well. it's true tree of 3 nodes.
if it's true node k i'll prove node k + 1.
- if node k+1 shares parent node k it's true.
- if node k+1 has difference parent node k....
i trying make general binary tree types won't me use induction assumption. assume maybe i'll have use proved before child's position.
any help?
so you've proven kth node has children @ 2k , 2k+1. let's divide children 2 cases, , odd.
for children they're located @ i=2k k. can see that means parent @ k, or i/2, or floor(i/2).
for odd children they're located @ i=2k+1 k. can see means parent @ k. floor(i/2) in case equals floor(k+1/2), equals floor(k) = k since k integer, here parent node @ floor(i/2) also.
since set of odd , children make children, parent of ith child floor(i/2)
qed? sorry if isn't rigorous or formal enough..
Comments
Post a Comment