|
|
A228155
|
|
Maximal external path length of AVL trees with n (leaf-) nodes.
|
|
3
|
|
|
0, 2, 5, 8, 12, 16, 20, 25, 30, 35, 40, 44, 50, 56, 62, 68, 73, 79, 85, 91, 97, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 219, 227, 235, 243, 250, 257, 265, 273, 281, 289, 296, 304, 312, 320, 328, 335, 342, 349, 356
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).
|
|
REFERENCES
|
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).
|
|
LINKS
|
|
|
EXAMPLE
|
The (two) AVL trees with 3 (leaf-) nodes have one with depth 1 and two with depth 2:
o o
/ \ / \
o 1 1 o
/ \ / \
2 2 2 2
so a(3) = 5.
|
|
MATHEMATICA
|
maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[A228155[k], {k, 1, maxNods}] (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)
|
|
PROG
|
(MuPAD)
maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
// A036289 indexed [h], max depthsum of all height h AVL trees:
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
for k from 2 to maxNods do:
A029837[k]:=maxNods: // try infinity for the min height
A228155u:=0:
// Put together 2 AVL trees:
for kL from 1 to floor(k/2) do:
// kL leaves in the left tree
for hR from max(hL-1, A029837[k-kL])
// k-kL leaves in the right subtree
maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
A228155u:=max(maxDepthSum, A228155u):
h:=max(hL, hR)+1:
if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
T[h, k]:=maxDepthSum:
else
T[h, k]:=max(maxDepthSum, T[h, k]):
end_if:
if type(A036289[h]) <> DOM_INT then
else
end_if:
end_for: // hR
end_for: // hL
end_for: // kL
end_for: // k
|
|
CROSSREFS
|
Row maxima give: n*2^n = A036289(n).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of all binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Number of AVL trees read by columns gives: A217298.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|