0
$\begingroup$

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an

"Example of a heap storing 13 entries with integer keys. The last position is the one storing entry (13,W)."

I've recreated the a similar image using qtree-tikz with my own depth and height calculations in the box on the left.

enter image description here

According to the book,

A heap T storing n entries has height $h = \lfloor \log n \rfloor$.

Justification: From the fact that T is complete, we know that the number of nodes in levels $0$ through $h-1$ of T is precisely $1+2+4+...+2^{h-1} = 2^{h}-1$, and that the number of nodes in level $h$ is at least 1 and at most $2^h$. Therefore

$n \geq 2^h -1 +1 = 2^h$ and $n \leq 2^h -1 +2^h = 2^{h+1} -1$.

Here is where I see a problem. I added the depths and heights for nodes at each level according to my understanding of trees in the box to the left of the tree. The example tree Figure 9.1 shown above obviously has 7 inner nodes and although depth level 3 would have 8 nodes, it is unfull at 6 nodes.

If I follow the "Justification", I end up with the following

  • "we know that the number of nodes in levels 0 through $h-1$ of T is $2^h-1$"

    $2^2 -1 = 3 \neq 7$.

  • but my understanding is that the $7$ would match the formula $2^3-1$, which means the $h$ referred to in the text must be $h=4$. But the $h =3$ from my understanding. Herein lies the problem.

I am being forced to conclude that there must be a missing level of sentinels, $2^3 -1 = 7$ and the only way to get a power of 3 in those formulas is to have a height of 4. But why on earth would the authors, who otherwise explain everything in detail, not make important piece of information explicit? Or, did I miss something? I would appreciate a thorough explanation to help me understand the proof. It also seems that the authors throw around the term "level" loosely, sometimes meaning depth level and sometimes meaning height level.

I should also mention that earlier in the book, on page 286, they provide a definition for the height of a tree without any examples (and it is a bit cryptic).

We next define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

  • If $p$ is a leaf, then the height of $p$ is $0$.
  • Otherwise, the height of $p$ is one more than the maximum of the heights of $p$'s children.
$\endgroup$
  • $\begingroup$ " levels $0$ through $h−1$", doesn't that indicate a tree of height $h-1$ rather than height $h$? $\endgroup$ – Hendrik Jan Sep 27 at 11:26
  • $\begingroup$ @HendrikJan Yes, my understanding is that it indicates the inner subtree (tree without the leaves), which must be full by definition of a complete heap. $\endgroup$ – Jonathan Komar Sep 27 at 12:16
1
$\begingroup$

You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric series:

$$ 2^0 + \cdots + 2^{h-1} = \frac{2^h - 1}{2 - 1} = 2^h - 1.$$

I think that a good rule of thumb for distinguishing between height and depth is that depth is the more useful one (the number of nodes on a complete level at depth $d$ is $2^d$, and a node's depth does not change as the tree grows), while the height $h$ is only really useful when looking at the tree as a whole (and is just the upper bound for depths).

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

After accepting Joppy's answer for clearing up my confusion, I'd like to elaborate with a more precise expression. I would have explained it in terms of depth, since we're starting with the root node:

$$ \sum_{d=0}^{h-1} 2^d = 2^h -1 \left. \right\vert \text{d is the depth (at each level) and h is the total height of a binary tree.} $$

This works because the number of nodes at each level is $2^d \left. \right\vert \text{where d is the depth of the current level}$.

$d = 0 \rightarrow 2^0 = 1$

$d = 1 \rightarrow 2^1 = 2$

$d = 2 \rightarrow 2^2 = 4$

$d = 3 \rightarrow 2^3 = 8$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.