完全なANDバイナリツリーの最大および最小インデックス？

Question

は、私は私がこれをoverthinkingてるかどうかわからないんだけど、私は一般的なケースソリューション:(を考えることはできません

Answer 1

限り我々は右のサブツリー内の大きい値と小さい値を持つノードを格納してどのノードでも左サブツリーの場合、Bottom Rightのノードが最大値を持ち、Bottom Leftのノードが最小値を持つことになります。

これで、ノードを見つける必要があります。 Complete and Full BSTまた、配列に格納されているため、インデックスはノード上に均等に分散されますes。だからここでTop to BottomとLeft to Right1からnまでのノードにインデックスを割り当てようとすると、nノードがあればそれを移動する必要があります。私たちは与えられた木のインデックスを作成している場合

、だからここ

      1 
         / \ 
         2  3 
        / \ / \ 
        4  5 6  7 
        /\   ^^^-------------Largest value 
        8 9 
Smallest value----^^^ 

8インデックスが最も小さい値を持つことになると 7率を有するノードが最も大きな値を持つことになる有するノード。

ここで問題はそれを見つける方法です。それで、レベルがlのツリーを持っているとしたら、最大値のインデックスは2^level - 1となり、最小値は2^levelインデックスになります。total_nodes = 2^level-1の場合は、ここで最大値を取得するインデックスが間違った答えを与えることがあります。だから、levelを別の方法で計算する必要があるのは、total_nodes = n+1です。

int level = (int)(Math.ceil (Math.log(n)/Math.log(2))); //For index of smallest value; 
int smallest_index = (int) Math.pow (2,level); 

level = (int)(Math.ceil (Math.log(n+1)/Math.log(2))); //For index of largest value; 
int largest_index = (int) Math.pow (2,level) - 1; 

Answer 2

ザンケットの回答は基本的には正しいですが、最終的に言われている通り私は不快になります。 2つの丸められた（！）ログの丸められた（！）比率は、のほうに丸められません。ちょうどは、意図した整数よりわずかに高いと言いますか？そして、ceilはそれをすべて持ち歩くでしょう。たぶんそれはうまくいくかもしれませんが、設計上ではなく事実上ではあります。

これは、ビット単位の算術の観点から、このようなことを考える/心配する必要なしに、「きれいに」記述することもできます。すべてが整数のままなので、推論するのが簡単です。

最も低い項目のインデックスは、nに存在する2の最大累乗であるため、最も高い設定ビットです。 Javaでは、そこにそのためにも機能です：Integer.highestOneBitは、あるいは我々はそれを書くことができます：

int highestOneBit(int x) { 
    x |= x >> 16; 
    x |= x >> 8; 
    x |= x >> 4; 
    x |= x >> 2; 
    x |= x >> 1; 
    return x^(x >>> 1); 
} 

そして今、我々は

indexOfLowest = highestOneBit(n); 
indexOfHighest = highestOneBit(n + 1) - 1; 

を持っているこれはまだ1索引（未使用のインデックス0を残して）を前提とし、すべて0にインデックスを付けるために1だけオフセットすることができます。