13

对于给定的二叉树，找到也是二叉搜索树的最大子树？

例子：

输入：

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

输出：

                   50
                  /   \
                 25   75
                / \   /
               15 35  65
4

7 回答 7

4

该答案之前包含基于链接/切割树的 O(n log n) 算法。这是一个更简单的O(n)解决方案。

核心是一个过程，它接受一个节点，唯一的最大 BSST 植根于它的左孩子，唯一的最大 BSST 植根于它的右孩子，以及指向这些 BSST 最左边和最右边元素的指针。它破坏其输入（可通过持久数据结构避免）并构造以给定节点为根的唯一最大 BSST 及其最小和最大元素。所有 BSST 节点都标注有后代的数量。和以前一样，从后序遍历中重复调用此过程。要恢复子树，请记住最大 BSST 的根；重建它只需要简单的遍历。

我将只处理左侧的 BSST；右边是对称的。如果左侧 BSST 的根大于新根，则移除整个子树，新根现在位于最左侧。否则，旧的最左边节点仍然是最左边的。从左侧 BSST 的最右侧节点开始向上移动，找到小于或等于根的第一个节点。它的右孩子必须被移除；现在请注意，由于 BST 属性，不需要其他节点！继续到左侧 BSST 的根，更新计数以反映删除。

这是 O(n) 的原因是，尽管存在循环，但原始树中的每条边本质上只遍历一次。

编辑：总的来说，经过的路径是 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
于 2010-07-03T16:46:28.053 回答
3

以前的算法（见修订）是O(n^2)- 我们可以O(n log n)通过注意到以下事实来概括它：

  1. 如果 b 是最大 BST 的根且b.left.value < b.value，则b.left也在 BST 中（对于 相同b.right.value ≥ b.value）
  2. 如果b是最大BST的根并且a也在BST中，那么a和b之间的每个节点都在BST中。

因此，如果 c 在 a 和 b 之间，并且 c 不在以 b 为根的 BST 中，则 a (due to (2.))也不是。使用这个事实，我们可以很容易地确定一个节点是否在以任何给定祖先为根的 BST 中。我们将通过将一个节点及其祖先列表以及如果该祖先确实是最大 BST 的根（我们'将调用此列表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)

于 2010-07-02T19:21:43.500 回答
2

有趣的问题！

我之前的尝试是愚蠢的错误！

这是另一个尝试（希望这次更正）。

我假设树是连接的。

假设对于树的每个节点 n，您有一组 n，S n的后代，其属性为

  • 对于 S n的每个成员 x，从 n 到 x 的唯一路径是二叉搜索树（它只是一条路径，但您仍然可以将其视为一棵树）。

  • 对于 x 的每个后代 y，使得从 n 到 y 的路径是一个 BST，y 在 S n中。

节点集 S n为您提供以 n 为根的最大 BST。

我们可以通过在树上进行深度优先搜索，并传入路径信息（从根到当前节点的路径）并通过沿路径回溯来更新路径中节点的集合来为每个节点构造 S n 。

当我们访问一个节点时，我们沿着路径走，并检查到目前为止走的那段路径是否满足 BST 属性。如果是这样，我们将当前节点添加到我们刚刚走过的路径的相应节点集合中。在违反 BST 属性的那一刻，我们停止行走。检查我们到目前为止走过的路径段是否是 BST 可以在 O(1) 时间内完成，对于每个节点的总处理时间为 O(path_length) 时间。

最后，每个节点都将填充其对应的 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);

}
于 2010-07-02T13:13:18.643 回答
1

二叉树中最大的二叉搜索树：

我们有两种方法可以解决这个问题，

i) 最大 BST 未诱导（从一个节点，它的所有子节点不需要满足 BST 条件）

ii) 最大 BST 诱导（从一个节点，它的所有子节点都将满足 BST 条件）

我们将在这里讨论最大的 BST（未诱导）。我们将采用自下而上的方法（后序遍历）来解决这个问题。

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 条件。我们将重复相同的操作直到 root。

e) 从每个节点返回两个对象。一个用于最后的最大 BST，另一个用于当前 BST 满足节点。因此，从每个节点（叶上方）（2+2）=4（左子树为 2，右子树为 2）对象将被比较并返回两个。

f) 来自根的最终最大节点对象将是最大的 BST

问题：

这种方法存在问题。在遵循这种方法时，如果子树不满足当前节点的 BST 条件，我们不能简单地忽略子树（即使它的节点数较少）。例如

 55
  \
   75
  /  \
 27  89
    /  \
   26  95
      /  \
     23  105
         /  \
        20  110

从叶子节点（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

于 2014-03-26T23:48:30.307 回答
0

如果您执行按顺序遍历，二叉搜索树将为您提供排序结果。因此，对整个二叉树进行中序遍历。最长的排序序列是你最大的二叉搜索子树。

  • 对元素进行顺序遍历（访问左、访问根、访问右）
  • 这样做时，获取节点数据，比较前一个节点数据是否小于下一个数据。如果是，则将计数器加 1。存储起始节点。
  • 当比较失败时，存储结束节点并将计数器重置为0
  • 将此信息（计数器，开始，结束）节点存储在数组结构中，以便稍后找到具有最大值的节点，这将为您提供最长的二叉搜索子树
于 2010-07-02T05:26:44.137 回答
0 
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。

于 2010-07-02T18:46:59.573 回答
0 
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)

只查看每个树节点一次，因此在 O(N) 中运行。

编辑： Crud，这不认为它可以遗漏子树的某些部分。当我阅读子树时，我假设“整个树都植根于某个节点”。我稍后可能会回来解决这个问题。

于 2010-07-03T00:15:58.690 回答