arrays - 特定の高さの二分探索木の配列サイズを計算するには?

Question

配列を使用した二分探索木の実装に取り​​組んでいます。特定の高さを持つ BST の配列を作成する必要があります。そのサイズはどうやって計算するのですか？

Answer 1

バイナリヒープのようなインデックス化による実装について話していると思います。

配列に格納されたすべての頂点。この配列の最初の要素 - ルート。BST の頂点が配列の i 番目の要素である場合、左の息子はインデックス 2*i のセルに格納され、右の息子はインデックス 2*i+1 のセルに格納されます。メモリ内でのそのような表現のスキームを以下に示します。

特定の高さに対する木のサイズについて質問しています。高さ - ツリーのレベル数です。つまり、高さはルートから任意の葉までのパスの長さです。上の図では、BST の高さ = 2 です。

固定高さのツリーを格納するための配列のサイズをどのように計算しますか? 等比級数の和ですね。高さ = 0 のレベルには 1 つの要素があり、高さ = 1 の次のレベルには 2 つの要素があり、次のレベルには 4 つの要素があります。高さ = H のレベルには 2^H 要素があります。

高さ = H のツリーを格納するための配列サイズは、0 から H までのすべてのレベルを格納するのに十分なサイズです:
2^0 // 高さ = 0 のレベルのセル
+
2^1 // 高さ = 1 のレベルのセル
+...
+2^H = 2^(H+1)-1 ;

重要な注意 - 多くのプログラミング言語には、ゼロから始まる配列インデックスがあります。したがって、配列を次のようint tree[2^(H+1)-1]に宣言すると、要素に 0 から 2^(H+1)-2 の番号が付けられ、1 から 2^(H+1)-1 の番号が付けられます。インデックス 0 の要素は便利ではありません。0=2*0 であるため、「親 i、左の息子 2*i」という規則に違反します。つまり、配列の最初の要素がルートであると言うときは、tree[0] ではなく、tree[1] を意味します。tree[0] は無視してください。

最後に、高さ H の BST の required_array_size = calculate_size + zero_ignoring_shift = 2^(H+1)-1 +1 = 2^(H+1)