(Header Value)/(Leaf Value) ratio in L.d.a.s: Paradox?
headers 5 13 21 29 37 45 53 61 69 77 85 ... 805 ...
leaves 3 9 15 21 27 33 39 45 51 57 63 ... 603 ...
- l.d.a. headers, 5[8], are sparser than leaf nodes, 0[3] (see above)
- so you'd
suppose that the (header value)/(leaf value) for l.d.a.s would average 4/3
- in fact, weighted averages on all l.d.a.s of a given length is 1
- e.g. sss: 2^6*3/(2^3*3^4) = 8/27 weight 1
- (ssb): 2^7*3/(2^3*3^4) = 16/27 weight 3
- (sbb): 2^8*3/(2^3*3^4) = 32/27 weight 3
- bbb: 2^9*3/(2^3*3^4) = 64/27 weight 1
- whose weighted average is ((8+3*16+3*32+64)/27)/8 = (216/27)/8 = 1.0000.
- it's NOT a paradox --- it's a MISTAKE
- should assess at constant power-of-2 depths, not constant l.d.a. length depths
- computer run to 2^25 results in cumulative header/leaf ratio at 1.3295 (increasing
from 1 and approaching the expected 4/3)
- Explanation: the abstract tree is unbalanced: the "b" side reaches higher numbers
first, so "s" rich l.d.a.s are overweighted in equi-length l.d.a. calculations
next slide
return to slide index
skip past paradoxes