[comp.theory] Full Binary Trees

BURGARD@DBNINF5.BITNET (11/21/90)

I am interested in the following problem:

  What is the order of the average depth of the leafs of full binary
  trees with n leafs?

  Remarks:

  - A full binary tree is a binary tree with each node having
    outdegree either 2 or 0

  - The number of full binary trees with n leafs is the
    Catalan number C(n-1)

  - C(n)= 2n \over n / (n+1)

  - The average depth A(n,k) of the leafs of a full binary tree
    with n leafs and k leafs in the left subtree of the root is:

    A(n,k)= 1 + ( k*A(k) + (n-k)*A(n-k) ) / n

  - Thus the average depth A(n) of the leafs of a full binary tree
    with n leafs is:

    A(n)= 1+ \sum_{k=1}^{n-1} { f(n,k) * k*A(k) + (n-k)*A(n-k) ) } / n

    where f(n,k)= C(k-1)*C(n-1-k)/C(n-1).

  - trivial bounds for A(n):  O(log(n)) \leq A(n) \leq O(n)

  - Conjecture:  A(n) is sublinear, e.g. O(n^c) with c<1


Are there any results concerning this problem?

Thanks for the interest,

   -- Wolfram


Wolfram Burgard
Institut fuer Informatik III
Universitaet Bonn
BURGARD@DBNINF5.BITNET

nachum@m.cs.uiuc.edu (11/22/90)

/* Written  4:21 pm  Nov 20, 1990 by BURGARD@DBNINF5.BITNET in m.cs.uiuc.edu:comp.theory */
/* ---------- "Full Binary Trees" ---------- */
I am interested in the following problem:

  What is the order of the average depth of the leafs of full binary
  trees with n leafs?
  ...
  - Conjecture:  A(n) is sublinear, e.g. O(n^c) with c<1
  ...
/* End of text from m.cs.uiuc.edu:comp.theory */

Your conjecture is correct.  It is O(sqrt(n)), by results in Knuth's vol.
1, sect. 2.3.4.5 on "external path length".  (See also my paper with S.
Zaks, "Patterns in Trees", in Discrete Applied Math, vol. 25, pp. 241ff.,
result 3.5.1.)