Whether array indexing should start at 0 or at 1 comes up every now and then. Especially when programming language proponents argue. (It was once a hot topic between Fortran and C proponents, for example.)
I'm firmly in the zero camp... except when it comes to binary search trees stored in an array, then I insist on indexing starting at 1. The reason is this:
Upper, red numbers indicate the index to the node, if the tree were to use array representation. They increment from top to bottom (and on each row, from left to right).
The lower, blue numbers indicate the value in the node, or equivalently the sort order of the node. They increment strictly from left to right, this being a binary search tree.
The green numbers indicate path from the root node, with 0 left and 1 right, each descent adding a new binary digit to the right.
If you prepend a binary 1 to each binary path (in green) from root to a node, you get the binary representation of the target node index (in red). Including to the root node itself, 1.
If you have N levels, and therefore \$2^N-1\$ nodes, and use \$i\$ for the (red) node index, and \$k\$ for the (blue) node sort orders, \$1 \le i, k \le 2^N - 1\$, then
$$\begin{aligned}
k(i, N) &= \left( i - 2^{\lfloor \log_2 i \rfloor} \right) 2^{N - \lfloor \log_2 i \rfloor} + 2^{N - \lfloor \log_2 i \rfloor - 1} \\
i(k, N) &= \frac{G\left(k + 2^N\right) - 1}{2} \\
\end{aligned}$$
where \$G(x)\$ is the largest odd multiplier of \$x\$, i.e.
$$G(x) = \left\lbrace \begin{matrix}
x, & \text{if } x \text{ is odd} \\
G(x/2), & \text{if } x \text{ is even} \\
\end{matrix} \right.$$
Furthermore, the index (red) for the bottom-rightmost node is \$2^N-1\$, and the index of the leftmost node on level \$n\$, \$1 \le n \le N\$, is \$2^{n-1}\$, with the node index incrementing by \$2^n\$ to the next node on the right on that same level, and the index of the rightmost node is \$2^n-1\$.
(The above formulae tell you, for example, how to convert a sorted array (of \$2^N-1\$ elements) to a perfect binary search tree, and vice versa, using direct assignments in a single pass over the source array.)
You can find a lot more very easy mappings, but really, only when the indexing starts at 1. If you start the indexing at 0, one would think it just adds some \$+1\$ and \$-1\$ above (which is true), but it is much harder to derive the formulae, then. (I know, because I derived all these myself from scratch in 2016. I'm sure someone else discovered all these before me, I don't claim to be the discoverer; I'm just saying that switching to one-based indexing was the trick that helped me discover these.)
For those interested in the integer sequences involved, \$G(x)\$ is
OEIS A000265, \$k(i,N)\$ is a variant of
OEIS A131987, and \$i(k,N)\$ is a variant of
OEIS A101279.
Home
Help
Search
Login
Register
