|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: how were the weights sum-ed ?''
by Logan on 2004-06-01 10:27:07 |
|
| The example is slightly misleading. The values in the internal nodes (in circles) are not intermediate results. They are the weighted path length for the subtree rooted at that node.
The weighted path length is the sum over all external nodes of each external node's weight multiplied by its distance from the root. Thus, for the left child of the top-most node, we have a value of 9: 1 * 2 + 2 * 2 + 3 * 1. For the entire tree, we have: 1 * 3 + 2 * 3 + 3 * 2 + 3 * 2 + 4 * 2 = 3 + 6 + 6 + 6 + 8 = 29.
|
| | [ reply | up | top ] |
|
|
|
|
|
|
