login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 1..5000

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

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:

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

Column maxima of triangles A228152, A228153.

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

Column heights give: A217710(k).

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.

Sequence in context: A228152 A061717 A003314 * A070977 A134925 A184430

Adjacent sequences:  A228152 A228153 A228154 * A228156 A228157 A228158

KEYWORD

nonn

AUTHOR

Herbert Eberle, Aug 14 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 14:52 EST 2018. Contains 317352 sequences. (Running on oeis4.)