algorithm - 特定の二分木について、最大の二分探索部分木を見つける

Question

特定の二分木について、二分探索木でもある最大の部分木を見つけますか?

例：

入力：

                   10
               /         \
             50           150
            /  \         /   \
          25    75     200    20
         / \   / \    /  \    / \
        15 35 65 30  120 135 155 250

出力：

score 4 · Accepted Answer

この回答には、以前はリンク/カットツリーに基づく O(n log n) アルゴリズムが含まれていました。これは、より単純なO(n)ソリューションです。

コアは、ノード、その左の子をルートとする一意の最大 BSST、右の子をルートとする一意の最大 BSST、およびこれらの BSST の左端と右端の要素へのポインタを受け入れるプロシージャです。入力を破棄し (永続的なデータ構造で回避可能)、指定されたノードをルートとする一意の最大 BSST を最小要素と最大要素と共に構築します。すべての BSST ノードには、子孫の数の注釈が付けられます。前述のように、このプロシージャはポストオーダートラバーサルから繰り返し呼び出されます。サブツリーを復元するには、最大の BSST のルートを覚えておいてください。それを再構築するには、単純なトラバーサルのみが必要です。

左の BSST のみを扱います。右は対称です。左の BSST のルートが新しいルートよりも大きい場合、サブツリー全体が削除され、新しいルートが最も左になります。それ以外の場合、古い左端のノードは依然として左端のままです。左の BSST の右端のノードから始めて上に移動し、ルート以下の最初のノードを見つけます。その右の子を削除する必要があります。BST プロパティにより、他のノードに移動する必要がないことに注意してください。左の BSST のルートに進み、削除を反映するようにカウントを更新します。

これが O(n) である理由は、ループにもかかわらず、元のツリーの各エッジが本質的に 1 回だけトラバースされるためです。

編集: まとめて、トラバースされたパスは、左のスパインと右のスパインを除いて、BST の最大直線パスです。たとえば、入力では

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / \             / \
    /   \           /   \
   /     \         /     \
  B       F       J       N
 / \     / \     / \     / \
A   C   E   G   I   K   M   O

各エッジがトラバースされる再帰呼び出しは次のとおりです。

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / h             h \
    /   h           h   \
   /     h         h     \
  B       F       J       N
 / d     d h     h l     l \
A   C   E   G   I   K   M   O

score 3 · Accepted Answer

以前のアルゴリズム(リビジョンを参照)は、次の事実に注目するO(n^2)ことで一般化できます。O(n log n)

b が最大の BST のルートであり、である場合、b.left.value < b.valueもb.leftBST に含まれます ( についても同じb.right.value ≥ b.value) 。
b が最大 BST のルートであり、a も BST 内にある場合、a と b の間のすべてのノードは BST 内にあります。

