Найти все поддеревья в BST, ключи которых находятся в заданном диапазоне

Question

Мне задали этот вопрос во время недавнего интервью: Учитывая BST, узлы которого содержат значение Integer как целое, найдите все поддеревья, узлы которых попадают между целыми числами X (min) и Y (max), где X < Y. Эти поддеревья не могут пересекаться друг с другом.

Я решил варианты этой проблемы, например - клавиши печати BST, которые попадают в заданный диапазон. Но он не мог понять этого, поскольку он включает в себя поиск всех связанных субграфов главного графика/дерева, которые удовлетворяют очень конкретным ограничениям. Любые указатели/help/псевдокод оцениваются.

Добавлены ноты -

1. Проблема определена структура данных узла, как имеющий левый, правый указатель указатель, и целое значение. Невозможно было отметить узел.
2. Просили решить эту проблему на Java.
3. Когда я сказал поддерево/подграф, я имел в виду подключенный набор узлов, а не список непересекающихся узлов. извините за путаницу.

Answer 1

Конкретное решение зависит от определения поддерева. Рассмотрим следующий BST:

5 
    3 
    2 
    4 
    8 
    - 
    9 

И мы хотим, чтобы найти поддеревьев в диапазоне [4,8]. Очевидно, что узел 4 принадлежит к выходу. Но как насчет другой половины дерева? Если поддерево ссылается на узел со всеми его дочерними элементами, то это весь результат.Если поддерево фактически является подмножеством входных узлов, узлы 5 и 8 относятся к результату, но их соединения с узлами 3 и 9 должны быть удалены.

В любом случае, следующий алгоритм может обрабатывать оба. Препроцессор, определяющий WHOLE_SUBTREES, определяет, являются ли поддеревья целыми субкомпонентами со всеми дочерними элементами.

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 

} 

Идея заключается в следующем: Если только один поддерево данного узла находится в пределах заданного диапазона, то это должно быть корнем нового поддерева. Если оба лежат в диапазоне, то они не являются корнем поддерева. Вместо этого родительский уровень должен обрабатывать соответствующее решение.

Алгоритм начинается со следующего: мы пересекаем дерево и помним, в каких диапазонах могут быть ключи (treeRangeMin/Max). Это позволяет быстро проверить, находится ли в данном диапазоне целое поддерево (первый оператор метода IsTreeWithinRange.

Следующие два оператора обрабатывают регистр, если ключ текущего узла находится за пределами заданного диапазона. Тогда только одно из его поддеревьев может быть в пределах диапазона.Если это так, это поддерево добавляется в список результатов.

Далее мы проверяем, существуют ли поддеревья. Если и то и другое, то текущее дерево полностью содержится в пределах диапазона.

Если существует только одно поддерево, действие различается в зависимости от того, можно ли разделить деревья. Если мы можем разделить дерево, произойдет следующее: если поддерево не находится внутри диапазон, мы отключили его и вернем true (поскольку текущий узел содержится в заданном диапазоне). Если мы не можем разделить деревья, мы просто распространяем результат рекурсивного вызова.

Наконец, если оба ребенка существуют. Если один из них не содержится в пределах диапазона, мы отключили его (если нам разрешено). Если нам не разрешено, мы добавляем поддерево в список результатов, который находится в заданном диапазоне.

Answer 2

Это очень легко решить. Для того, чтобы иметь поддеревья, которые не перекрываются, я включил выделенное поле, инициализированное значением false для каждого узла.

Алгоритм выглядит следующим образом:

траверсы с BST, начиная от корня используя метод DFS. Теперь, если узел встречается в DFS, который не помечен, и он удовлетворяет ограничению (падает между X и Y), тогда существует решение с корневым поддеревом на этом узле, но мы не знаем, насколько велика эта поддерево ? Таким образом, мы делаем следующее:

Пройди свой левый и правый ребенка в другой метод проверки, который будет делать следующее:

Траверс поддерева с корнем в узле и пересекают ее в моде ДФС, пока ограничения удовлетворены и обнаруженные узлы не отмечены. Как только какое-либо условие будет нарушено, вернитесь.

Теперь исходный метод DFS можно вызывать в уже отмеченных вершинах, но условие if будет оцениваться как false. Следовательно, цель достигнута.

Я решил использовать его с использованием языка JAVA и при условии, что ключи лежат между 10 и 21 (эксклюзивно). Вот код:

Еще одна вещь, если после поддерево корневое на X с childs равно, то оно обозначает поддерево с единственным узлом.

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 3

Это можно сделать рекурсивно, и мы сохраняем список поддеревьев, которые мы добавляем, всякий раз, когда найдено подходящее поддерево. Рекурсивная функция возвращает true, когда поддерево, укорененное на узле аргумента, полностью находится в зоне действия. Решение вызывающего абонента (родительский узел) определяет, что делать, если вызов recusruve для ребенка возвращает true или false. Например, если текущее значение узла находится в диапазоне, а его дочерние поддеревья также полностью находятся в зоне действия, то мы просто возвращаем true. Но если только одно из дочерних поддеревьев находится в диапазоне, а другое не находится в диапазоне, то мы возвращаем false (поскольку не все текущее поддерево узла находится в диапазоне), но мы также добавляем дочерний элемент, который был в диапазон к списку. Если текущее значение узла не находится в диапазоне мы возвращаемся ложным, но мы также проверяем левую или правую ребенка, и добавить его в список поддеревьев, если это соответствует:

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] филиала

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) 
} 

Это должно создать коллекцию поддерев корневых узлов, где каждое поддерево является копией структуры исходного дерева.