Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>With your definition of perfectly balanced, all the variation in structure happens at the deepest level of the tree, so you only need to worry about that one level.</p> <p>A maximal balanced tree with height h will have 2^(h-1) leaves - e.g. for height 1, the only leaf is the root. These are all at the deepest level.</p> <p>A minimal balanced tree with height h has only one node at the deepest level.</p> <p>The number of ways you can construct a perfectly balanced binary tree is therefore the same as the number of ways you can have between 1 and 2^(h-1) nodes at the deepest level.</p> <p>There are 2^(h-1) nodes that may or may not be present at that level (a combinations problem, not permutations), so you get 2^(2^(h-1)) possiblilities, of which only one (the "none" case) is invalid.</p> <p>So I think your answer is (2^(2^(h-1)))-1. So if you can determine the correct h...</p> <p>That's assuming a binary <em>search</em> tree (with item values unique and in order), so the binary tree is fully determined by the choice of which deepest-level nodes are present. Otherwise, you multiply that by the number of permutations of the sequence of values.</p> <p>Take care with my definition of h - a zero-height tree would have no nodes at all, and give a nonsense result - sqrt(2)-1 is an irrational answer in at least two senses.</p> <p><strong>EDIT</strong></p> <p>Marcs comment made me think some more. For a particular height I think my answer is right. The problem is that a particular height allows various different numbers of total nodes, because it allows various different numbers of nodes in that deepest layer. So I can't get the correct answer for one particular node count this way. So... lets try again...</p> <p>If our tree has height h, it can have at most (2^h)-1 nodes in total. Excluding the deepest level, it has (2^(h-1))-1 nodes - all of which must be present.</p> <p>We have c-((2^(h-1))-1) nodes at the deepest level, and we get to choose where to put those nodes from the 2^(h-1) possible positions at the deepest level. I use c for count, because I want to define...</p> <pre><code>n = 2^(h-1) k = c-((2^(h-1))-1) </code></pre> <p>answer = <a href="http://en.wikipedia.org/wiki/Binomial_coefficient" rel="nofollow">n choose k</a></p> <p>I still haven't derived h from c - it should be the floor of the base 2 logarithm, but I have that out-by-one-somewhere feeling.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow many ways to build a perfectly balanced tree?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSteve314
    1. USSteve314
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COThank you for your answer, but i tried that formula and it does not work :( The structure is not variable.. only the order of input. First input must be 8. Second input can bei 4 or 12. Third input can be 4 or 12 or 2 or 6 or 10 or 14, depending on what you chose before.
      singulars
      1. PO
      1. USMarc
    2. CO@Marc - given that only "perfectly" balanced trees are valid, and if the tree is a binary search tree, the order of inputs is only relevant to the degree that the structure can vary. In a comment somewhere, you said not all leaves were at the deepest level - some can be at the next level up. That's the same variation of structure I'm describing above - the minimum variation of structure that allows for e.g. a tree of size 14. Each variation I allow for can arise (and will arise) by varying the insertion order.
      singulars
      1. PO
      1. USSteve314
    3. CO@Marc - some arrangements of the tree may be generated by more than one ordering of the insertions - if you're counting input orderings rather than resulting tree arrangements, that's the only way I can see my answer being wrong - but then again, I've already made at least one daft mistake ;-)
      singulars
      1. PO
      1. USSteve314
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload