二分木を配列で持つときのインデックスづけについて

二分木は一次元の配列として表現できます。例えば、インデックス0をルートとして、xの左の子は2*x+1,右の子は 2*x+2といった具合です。

ところで、このインデックスづけは1.「どの子のインデックスも他の子やルートと被らない」という必須の性質と、2.「配列に隙間がない（あっても定数サイズ）」というよい性質を持ちます。このことを簡単に確認してみましょう。(自明だという人も多いと思いますが、自分は式が天下り的に与えられて悩みました)

まず1.についてとは単調増加で、かつでとる整数値がそれぞれ(でない)奇数と偶数であるため成り立つことが分かります。また2.についてはとより、インデックスが小さいほうから敷き詰められていくため、こちらも成り立つことが分かります。

これを頭に入れておくと、いざ使うときに「式何だっけ？」とならずに済みます。またルートを1、左の子をx << 1、右の子をx << 1 | 1とするようなインデックスづけも正当であることが分かります。