したがって、c が a と b の間にあり、c が b をルートとする BST にない場合、((2.) により) a もありません。この事実を使用して、ノードが特定の祖先によってルート化された BST にあるかどうかを簡単に判断できます。これを行うには、ノードをその先祖のリストと一緒に関数に渡し、実際にその先祖が最大の BST のルートである場合に現在の子ノードが満たす必要がある関連する最小値/最大値 (we'このリストを呼び出しますancestorList）。潜在的な根のコレクション全体をoverallRootsList

次のように potentialRoot という構造体を定義しましょう。

各potentialRootには次の値が含まれます:
* node : BST のルートとして検討しているノード
* minValue および maxValue : ノードによってルート化された BST の一部となるために別のノードが収まる必要がある範囲(ノードごとに異なる)
* subNodes : ノードをルートとする最大の BST 内の残りのノードのリスト

疑似コードは次のようになります (言及されているすべてのリストは、潜在的なルートのリストであることに注意してください)。

FindLargestBST(node, ancestorList):
    leftList, rightList = empty lists
    for each potentialRoot in ancestorList:
        if potentialRoot.minValue < node.Value ≤ potentialRoot.maxValue:
            add node to potentialRoot.subNodes (due to (1.))
            (note that the following copies contain references, not copies, of subNodes)
            add copy of potentialRoot to leftList, setting maxValue = node.Value
            add copy of potentialRoot to rightList, setting minValue = node.Value

    add the potentialRoot (node, -∞, +∞) to leftList, rightList, and overallRootsList
    FindLargestBST(node.left, leftList)
    FindLargestBST(node.right, rightList)

最後overallRootsListに、n潜在的なルートのリストがあり、それぞれにサブノードのリストがあります。サブノードリストが最大のものは BST です。

には < treeHeight 値があるためancestorList、(ツリーのバランスが取れていると仮定して) アルゴリズムは次のように実行されます。O(n log n)

score 2 · Accepted Answer

興味深い質問です！

私の以前の試みはばかげて間違っていました！

これが別の試みです（今回は正しいことを願っています）。

ツリーが接続されていると仮定します。

ツリーの各ノード n について、次のプロパティを持つn の子孫のセット S _{nがあるとします。}

_{S n}の各メンバー x について、n から x への一意のパスは二分探索木です (これは単なるパスですが、ツリーと見なすこともできます)。
n から y へのパスが BST であるような x のすべての子孫 y について、y は S _nにあります。

ノード S _nのセットは、nをルートとする最大の BST を提供します。

ツリーで深さ優先検索を実行し、パス情報 (ルートから現在のノードまでのパス) を渡し、パスに沿ってバックトラックすることでパス内のノードのセットを更新することにより、各ノードのS _nを構築できます。

ノードにアクセスすると、パスをたどり、これまでにたどったパスのセグメントに対して BST プロパティが満たされているかどうかを確認します。その場合、現在のノードを、今歩いたパスのノードの対応するセットに追加します。BST プロパティが侵害された瞬間にパスを停止します。これまでに歩いたパスセグメントが BST であるかどうかのチェックは、ノードごとに O(path_length) 時間の合計処理時間に対して、O(1) 時間で実行できます。

最後に、各ノードには対応する S _nが入力されます。_{ここでツリーをたどって、S n}の最大値を持つノードを選択できます。

これにかかる時間は、ノードの深さの合計 (最悪の場合) であり、平均的な場合は O(nlogn) です ( http://www.toves.org/books/のセクション 5.2.4 を参照)。 data/ch05-trees/index.html ) ですが、最悪の場合 O(n^2) になります。

おそらく、セットを更新するより賢明な方法は、最悪の場合の時間の短縮を保証します。

疑似コードは次のようになります。

static Tree void LargestBST(Tree t)
{
    LargestBST(t, new List<Pair>());
    // Walk the tree and return the largest subtree with max |S_n|.
}

static Tree LargestBST(Tree t, List<Pair> path)
{
    if (t == null) return;

    t.Set.Add(t.Value);

    int value = t.Value;
    int maxVal = value;
    int minVal = value;

    foreach (Pair p in path)
    {
        if (p.isRight)
        {
            if (minVal < p.node.Value)
            {
                break;
            }
        }

        if (!p.isRight)
        {
            if (maxVal > p.node.Value)
            {
                break;
            }
        }

        p.node.Set.Add(t.Value);

        if (p.node.Value <= minVal)
        {
            minVal = p.node.Value;
        }

        if (p.node.Value >= maxVal)
        {
            maxVal = p.node.Value;
        }
    }

    Pair pl = new Pair();
    pl.node = t;
    pl.isRight = false;

    path.Insert(0, pl);
    LargestBST(t.Left, path);

    path.RemoveAt(0);

    Pair pr = new Pair();
    pr.node = t;
    pr.isRight = true;

    path.Insert(0, pr);

    LargestBST(t.Right, path);

    path.RemoveAt(0);

}

score 1 · Accepted Answer

二分木における最大の二分探索木:

この問題にアプローチするには 2 つの方法があります。

i) 誘導されない最大の BST (ノードから、そのすべての子が BST 条件を満たす必要はない)

ii) 誘導される最大の BST (ノードから、そのすべての子が BST 条件を満たす)

ここでは、最大の BST(Not Induced) について説明します。これを解決するために、ボトムアップアプローチ (ポストオーダートラバーサル) に従います。

a) 葉ノードに到達する

b) ツリーノード (リーフから) は、次のフィールドを持つ TreeNodeHelper オブジェクトを返します。

public static class TreeNodeHelper {
        TreeNode node;
        int nodes;
        Integer maxValue;
        Integer minValue;
        boolean isBST;


        public TreeNodeHelper() {}

        public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {
            this.node = node;
            this.nodes = nodes;
            this.maxValue = maxValue;
            this.minValue = minValue;
            this.isBST = isBST;
        }      
    }

