1
$\begingroup$

I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the author claims that the amount of bits needed to represent a tree of $n$ elements (without their values) is exactly $2n+1$.

According to my calculations, it's $2n-1$. Here they are:

  1. As in this representation every BST is represented as a complete tree, for the complete tree of height $k$ it has $2^{k+1}-1$ nodes.
  2. On average for $n$ nodes tree has a height of $log_2n$.
  3. Replacing the $k$ from the first list item with the average BST height from the second list item I received:

$$2^{log_2n+1}-1=2n-1$$

What am I missing in my calculations? Where do these 2 extra bits come from?

Thanks in advance for your answer!

$\endgroup$
0
$\begingroup$

You can count it like this:

Let $n$ be the original number of nodes

Each original node has 2 children after adding the external nodes.

So 1 bit for the original node and 2 for its children. Total $3n$ bits.

But we are over counting here because original node is child of one other original node. So we subtract $n$ and get $2n$.

But we over corrected the count because root node has no parent so we add back 1 bit.

$2n + 1$.

$\endgroup$
  • $\begingroup$ Thanks for your answer! This way it makes sense but using my calculations I still can't figure out why it lacks 2 additional bits (it should have some kind of explanation I hope). $\endgroup$ – ddnomad Oct 8 '16 at 17:26
  • $\begingroup$ You are dealing with full binary trees and not complete binary trees. Now, full binary trees of height $k$ don't necessarily have $2^{k+1} -1$ nodes. Also, you don't really want to use average height of binary trees in your calculations since you are trying to derive a formula which tells how many bits the representation will require given a tree with $n$ nodes. Its not about the height of the tree. $\endgroup$ – Pratik Deoghare Oct 8 '16 at 18:21

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.