login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A228153
Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).
3
0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 50, 54, 56, 59, 62, 64, 68, 73, 79, 85, 91, 97, 96, 102, 103, 107, 110, 113, 117, 119, 123, 125, 130, 131, 137, 136, 144, 142, 151, 148, 157, 154, 163, 160, 170, 177, 184, 180, 191, 188, 197, 196, 204, 204
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
In the (two) AVL trees of height 2 the 3 external nodes (leaves) have once depth 1 and twice depth 2:
o o
/ \ / \
o 1 1 o
/ \ / \
2 2 2 2
so that the sum of depths is 5 for both trees.
Triangle begins:
0
. 2
. . 5 8
. . . . 12 16 20 24
. . . . . . . 25 30 35 40 44 49 54 59 64
. . . . . . . . . . . . 50 56 62 68 73 79 85 91 97 102 ...
. . . . . . . . . . . . . . . . . . . . 96 103 ...
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[ Select[ Table[T[n, k], {n, A029837[k], A072649[k] - 1}], IntegerQ], {k, 1, maxNods}] // Flatten (* 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:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
A029837[k]:=maxNods: // try infinity for the min height
A072649[k]:=0:
A228155u:=0:
// Put together 2 AVL trees:
for kL from 1 to floor(k/2) do:
// kL leaves in the left tree
for hL from A029837[kL] to A072649[kL]-1 do:
for hR from max(hL-1, A029837[k-kL])
to min(hL+1, A072649[k-kL]-1) do:
// 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:
A029837[k]:=min(h, A029837[k]):
if type(A036289[h]) <> DOM_INT then
A036289[h]:=maxDepthSum:
else
A036289[h]:=max(maxDepthSum, A036289[h]):
end_if:
A072649[k]:=max(h+1, A072649[k]):
end_for: // hR
end_for: // hL
end_for: // kL
A228155[k]:=A228155u:
end_for: // k
CROSSREFS
Triangle read by rows gives: A228152.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.
Sequence in context: A087347 A062468 A365624 * A228152 A061717 A003314
KEYWORD
nonn,tabf
AUTHOR
Herbert Eberle, Aug 13 2013
STATUS
approved