StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
12541710
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2012-09-22T07:24:56.413
FavoriteCount
0
LastActivityDate
2012-09-22T07:24:56.413
LastEditDate
LastEditorUserId
0
OwnerUserId
47984
ParentId
12529556
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
Let's call the minimum height required to fit <code>N</code> nodes in a binary tree <code>minheight(N)</code>. One way to derive a lower bound on the tree height for a given number <code>N</code> of nodes is to work from the other direction: given a tree of height <code>h</code>, what is the maximum number of nodes that can be packed into it? Let's call this function of height <code>maxnodes(h)</code>. Clearly the number of nodes on a binary tree of given height is maximised when the tree is full, i.e. when each internal node has 2 children. Induction will quickly show that <code>maxnodes(h) = 2^h - 1</code>. So, if we have <code>N</code> nodes, every <code>h</code> for which <code>maxnodes(h) >= N</code> is an upper bound for <code>minheight(N)</code>: that is, you could fit all <code>N</code> nodes on a tree of that height. Of all these upper bounds, the best (tightest) one will be the minimum. So what we want to find is the smallest <code>h</code> such that <pre><code>N <= maxnodes(h) = 2^h - 1 </code></pre> So how to find this smallest satisfying value of <code>h</code>? The important property of <code>maxnodes(h)</code> is that it is nondecreasing w.r.t. <code>h</code> (in fact it's strictly increasing, but nondecreasing is sufficient). What that means is that you can never fit more nodes into a full binary tree by reducing its height. (Obvious really but it helps to spell things out sometimes!) This makes rearranging the above equation to find the minimum value of <code>h</code> easy: <pre><code>2^h - 1 >= N 2^h >= N+1 # This is the RHS of your inequality, just flipped around h >= log2(N+1) # This step is only allowed because log(x) is nondecreasing </code></pre> <code>h</code> must be integer, so the smallest value of <code>h</code> satisfying <code>h >= log2(N+1)</code> is <code>RoundUp(log2(N+1))</code>. I find this to be the most useful way to describe the lower bound, but it can be used to derive the LHS of the inequality you're asking about. Starting from the 2nd equation in the previous block: <pre><code>2^h >= N+1 </code></pre> The set of <code>h</code> values that satisfy this inequality begins at <code>h = log2(N+1)</code> and stretches out to positive infinity. Since <code>h = log2(N+1)</code> is the minimum satisfying value in this set, anything lower must not satisfy the inequality, so in particular <code>h-1</code> will not satisfy it. If a <code>>=</code> inequality does not hold between two real (non-infinite) numbers then the corresponding <code><</code> inequality must hold, so: <pre><code>2^(h-1) < N+1 </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POBest case height for a binary tree with N internal nodes
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USj_random_hacker
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
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.