A228152 Triangle read by rows: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

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, 107, 113, 119, 125, 131, 136, 142, 148, 154, 160, 96, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 218, 225, 231

Offset: 0

Author

Herbert Eberle, Aug 13 2013

Keywords

• nonn
• tabf

Comments

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

Examples

			T(2,3) = 5 because in the (two) AVL trees of height 2 with 3 (leaf-) nodes one has depth 1 and two have 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 ...
		

References

• D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Links

• Alois P. Heinz, Rows n = 0..12, flattened
• R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
• Wikipedia, AVL tree
• Index entries for sequences related to rooted trees

Crossrefs

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.

Triangle read by columns gives: A228153.

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.

Programs

Maple

with(combinat): F:=fibonacci:
T:= proc(n, k) option remember; `if`(n<1, 0, max(seq([k+T(n-1,t)+
      T(n-1,k-t), k+T(n-1,t) +T(n-2,k-t)][], t=F(n+1)..k-1)))
    end:
seq(seq(T(n, k), k=F(n+2)..2^n), n=0..7);  # Alois P. Heinz, Aug 14 2013

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[T[n, k], {n, 0, maxNods}, {k, 1, maxNods}] // Flatten // Select[#, IntegerQ]& (* Jean-François Alcover, Aug 14 2013, translated and adapted from Herbert Eberle's MuPAD program *)

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