c) 最初は葉ノードから、 nodes=1,isBST=true,minValue=maxValue=node.data . さらに、BST条件を満たす場合、ノード数が増加します。

d) これを利用して、現在のノードで BST の状態を確認します。そして、ルートまで同じことを繰り返します。

e) 各ノードから 2 つのオブジェクトが返されます。1 つは最後の最大 BST 用で、もう 1 つは現在の BST を満たすノード用です。したがって、各ノード (葉の上) (2+2)=4 (左側のサブツリーに 2 つ、右側のサブツリーに 2 つ) のオブジェクトが比較され、2 つが返されます。

f) ルートからの最終的な最大ノードオブジェクトは、最大の BST になります。

問題：

このアプローチには問題があります。このアプローチに従いながら、サブツリーが現在のノードで BST 条件を満たさない場合、サブツリーを単純に無視することはできません (ノードの数が少ない場合でも)。例えば

リーフノード (20,110) から、オブジェクトはノード (105) でテストされ、条件を満たします。しかし、ノード (95) に到達すると、リーフノード (20) は BST 条件を満たしません。この解決策は BST (非誘導) のためのものであるため、条件を満たしているノード (105) とノード (110) を無視してはなりません。そのため、ノード (95) から再びバックトラックして BST 条件をテストし、それらのノード (105、110) をキャッチする必要があります。

この実装の完全なコードは、このリンクで入手できます

https://github.com/dineshappavoo/Implementation/tree/master/LARGEST_BST_IN_BT_NOT_INDUCED_VER1.0

score 0 · Accepted Answer

IN-ORDER Traversal を実行すると、二分探索木によってソートされた結果が得られます。したがって、バイナリツリー全体に対して順序どおりのトラバーサルを実行します。最長のソート済みシーケンスは、最大の二分探索サブツリーです。

要素を順不同に走査する (VISIT LEFT、VISIT ROOT、VISIT RIGHT)
そうしている間に、ノードデータを取得し、前のノードデータが次のデータより少ないかどうかを比較します。その場合、カウンターを 1 増やします。開始ノードを保存します。
比較が失敗した場合、終了ノードを保存し、カウンターを 0 にリセットします。
この情報 (カウンター、開始、終了) ノードを配列構造に格納して、後で最大値を持つノードを見つけ、最長の二分探索サブツリーを取得します。

score 0 · Accepted Answer

root(Tree L A R) = A

MaxBST(NULL) = (true, 0, NULL)
MaxBST(Tree L A R as T) = 
  let
    # Look at both children
    (L_is_BST, L_size, L_sub) = MaxBST(L)
    (R_is_BST, R_size, R_sub) = MaxBST(R)
  in
  # If they're both good, then this node might be good too
  if L_is_BST and R_is_BST and (L == NULL or root(L) < A) and (R == NULL or A < root(R))
  then (true, 1 + L_size + R_size, T)
  else
       # This node is no good, so give back the best our children had to offer
       (false, max(L_size, R_size), if L_size > R_size then L_sub else R_sub)

各ツリーノードを 1 回だけ参照するため、O(N) で実行されます。

編集：ひどい、これはサブツリーの一部を除外できるとは考えていません。サブツリーを読んだとき、「ツリー全体が何らかのノードに根ざしている」と想定しました。後でこれを修正するために戻ってくるかもしれません。

score 0 · Accepted Answer

GetLargestSortedBinarySubtree(thisNode, ref OverallBestTree)
    if thisNode == null
        Return null
    LeftLargest = GetLargestSortedBinarySubtree(thisNode.LeftNode, ref OverallBestTree)
    RightLargest = GetLargestSortedBinarySubtree(thisNode.RightNode, ref OverallBestTree)
    if LeftLargest.Max < thisNode.Value & RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, RightLargest)
    else if LeftLargest.Max < thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, null)
    else if RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(null, thisNode.Value, RightLargest)
    else
        currentBestTree = new BinaryTree(null, thisNode.Value, null)
    if (currentBestTree.Size > OverallBestTree.Size)
        OverallBestTree = currentBestTree
    return currentBestTree

BlueRaja が指摘したように、このアルゴリズムは正しくありません。

本当はと呼ぶべきGetLargestSortedBinarySubtreeThatCanBeRecursivelyConstructedFromMaximalSortedSubtreesです。

algorithm - 特定の二分木について、最大の二分探索部分木を見つける

7 に答える 7

Related

Reference