cp's OEIS Frontend

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).

%I A228153 #33 Dec 17 2018 09:14:31
%S A228153 0,2,5,8,12,16,20,24,25,30,35,40,44,49,50,54,56,59,62,64,68,73,79,85,
%T A228153 91,97,96,102,103,107,110,113,117,119,123,125,130,131,137,136,144,142,
%U A228153 151,148,157,154,163,160,170,177,184,180,191,188,197,196,204,204
%N 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).
%C A228153 The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).
%D A228153 D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).
%H A228153 Alois P. Heinz, <a href="/A228153/b228153.txt">Columns k = 1..3000, flattened</a>
%H A228153 R. C. Richards, <a href="http://dx.doi.org/10.1016/0020-0190(83)90085-6">Shape distribution of height-balanced trees</a>, Info. Proc. Lett., 17 (1983), 17-20.
%H A228153 Wikipedia, <a href="http://en.wikipedia.org/wiki/AVL_tree">AVL tree</a>
%H A228153 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%e A228153 In the (two) AVL trees of height 2 the 3 external nodes (leaves) have once depth 1 and twice depth 2:
%e A228153        o       o
%e A228153       / \     / \
%e A228153      o   1   1   o
%e A228153     / \         / \
%e A228153    2   2       2   2
%e A228153 so that the sum of depths is 5 for both trees.
%e A228153 Triangle begins:
%e A228153   0
%e A228153   . 2
%e A228153   . . 5 8
%e A228153   . . . . 12 16 20 24
%e A228153   . . . .  .  .  . 25 30 35 40 44 49 54 59 64
%e A228153   . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
%e A228153   . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...
%t A228153 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 *)
%o A228153 (MuPAD)
%o A228153 maxNods:=100: // max number of leaves (= external nodes)
%o A228153 // Triangle T for all AVL trees with <= maxNods leaves:
%o A228153 delete T:
%o A228153 // table T indexed [h, k] (h=height, k=number of leaves):
%o A228153 T[0, 1]:=0:
%o A228153 // A029837 indexed [k], min height of tree with k leaves:
%o A228153 A029837:=array(1..maxNods): A029837[1]:=0:
%o A228153 // A072649 indexed [k], 1+max height of AVL tree with k leaves:
%o A228153 A072649:=array(1..maxNods): A072649[1]:=1:
%o A228153 // A036289 indexed [h], max depthsum of all height h AVL trees:
%o A228153 A036289:=array(1..maxNods):
%o A228153 // A228155 indexed [k], max depthsum of all AVL trees with k leaves:
%o A228153 A228155:=array(1..maxNods): A228155[1]:=0:
%o A228153 for k from 2 to maxNods do:
%o A228153   A029837[k]:=maxNods: // try infinity for the min height
%o A228153   A072649[k]:=0:
%o A228153   A228155u:=0:
%o A228153   // Put together 2 AVL trees:
%o A228153   for kL from 1 to floor(k/2) do:
%o A228153     // kL leaves in the left tree
%o A228153     for hL from A029837[kL] to A072649[kL]-1 do:
%o A228153       for hR from max(hL-1, A029837[k-kL])
%o A228153                to min(hL+1, A072649[k-kL]-1) do:
%o A228153         // k-kL leaves in the right subtree
%o A228153         maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
%o A228153         A228155u:=max(maxDepthSum, A228155u):
%o A228153         h:=max(hL, hR)+1:
%o A228153         if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
%o A228153           T[h, k]:=maxDepthSum:
%o A228153         else
%o A228153           T[h, k]:=max(maxDepthSum, T[h, k]):
%o A228153         end_if:
%o A228153         A029837[k]:=min(h, A029837[k]):
%o A228153         if type(A036289[h]) <> DOM_INT then
%o A228153           A036289[h]:=maxDepthSum:
%o A228153         else
%o A228153           A036289[h]:=max(maxDepthSum, A036289[h]):
%o A228153         end_if:
%o A228153         A072649[k]:=max(h+1, A072649[k]):
%o A228153       end_for: // hR
%o A228153     end_for: // hL
%o A228153   end_for: // kL
%o A228153   A228155[k]:=A228155u:
%o A228153 end_for: // k
%Y A228153 Triangle read by rows gives: A228152.
%Y A228153 Row maxima give: n*2^n = A036289(n).
%Y A228153 Row minima give: A067331(n-1) for n>0 or A166106(n+2).
%Y A228153 Row lengths give: 1+A008466(n).
%Y A228153 Number of AVL trees read by rows gives: A143897.
%Y A228153 The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
%Y A228153 Column maxima give: A228155(k).
%Y A228153 Column heights give: A217710(k).
%Y A228153 Number of AVL trees read by columns gives: A217298.
%K A228153 nonn,tabf
%O A228153 1,2
%A A228153 _Herbert Eberle_, Aug 13 2013