home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2344 < prev    next >
Encoding:
Text File  |  1992-11-06  |  3.2 KB  |  68 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!ukma!netsys!decwrl!ads.com!marcel
  3. From: marcel@ADS.COM (Marcel Schoppers)
  4. Subject: Re: #nodes in avg.tree of given depth?
  5. Message-ID: <1992Nov5.224938.25597@ads.com>
  6. Keywords: binary tree size
  7. Sender: Marcel Schoppers
  8. Organization: Advanced Decision Systems, Mtn. View, CA (415)960-7300
  9. References: <96222@netnews.upenn.edu>
  10. Date: Thu, 5 Nov 1992 22:49:38 GMT
  11. Lines: 55
  12.  
  13. >In article <96222@netnews.upenn.edu> rymon@linc.cis.upenn.edu (Ron Rymon)
  14. >  writes:
  15. >I second the naturality of random (uniformly distributed) binary trees of
  16. >depth at most d. However, the analysis of the NUMBER of such trees suggest
  17. >a way to draw such trees.
  18.  
  19. Hmmm, OK...  Here's what I'm up to.  I'm doing an analysis of the expected
  20. size of a certain kind of program that happens to be analyzable as a
  21. decision tree.  Hence binary trees are a suitable abstraction of those
  22. programs.  Read program size as number of nodes in the corresponding tree.
  23. We are told the number of world-states (or objects) that the decision tree
  24. must classify; call that number W.
  25.  
  26. It can be shown that on average (uniform distribution over all possible
  27. partitions of W objects) the W states to be classified will fall into
  28. O(W/log W) classes, i.e. that's how many leaves the binary tree should have.
  29. Hence we immediately know how many internal nodes it has.  Further, we also
  30. know (from Knuth) that the expected height/depth of the tree is
  31.     D = O( sqrt(W / log W) )
  32.  
  33. However, the real classification programs I am dealing with turn out to be
  34. very much smaller, i.e. they are not average, and I've managed to prove
  35. mathematically that the cause of their small size is that the programs contain
  36. dynamically bindable variables.  That results (at least for some domains I
  37. have analyzed) in trees that have
  38.     O( (log W / loglog W)^P )
  39. leaves, where P is something small like 2 or 3.
  40.  
  41. So, now I have an average-case estimate (way too large) and some actual-case
  42. figures (much smaller) and the restriction causing the difference (the
  43. existence of variables in the programs being modelled), and now want to find
  44. a way to do an average-case analysis for the *restricted* set of programs.
  45.  
  46. It turns out that the presence of variables in my programs has the following
  47. effect on tree structure:  the depth of the trees stays about the same, but
  48. the trees become much thinner "horizontally" because the variables effectively
  49. allow to replace a list of identical subtrees by only one such subtree (OK, so
  50. the depth of the list decreases by the number of subtrees in the list minus 1).
  51.  
  52. Hence, my first idea was to find out the number of nodes in the average tree
  53. of a fixed depth D.  The answer, O(2^D), for D = O( sqrt(W / log W) ) as above,
  54. would give me N = O(2 ^ sqrt(W / log W)) nodes, which is way too big, and so
  55. reveals that indeed, the restricted set of thinned trees I'm concerned about
  56. is very far away from being a uniformly distributed set of trees with depth D.
  57.  
  58. Obviously, I need to come up with a suitably restricted set of binary trees,
  59. and then figure out the expected number of nodes in that set as a function of:
  60. the known depth, the number of subtrees in each list, and the density (and
  61. placements?) of such lists.  (Such lists can be nested, i.e. a subtree in a
  62. list can contain another list.)
  63.  
  64. Marcel
  65.  
  66.  
  67.  
  68.