查找 BST 中所有键在给定范围内的子树

Question

我在最近的一次采访中被问到这个问题：给定一个 BST，其节点包含一个整数作为值，找到其节点落在整数 X（最小值）和 Y（最大值）之间的所有子树，其中 X

我已经解决了这个问题的变体，例如 - 打印给定范围内的 BST 键。但是无法弄清楚这一点，因为它涉及找到满足非常特定约束的主要 graph/tree 的所有连接子图。感谢任何 pointers/help/pseudo 代码。

已添加注释 -

问题将节点的数据结构定义为具有左指针、右指针和整数值。无法标记节点。
被要求在 Java 中解决这个问题。
当我说 subtree/subgraph 时，我指的是一组相连的节点，而不是不相交节点的列表。对困惑感到抱歉。

Answer 1

这很容易解决。对于不重叠的子树，我包含了一个标记字段，每个节点都初始化为 false。

算法如下：

使用DFS方法从根开始遍历BST。现在如果在 DFS 中遇到一个节点，它没有被标记并且它满足约束（落在 X 和 Y 之间），那么有一个以该节点为根的子树的解决方案，但我们不知道该子树有多大？所以我们执行以下操作：

将其左右子节点传递给另一个方法检查，它将执行以下操作：

遍历以该节点为根的子树，只要满足约束且遇到的节点未标记，就以DFS方式遍历。一旦违反任何一个条件，则 return.

现在，可以在已标记的顶点上调用原始 DFS 方法，但 if 条件将计算为 false。至此，目标达成。

我使用 JAVA 语言解决了它，条件是键位于 10 和 21（不包括）之间。这是代码：

还有一点，如果在 以 X 为根的子树 之后没有打印任何内容，则它表示具有单个节点的子树。

class BST
{
 public Node insert(Node x,int key)
 {
     if(x==null)
      return new Node(key,null,null,false);
     else if(key>x.key)
     {
         x.right=insert(x.right,key);
         return x;
     }
     else if(key<x.key)
     {
         x.left=insert(x.left,key);
         return x;
     }
     else {x.key=key;return x;}
 }

 public void DFS(Node x)
 {
     if(x==null)
     return;
     if(x.marked==false&&x.key<21&&x.key>10)
     {
         System.out.println("Subtree rooted at "+x.key+" with childs as");
         x.marked=true;
         check(x.left);
         check(x.right);
     }
     DFS(x.left);
     DFS(x.right);

 }
 public void check(Node ch)
 {
     if(ch==null)
      return;
     if(ch.marked==false&&ch.key<21&&ch.key>10)
     {
         System.out.println(ch.key);
         ch.marked=true;
         check(ch.left);
         check(ch.right);
     }
     else return;

 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     Node root=null;
     root=tree1.insert(root,14);
     root=tree1.insert(root,16);
     root=tree1.insert(root,5);
     root=tree1.insert(root,3);
     root=tree1.insert(root,12);
     root=tree1.insert(root,10);
     root=tree1.insert(root,13);
     root=tree1.insert(root,20);
     root=tree1.insert(root,18);
     root=tree1.insert(root,23);   
     root=tree1.insert(root,15);
     tree1.DFS(root);
 } 
}
class Node
{
 Node left,right;
 int key;
 boolean marked;
 Node(int key,Node left,Node right,boolean b)
 {
  b=false;   
  this.key=key;
  this.left=left;
  this.right=right;
 }
}

如有任何疑问，欢迎随时咨询。

Answer 2

具体的解决方案取决于子树的定义。考虑以下 BST：

并且我们想要找到 [4,8] 范围内的子树。很明显4节点属于输出。但是另一半树呢？如果一个子树引用一个节点及其所有 children，那么这就是整个结果。如果子树实际上是输入节点的子集，则节点 5 和 8 属于结果，但它们与 3 和 9 节点的连接必须被剥离离开。

无论如何，下面的算法都可以处理。预处理器定义 WHOLE_SUBTREES 定义子树是否是具有所有 children.

的完整子组件

static List<BSTNode> FindSubtreesInRange(BSTNode root, int rangeMin, int rangeMax)
{
    var result = new List<BSTNode>();
    if (IsTreeWithinRange(root, rangeMin, rangeMax, int.MinValue, int.MaxValue, result))
        result.Add(root);
    return result;
}

