Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The inequality <code>2^(h-1) &lt; N + 1 &lt;= 2^h</code> demonstrates that, for a given height <code>h</code>, there is a range of node quantities that will have <code>h</code> as a minimum height in common. This is indicative of the property: all binary trees containing <em>N</em> nodes will have a height of at least log(<em>N</em>) rounded up to the next integer.</p> <p>For example, a tree with either <code>4, 5, 6 or 7</code> nodes can have at best a minimum height of <code>3</code>. One less than this range, and you can have a tree of height <code>2</code>; one more and the best you can do is a height of <code>4</code>. If we map out the minimum height for a tree that grows from <code>3</code> nodes to <code>8</code> nodes using the base 2 logarithms for <em>N</em> and round up, the inequality becomes clear:</p> <pre><code>log(3) = 1.58 -&gt; 2 [lower bound] log(4) = 2 -&gt; 3 [2^(h-1)] log(5) = 2.32 -&gt; 3 log(6) = 2.58 -&gt; 3 log(7) = 2.81 -&gt; 3 log(8) = 3 -&gt; 4 [2^h | upper bound] </code></pre> <p>It might be useful to notice that the range (made up of <code>N+1</code> different quantities) is directly related to the number of external nodes for a given tree. Take a tree with <code>3</code> nodes and having a height of <code>2</code>:</p> <pre><code> * / \ * * </code></pre> <p>add one node to this tree,</p> <pre><code> * * * * / \ / \ / \ / \ * * or * * or * * or * * / \ / \ * * * * </code></pre> <p>and regardless of where you place it, the height will increase by 1. We can then keep creating leaf nodes without changing the height until the tree contains 7 nodes in total, at which point, any further additions will increase the minimum possible height once more:</p> <pre><code> * / \ * * / \ / \ * * * * </code></pre> <p>Originally, <em>N</em> was equal to <code>3</code> nodes, which meant <code>N+1 = 4</code> and we saw that there were <code>4</code> quantities that had a common minimum height.</p> <p>If you need more information, I suggest you look up the properties of complete and balanced binary trees.</p>
    singulars
    1. This table or related slice is empty.
    1. POBest case height for a binary tree with N internal nodes
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UStojrobinson
    1. UStojrobinson
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POBest case height for a binary tree with N internal nodes
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. This table or related slice is empty.
 

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