ポストオーダー方式で列挙された完全な二分木があります。そのようなツリーの例は次のとおりです。
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
木の大きさはよくわかります。入力として単一の数値（関心のある頂点のID）を取り、単一の数値（親のID）も返す数式または単純なアルゴリズムを探しています。ツリーを上からトラバースして結果を取得するのは非常に簡単O(log n)です。より速い解決策はありますか？私は主に葉に興味があるので、特別な場合の解決策があれば、それも持ってきてください.
親インデックスは O(log * n) 時間と O(1) 空間で見つかります。
ここで、 log * nは反復対数を意味します。結果が 1 以下になる前に、対数関数を繰り返し適用する必要がある回数です。
実際には、O(1) 時間で、大きなルックアップ テーブル (ツリー内の各ノードの親インデックスを格納する) 用に O(n) スペースを確保できれば、さらに高速に実行できる可能性があります。
以下に、余分なスペースを必要としないいくつかのアルゴリズムをスケッチし、O(log n) 最悪の場合の時間、O(log log n) の予想時間、O(log log n) の最悪の場合の時間、および O(log * n) 最悪の場合の時間。これらは、完全な二分木のための順序付けされたインデックスの次のプロパティに基づいています。
i.プロパティ#1 と #2 は、ツリーのいくつかのノードの親ノードを取得するための単純なアルゴリズムを提供します。2 i -2形式のインデックスの場合は、を追加するだけです。他のノードについては、プロパティ #4 を繰り返し使用して、プロパティ #1 または #2 を満たすノードに到達し (いくつかの左側のサブツリーのサイズを減算することによって)、次に左端のパスにある親ノードを見つけて、以前のすべてを追加し直すことができます。減算値。また、プロパティ #3 を使用すると、差し引く必要があるサブツリーのサイズをすばやく見つけることができます。したがって、次のアルゴリズムがあります。211
((x+1) & x) != 0、((x+2) & (x+1)) != 0手順 2 を繰り返します。1ます。差額を積み上げます。((x+1) & x) == 0、 を掛けて2加算し1ます。そうでない場合((x+2) & (x+1)) == 0は、追加し1ます。たとえば、12(2 進形式の0b1100) はステップ 2 で に変換され0b0101、次に0b0010(または210 進数) に変換されます。累計差額は10です。ステップ #3 が を追加1し、ステップ #4 が追加さ 10れるため、結果は になり13ます。
その他の例: 10(in binary form 0b1010) は、ステップ #2 で0b0011(または3in decimal) に変換されます。ステップ #3 を 2 倍にして ( 6)、追加します1( 7)。ステップ #4 は累積差 ( 7) を加算するため、結果は になり14ます。
時間の複雑さは O(log n) ですが、すべての基本操作が O(1) 時間で実行される場合のみです。
時間の複雑さを改善するために、ステップ 2 の反復を複数回並行して実行できます。n/2インデックスの上位ビットを取得し、それらの人口数を計算できます。結果を残りの下位ビットに追加した後、合計がこれらの上位ビットにオーバーフローしない場合、O(log log n) の複雑さでこのアプローチを再帰的に適用できます。オーバーフローが発生した場合は、元のアルゴリズムに (ビット単位で) ロールバックできます。セットされたすべての下位ビットもオーバーフローとして扱われるべきであることに注意してください。したがって、結果の複雑さは O(log log n) expected timeです。
ビットごとにロールバックする代わりに、二分探索を使用してオーバーフローを処理できます。n/2オーバーフローが発生しないように、または ( index に関して0b00101111111111は) 選択されたゼロ以外の上位ビットの数が正確に になるように、いくつの上位ビット ( 未満) を選択するかを決定でき1ます。数のビット数が O(log log n) より大きい場合、2 番目のオーバーフローは発生しないため、このバイナリ検索手順を複数回適用する必要がないことに注意してください。したがって、結果の複雑さは O(log log n)最悪の場合の時間です。すべての基本操作は O(1) 時間で実行されると想定されます。いくつかの操作 (人口カウント、先行ゼロカウント) が O(log log n) 時間で実装される場合、時間の複雑さは O(log 2 log n) に増加します。
インデックスのビットを 2 つの等しいセットに分割する代わりに、別の戦略を使用できます。
0からに変化した最上位ビットにより、上位1/下位ビットの区切り点が決まります。((x+1) & x) != 0あり((x+2) & (x+1)) != 0、かつ である場合は、ステップ #1 から続行します。((x+1) & x) != 0との場合((x+2) & (x+1)) != 0は、これも右の子として処理します。((x+1) & x) == 0、 を掛けて2加算し1ます。そうでない場合((x+2) & (x+1)) == 0は、追加し1ます。ステップ 3 の条件が満たされている場合、これはステップ 2 で加算した結果、「分離」ビットにキャリーが発生したことを意味します。他の下位ビットは、元の個体数を超えることのできない数値を表します。この数値に設定されるビット数は、元の値の人口カウントの対数より大きくすることはできません。これは、各反復後のセット ビット数が、前の反復でのセット ビット数の最大対数であることを意味します。したがって、最悪の場合の時間計算量は O(log * n) です。これは O(1) に非常に近いです。たとえば、32 ビットの数値の場合、必要な反復回数は約 2 回以下です。
このアルゴリズムのすべてのステップは明らかなはずですが、おそらくステップ 5 を除いて、その正確性が証明されます。このステップは、人口カウントを追加すると「分離」ビットにキャリーが発生する場合にのみ実行されますが、上位ビットのみの人口カウントを追加すると、このキャリーは発生しません。「分離」ビットは、値 2 iに対応します。全ビットの個体数と上位ビットのみの個体数の差は最大でiです。したがって、ステップ 5 は少なくとも 2 i -i の値を扱います。この値にビットごとのアルゴリズムを適用してみましょう。2 ii-1 -i は、ビットが設定されるのに十分な大きさです。このビットをクリアし、ビット1の値に加算します0..i-2。2を引いたばかりなので、この値は少なくとも 2 i-1 -(i-1) です。i-1および を追加1。または、インデックスを 1 つ右に移動すると、少なくとも 2 i -i になります。この手順を繰り返すと、常にゼロ以外のビットが位置 に見つかりますi-1。0..i-1各ステップでは、ビット単位の値と の最も近い累乗の差が徐々に減少します2。この差が になると2、現在のノードが明らかに正しい子であるため、このビットごとのアルゴリズムを停止できます。このビットごとのアルゴリズムは常に同じ結果になるため、それをスキップして現在のノードを常に正しい子として処理することができます。
このアルゴリズムの C++ 実装を次に示します。詳細とその他のアルゴリズムについては、ideoneを参照してください。
uint32_t getMSBmask(const uint32_t x)
{ return 1 << getMSBindex(x); }
uint32_t notSimpleCase(const uint32_t x)
{ return ((x+1) & x) && ((x+2) & (x+1)); }
uint32_t parent(const uint32_t node)
{
uint32_t x = node;
uint32_t bit = x;
while ((x & bit) && notSimpleCase(x))
{
const uint32_t y = x + popcnt(x);
bit = getMSBmask(y & ~x);
const uint32_t mask = (bit << 1) - 1;
const uint32_t z = (x & mask) + popcnt(x & ~mask);
if (z == mask && (x & (bit << 1)))
return node + 1;
x = z;
}
if (notSimpleCase(x))
return node + 1;
else
return node + 1 + (((x+1) & x)? 0: x);
}
葉ノードの親のみを見つける必要がある場合、このアルゴリズムとコードは単純化される可能性があります。(イデオネ)。
uint32_t parent(const uint32_t node)
{
uint32_t x = node;
while (x > 2)
{
const uint32_t y = x + popcnt(x);
const uint32_t bit = getMSBmask(y & ~x);
const uint32_t mask = (bit << 1) - 1;
x = (x & mask) + popcnt(x & ~mask);
}
return node + 1 + (x == 1);
}
function getParent(node, size)
{
var rank = size, index = size;
while (rank > 0) {
var leftIndex = index - (rank + 1)/2;
var rightIndex = index - 1;
if (node == leftIndex || node == rightIndex) {
return index;
}
index = (node < leftIndex ? leftIndex : rightIndex);
rank = (rank - 1)/2;
}
}
ルートから開始し、ステップダウンするブランチを決定し、ノードが見つかるまで繰り返します。ランクは、同じレベルの左端のノードのインデックスです: 1, 3, 7, 15, ..., k^2 - k + 1.
入力パラメータは次のとおりです。
node– 親にしたいノードのインデックス。(1 ベース)size– ルート ノードのインデックス。15あなたの例では。例：
>>> r = []; for (var i = 1; i <= 15; i++) r.push(parent(i,15)); r;
[3, 3, 7, 6, 6, 7, 15, 10, 10, 14, 13, 13, 14, 15, undefined]
あなたのツリーを見てみましょう：
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
ラベルnを15-nに書き換えます。次に、次のようになります。
0
8 1
12 9 5 2
14 13 11 10 7 6 4 3
次のように書くこともできます
0
+8 +1
+4 +1 +4 +1
+2 +1 +2 +1 +2 +1 +2 +1
さて、あなたのためのパターンがあります。したがって、このラベル付け方式では、左の子は2^(i+1)親よりも大きく、iは子の身長であり、右の子は1親よりも大きいです。では、子供の身長や、右か左かを判断するにはどうすればよいでしょうか。
残念ながら、ノードへのパス全体、つまり対数時間を計算しないと、この情報を取得する方法を見つけることができません。ただし、ノードのラベルからノードへのパスを直接推測できます (ここでは高さ 3 のツリーについて説明します)。
nn == 0、それはルートです。n - 8 >= 0、ルートの左側のサブツリーにあります。設定しn = n-8ます。n - 8 < 0、ルートの右側のサブツリーにあります。設定しn = n-1ます。n == 0、それは最後のステップで発見されたサブツリーのルートです。n - 4 >= 0、最後のステップで発見されたサブツリーの左側のサブツリーにあります。設定n = n-4n - 4 < 0、最後のステップで発見されたサブツリーの右側のサブツリーにあります。設定しn = n-1ます。n-1 >= 0。ビット演算と-1s を使用してこれらすべてを行うことができ、実際には驚くほど高速になります (これを 1 兆ノード ツリーで計算すると、10 ノード ツリーの約 12 倍の時間がかかります (メモリの問題を無視します))。それはまだ対数時間になります。
とにかく、ラベルの高さと、それが左の子か右の子かがわかれば、前述の関係を使用して親のラベルを簡単に計算できます。
ノードの子の ID を照会できる場合は、いくつかの便利なことができます。
自明なケース 1: の場合x = size、それはルートです。
些細なケース 2:xがリーフの場合 (子 ID を照会して調べる)、 を試してくださいx + 1。x + 1がリーフ (子 ID の別のクエリ) でない場合はx、 の正しい子でしx + 1た。x + 1 が葉の場合x、 の左の子ですx + 2。
内部ノードの場合: の子xはx - 1(右の子) とx - (1 << height(x) - 1)(左の子、右の子は完全な二分木なので、ノードは 2 h -1 です) です。xしたがって、との差を使用してleft_child(x)、 の高さを決定xできheight(x) =ctz(x - left_child(x))ます:
したがって、の親は (iff ) であるか、または(そうでない場合) の親です。1 << heightctzxx + 1right_child(x + 1) == xx
x + (x - left_child(x)) * 2
ID を計算するだけではうまくいきませんが、一定時間内にノードの子を要求できると仮定すると、これは一定時間アルゴリズムです。