Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!ucsd!ucbvax!DBNINF5.BITNET!BURGARD
From: BURGARD@DBNINF5.BITNET
Newsgroups: comp.theory
Subject: Full Binary Trees
Message-ID: <9011202221.AA08268@irt.watson.ibm.com>
Date: 20 Nov 90 22:21:00 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: BURGARD%DBNINF5.BITNET@VM1.NoDak.EDU
Lines: 43

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