static bool IsTreeWithinRange(BSTNode root, int rangeMin, int rangeMax, int treeRangeMin, int treeRangeMax, List<BSTNode> resultList)
{
    if (treeRangeMin >= rangeMin && treeRangeMax <= rangeMax)
        return true;
    if ( treeRangeMin > rangeMax || treeRangeMax < rangeMin)
        return false;

    if (root.Key < rangeMin)
    {
        if (root.Right != null && IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
            resultList.Add(root.Right);
        return false;
    }

    if (root.Key > rangeMax)
    {
        if (root.Left != null && IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
            resultList.Add(root.Left);
        return false;
    }

    if (root.Left == null && root.Right == null)
        return true;

    if (root.Left == null)
    {
#if WHOLE_SUBTREES
        if (!IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
            root.Right = null;
        return true;
#else
        return IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);
#endif
    }

    if (root.Right == null)
    {
#if WHOLE_SUBTREES
        if (!IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
            root.Left = null;
        return true;
#else
        return IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
#endif
    }

    var leftInRange = IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
    var rightInRange = IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);

    if (leftInRange && rightInRange)
        return true;

#if WHOLE_SUBTREES
    if (!leftInRange)
        root.Left = null;
    if (!rightInRange)
        root.Right = null;
    return true;   
#else
    if (leftInRange)
        resultList.Add(root.Left);
    if (rightInRange)
        resultList.Add(root.Right);
    return false;
#endif

}

思路如下：如果给定节点的只有一个子树在给定范围内，那么这一定是新子树的根。如果两者都在范围内，则它们不是子树的根。相反，parent 级别应该处理相应的决定。

算法从以下内容开始：我们遍历树并记住键可能在哪些范围内 (treeRangeMin/Max)。这允许快速检查整个子树是否位于给定范围内（IsTreeWithinRange 方法的第一条语句。

如果当前节点的键位于给定范围之外，接下来的两个语句将处理这种情况。那么只有它的一个子树可能在范围内。如果是这样，则将此子树添加到结果列表中。

接下来，我们检查子树是否存在。如果两者都不是，则当前树完全包含在范围内。

如果只有一棵子树存在，那么动作会根据我们是否可以分裂树而有所不同。如果我们可以拆分树，则会发生以下情况：如果子树不在范围内，我们将其切断并且 return 为真（因为当前节点包含在给定范围内）。如果我们不能分裂树，我们只是传播递归调用的结果。

最后，如果 children 都存在。如果其中之一不包含在该范围内，我们将其切断（如果我们被允许）。如果不允许，我们将子树添加到给定范围内的结果列表。

Answer 3

这可以递归完成，我们保留一个子树列表，只要找到符合要求的子树，我们就会将其附加到该列表中。当以参数节点为根的子树完全在范围内时，递归函数 return 为真。这是调用者决定（parent 节点）来确定当 child 的 recusruve 调用 return 为真或假时要做什么。例如，如果当前节点值在范围内，并且它的 children 的子树也完全在范围内，那么我们就简单地 return 为真。但是如果只有一个children的子树在范围内，另外一个不在范围内，那么我们returnfalse（因为不是当前节点子树的所有子树都在范围内），但我们还将范围内的 child 附加到列表中。如果当前节点值不在我们 return false 的范围内，但我们也检查左侧或右侧 child，如果符合则将其追加到子树列表中：

def subtree_in_range(root, x, y):
  def _subtree_in_range(node):
    in_range=True
    if node:
      if node.val>=x and node.val<=y:
        if not _subtree_in_range(node.left):
          in_range=False
          if node.right and _subtree_in_range(node.right):
            l.append(node.right)
        elif not _subtree_in_range(node.right):
          in_range=False
          if node.left:
            l.append(node.left)
      else:
        in_range=False
        s=node.left
        if node.val<x:
          s=node.right
        if s and _subtree_in_range(s):
          l.append(s)
    return in_range

  l=[]
  if _subtree_in_range(root):
    l.append(root)
  return l

Answer 4

在进行范围搜索时，用某种通用语言编写的范围的主力函数可能如下所示：

function range(node, results, X, Y) 
{
    if node is null then return
    if node.key is in [X, Y] then results.add(node.key)
    if node.key < Y then range(node.right, results, X, Y)
    if node.key > X then range(node.left, results, X, Y)
}

对于子树版本问题，我们需要存储子树根节点而不是键，并跟踪我们是否在子树中。后者可以通过在范围调用中传递子树明智的父级来解决，这也是创建新结构所必需的。所需的功能如下。如您所见，主要变化是一个额外的参数和 node.key in [X, Y] branch

function range_subtrees(node, parent, results, X, Y) 
{
    if node is null then return

    node_clone = null 

    if node.key is in [X, Y] then 
        node_clone = node.clone()
        if parent is null then 
            results.add(node_clone)
        else
            parent.add_child(node_clone)

    if node.key < Y then range_subtrees(node.right, node_clone, results, X, Y)
    if node.key > X then range_subtrees(node.left, node_clone, results, X, Y)
}

这应该创建子树根节点的集合，其中每个子树都是原始树结构的副本。

查找 BST 中所有键在给定范围内的子树

Find all subtrees in a BST whose keys lie in a given range

algorithm

tree-traversal

binary-search-tree

range-query