7

私は完全な二分木を持っています。つまり、ツリー内の各ノードはリーフノードであるか、2つの子を持ち、すべてのリーフノードは同じレベルにあります。各ノードには、深さ優先のインデックスがあります。

（たとえば、3つのレベルを持つツリーでは、ルートノードのインデックスは0、最初の子は1、最初の子の最初の子は2、最初の子の2番目の子は3、2番目の子は4、最初の子は4です。 2番目の子の2番目の子は5で、2番目の子の2番目の子はインデックス6です。

      0
    /   \
  1      4
 / \    / \
2   3  5   6

）。

ツリーのサイズ（ノード数/最大レベル）はわかっていますが、特定のノードのインデックスのみであり、そのレベル（つまりルートノードまでの距離）を計算する必要があります。これを最も効率的に行うにはどうすればよいですか？

4

7 に答える 7

10

この質問の解決を容易にする別の提案があります。

幅優先のインデックスでノードにラベルを付けると、O（1）時間の走査なしでレベルを計算できます。したがって、複数のクエリを実行している場合は、O（N）BFTを実行して、各クエリにO（1）時間で応答させることができます。

レベルの式は次のとおりです。

level = floor(log(index + 1))

ログがベース2にある場所

このツリーで試してみてください：

       0
     /    \
    /      \
   1        2
  / \      / \
 /   \    /   \
3     4  5     6

乾杯。

于 2015-06-30T20:04:35.083 に答える
6

i探しているインデックスをnノードの総数とします。

このアルゴリズムはあなたが望むことをします：

level = 0
while i != 0 do
    i--
    n = (n-1)/2
    i = i%n
    level++
done

0はルートのインデックスです。i = 0適切なレベルにある場合は、ルートを削除して2つのサブツリーを取得n = (n-1)/2し、ノードの数を更新して新しいツリー（古いツリーのサブツリー）i = i%nのみを選択します。良いサブツリー。

于 2012-05-23T14:19:38.443 に答える
3

木を直接歩くのは十分効率的だと思われます。

アルゴリズムの各ステップで、現在のノードのサブツリーのインデックスの範囲に注意してください。範囲の最初の値はルートノードであり、その後、前半は左側のサブツリーの範囲であり、後半は右側のサブツリーの範囲である必要があります。その後、ノードが見つかるまで再帰的に下に移動できます。

たとえば、15個の要素を持つ4レベルのツリーで検索してみましょう

                 (root node)(left elements)(right elements)
Starting range:  (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)
Go left       :  (1)(2 3 4)(5 6 7)
Go right      :  (5)(6)(7)
Found node, total depth 2

範囲の開始と終了を格納するためにいくつかの変数を使用して、単純なループでこれを行うことができるはずです。また、ポスト/プレ/インオーダートラバーサルを使用したり、0ではなく1からインデックスを開始したりするなど、いくつかの小さな変更を行う場合にも、これを簡単に適応させることができます。

于 2012-05-23T14:13:10.420 に答える
2

未テスト：

int LevelFromIndex( int index, int count)
{
    if (index == 0)
        return 0;
    if (index > (count - 1)/ 2)
        index -= (count - 1) / 2;
    return 1 + LevelFromIndex( index - 1, (count - 1) / 2);
}

countツリー内のノードの総数は次のとおりです。

于 2012-05-23T14:17:20.340 に答える
0

編集：試行番号1...はBFSでのみ機能します。

完全な二分木とは、ヒープのような構造を持つ二分木を意味する場合、次の式を使用してノードの親インデックスを計算できます。

parentIndex = (index-1)/2

したがって、<= 0になるまでその式を繰り返すことができます。ループするたびに、基本的にツリーのレベルが上がります。

編集：番号2を試みます。

私が考えることができる最善の方法は、O（n）であるO（index + log n）を取ることです。目的のインデックスに到達するまでDFSを実行し、次に、ルートに到達するまで親ポインターを使用してツリーを上昇し続け、上昇した回数を追跡します。これは、各ノードに親ポインターが存在することを前提としています。

于 2012-05-23T14:09:47.640 に答える
0

あなたが持っているのがインデックスだけであるならば、あなたは深さを見つけることができません。

次のようなツリーがあるとします。

    1
   / \
  2   5
 / \
3   4

インデックス3のノードの深さは2です。

次のようなツリーがあるとします。

  1
 / \
2   3
   / \
  4   5

インデックス3のノードの深さは1です。

インデックスを知っているだけでは、これら2つのツリーを区別することはできません。インデックスを知っているだけでは、ルートからの距離を見つける方法はありません。

編集：のように完全な二分木を意味する場合、すべての葉は同じ深さにあり、すべての親には2つの子がありますが、それでも深さを見つけることはできません。

これらの2つのツリーを比較します。

  1
 / \
2   3


      1
   /     \
  2       5
 / \     / \
3   4   6   7

ノード3の深さは、木の高さに応じて変化します。

編集2：ツリー全体の高さがわかっている場合は、次の再帰的アルゴリズムを使用できます。

def distanceFromRoot(index, rootIndex, treeHeight):
    if index == rootIndex:
        return 0
    leftIndex = rootIndex+1
    rightIndex = rootIndex + 2**treeHeight
    if index >= rightIndex:
        return 1 + distanceFromRoot(index, rightIndex, treeHeight-1)
    else:
        return 1 + distanceFromRoot(index, leftIndex, treeHeight-1)
于 2012-05-23T14:15:53.287 に答える
0

したがって、4つのレベルを持つそのようなツリーがあります。

          0             - 0th level
      /       \         
     1          8       - 1th level
   /  \       /  \      
  2    5     9    12    - 2th level
 / \   /\   / \   / \
3   4 6  7 10 11 13 14  - 3th level

ご覧のとおり、DFSでは左の子が常に最初にアクセスするため、左の各子のルートのインデックスは1つ増えます（左=ルート+ 1）。2番目のノードには、左側のサブツリーのサイズ（right = left + leftSize）によって増加した左側のノードのインデックスがあります。木の深さがわかれば、そのサイズを計算できます（サイズ= 2 ^深さ-1）。左側のサブツリーの深さが親の深さに等しい深さが1減少している限り、そのサイズ= 2 ^（parentDepth-1）-1。

これでアルゴリズムができました-左ノードのインデックスを計算し、右ノードのインデックスを計算します。ノードインデックスがその間にある場合は、左側のノードに移動します。そうでない場合は、右側のノードに移動します。

コード：

static int level(int index, int root, int treeDepth) {
        if (index == root)
            return 0;

        if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */)
            throw new Exception("Unable to find node");

        int left = root + 1;
        int right = left + (int)Math.Pow(2, treeDepth - 1) - 1;

        if (index == left || index == right)
            return 1;

        if (left < index && index < right)
            return 1 + level(index, left, treeDepth - 1);
        else
            return 1 + level(index, right, treeDepth - 1);
    }
于 2012-05-23T14:41:45.423 に答える