0

これは、バイナリ ツリー内の 2 つのノードの最も低い共通の祖先を非再帰的に見つけるために思いついたアルゴリズムです。基本的な戦略は次のとおりです。

  1. 辞書/ハッシュテーブルを使用してツリーを保存します。各キーと値のペアは、ノードとその親を表します。
  2. 2 つのノードのそれぞれから始めて、各ノードの値を表す変数をその親の値に設定し、通過した値をハッシュセット (2 つのノードごとに 1 つ) に格納することによって、ツリーを上っていきます。
  3. 次の条件のいずれかが満たされると、検索は完了します。(a) 2 つのノードの値が等しい。または (b) 2 つのパスが互いに交差するとき (つまり、ノード 1 のトラバースされた値のハッシュセットにノード 2 の現在の値が含まれる、またはその逆)。または (c) 渡されたノードがツリーに存在しません (この場合、アルゴリズムは終了し、-1 を返します)。

私の理解では、アルゴリズムの最悪の場合の時間と空間の複雑さは O(log(n)) です。これは、ハッシュセットに 2 * 以上の高さのトラバーサルを行ったり、2 * 以上の高さの値を格納したりする必要がないためです (そして、ハッシュセットとツリー辞書のルックアップ時間は O(1)) です。

以下は私のコード（C＃）です。私の分析が正しいかどうか、またはこれを行うためのより効率的な（非再帰的な）方法があるかどうかを教えてください：

int LowestCommonAncestor(int value1, int value2, Dictionary<int, int> tree)
{
    var value1Visited = new HashSet<int>();
    var value2Visited = new HashSet<int>();
    while (true)
    {
        if (value1 == value2) return value1;
        if (value1Visited.Contains(value2)) return value2;
        if (value2Visited.Contains(value1)) return value1;

        int nextValue1;
        int nextValue2;

        if (tree.TryGetValue(value1, out nextValue1))
        {
            //Walk node 1 up the tree:
            value1 = nextValue1;
            value1Visited.Add(value1);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }

        if (tree.TryGetValue(value2, out nextValue2))
        {
            //Walk node 2 up the tree:
            value2 = nextValue2;
            value2Visited.Add(value2);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }
    }
}
4

3 に答える 3

0

2 つのハッシュ セットは必要ありません。

  1. 1 つのノードの祖先を 1 つのハッシュ セットに集めます。
  2. 2 番目のノードから上に移動し、その祖先のそれぞれで、ステップ 1 で収集されたパスに 2 番目の現在の祖先が含まれているかどうかを確認します。最初の一般的なもので停止します。

D がツリーの最大深度であるため、複雑さは O(D) の最悪の場合の複雑さです。

N - ノード数 - ツリーがリストで縮退された場合の最悪のケースの複雑さ。ノードの 1 つがこのリストの先頭であり、もう 1 つが末尾です。

ツリーのバランスがとれている場合、D=log(N) - ログのベースはノードの子孫の数です (バイナリ - log2、ターナリ - log3 など)。

于 2017-01-01T22:28:48.607 に答える
0

  1. 各ノードからルートまで上って、その深さを測定します

  2. 浅いノードと同じ深さに到達するまで、深いノードからパスを上に移動します。

  3. 両方のノードからのパスを上に移動します (つまり、両方のパスで同じ深さを維持します)。

于 2017-01-01T21:58:47.793 に答える