2
$\begingroup$

I was binary indexed trees and I came across this article. One part of the justification was the following:

Given that the (binary search tree) tree is perfectly balanced, a node N will have exactly $2^{i}-1$ children on each side, where $i$ is the position of the first 1-bit in N, starting from 0, and counting from least significant to most significant. For example, for $N=11000$, we have $i=3$. For $N=111$, we have $i = 0$. This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$ (similarly for the right side). The “minus 1″ is there because we can’t count $N$ itself as being a child of $N$.

First off, I believe that the authors claim that

"This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$"

is not entirely accurate, as for example, in the following BBST:

      4
   /     \
  2       6
 / \     / \
1   3   5   7

The left children of node 6 do not contain every number lower than 6. Nevertheless, the formula $2^i - 1$ still holds true. Why does this work?

$\endgroup$
2
$\begingroup$

Since I'm still learning proof techniques, this is a good practice for me too. Please verify the solution yourself. We shall prove this with a series of lemma.

Lemma 1. A perfectly balanced tree with height $h$ would have $n = 2^{h+1}-1$ nodes.

Proof. Trivial proof by induction.

Lemma 2. A perfectly balanced indexed binary search tree have root with value $2^h$.

Proof. By lemma 1, there are $2^h-1$ nodes on the left subtree of the root. By constraint of binary search tree, the root element will have value $(2^h-1)+1=2^h$.

Lemma 3. In a perfectly balanced indexed binary search tree, any node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$ and right child with value $k+2^{h-1}$.

Proof. Due to the properties of the tree, the value of the left child of $A$ is the value of $A$ itself, which is $k$, subtracted by the number of nodes on the right subtree of the left child, which is $2^{h-1}-1$ from lemma 1, added by one. This is trivial upon drawing out such a tree, which I shall not include here. Hence, the value of left child is $k-(2^{h-1}-1)-1=k-2^{h-1}$. A similar proof will suffice for the value of right child.

Theorem. In a perfectly balanced binary search tree with height $h$, any node $A$ will have exactly $2^i−1$ children on each side, where $i$ is the position of the first $1$-bit in the value of node $A$, starting from $0$, and counting from least significant to most significant.

Proof. We shall prove by induction from root down to leaves. By lemma 2, the root value is $2^h$, which binary representation is

$$ 1\overbrace{0\dots0}^h $$

The position of the first $1$-bit will therefore be in the $h$ position. Substituting $i=h$, we have $2^h-1$ children on each side, which agree with lemma 1.

Now, we assume any node $A$ satisfy the stated theorem. By lemma 3, the left child of node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$. By lemma 1, we know that $i=h$, so it suffice to show that the position of the first $1$-bit in $k-2^{h-1}$ appears a bit before that in $k$. In other words, we can assume that the first $1$-bit in $k$ appears at position $h$, and we need to show that the first $1$-bit in $k-2^{h-1}$ appears at position $h-1$.

In binary, we can represent $k$ as

$$ 1\dots1\overbrace{0\dots0}^{h} $$

and we are subtracting it from $2^{h-1}$, as represented by

$$ 1\overbrace{0\dots0}^{h-1} $$

Since $k$ is all zeros in the first $h$ bits, subtracting by $2^{h-1}$ will cause bit $h$ to become $0$ and bit $h-1$ to become $1$, which retain the stated proposition. A similar prove can be done for the right child of $A$. In addition, one also need to prove the termination case to complete this prove, which I also leave out here.

$\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.