Trova tutte le sottostrutture in un BST le cui chiavi si trovano in un determinato intervallo

Question

Mi è stata data questa domanda durante una recente intervista: Dato un BST i cui nodi contengono un intero come valore, trova tutti i sottotitoli i cui nodi rientrano tra interi X (min) e Y (max), dove X < Y. Questi sottostrati non possono sovrapporsi l'un l'altro.

Ho risolto le varianti di questo problema, ad esempio: i tasti di stampa di un BST che rientrano in un determinato intervallo. Ma non riuscivo a capire questo, dal momento che si tratta di trovare tutti i sotto-grafici collegati del grafico/albero principale che soddisfano vincoli molto specifici. Ogni puntatore/aiuto/pseudo codice è apprezzato.

Aggiunte note -

1. Il problema definito il datastructure di nodo come avere un puntatore sinistra, destra puntatore, e un valore intero. Non c'era modo di contrassegnare un nodo.
2. È stato chiesto di risolvere questo in Java.
3. Quando ho detto sottostruttura/sottografo, intendevo un insieme collegato di nodi, non un elenco di nodi disgiunti. dispiace per la confusione.

Answer 1

La soluzione concreta dipende dalla definizione di una sottostruttura. Si consideri il seguente BST:

5 
    3 
    2 
    4 
    8 
    - 
    9 

E vogliamo trovare le sottostrutture nella gamma [4,8]. È ovvio che il nodo 4 appartiene all'output. Ma per quanto riguarda l'altro mezzo albero? Se una sottostruttura si riferisce a un nodo con tutti i suoi figli, allora questo è l'intero risultato.Se una sottostruttura è in realtà un sottoinsieme dei nodi di input, i nodi 5 e 8 appartengono al risultato, ma le loro connessioni ai nodi 3 e 9 devono essere rimosse.

In ogni caso, il seguente algoritmo può gestire entrambi. Il preprocessore definisce WHOLE_SUBTREES definisce se i sottoalberi sono interi sottocomponenti con tutti i bambini.

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 

} 

L'idea è la seguente: Se solo una sottostruttura di un dato nodo è entro l'intervallo dato, allora questo deve essere la radice di una nuova sottostruttura. Se entrambi si trovano nell'intervallo, non sono la radice di un albero secondario. Invece, il livello genitore dovrebbe gestire la decisione secondo.

L'algoritmo inizia con quanto segue: Attraversiamo l'albero e ricordiamo in quale intervallo possono essere i tasti (treeRangeMin/Max). Ciò consente un controllo rapido se un'intera sottostruttura si trova nell'intervallo specificato (prima dichiarazione del metodo IsTreeWithinRange.

Le due istruzioni successive gestiscono il caso se la chiave del nodo corrente si trova al di fuori dell'intervallo specificato. Quindi solo una delle sue sottostrutture potrebbe essere all'interno dell'intervallo .. Se questo è il caso, questo sottostruttura viene aggiunto all'elenco dei risultati

Successivamente, controlliamo se esistono i sottoalberi. Se entrambi non lo sono, l'albero corrente è completamente contenuto nell'intervallo.

Se esiste solo un sottoalbero, l'azione varia a seconda che si possano suddividere gli alberi. Se si può suddividere l'albero, accade quanto segue: Se il sottostruttura non è all'interno l'intervallo, lo interrompiamo e restituiamo true (poiché il nodo corrente è contenuto nell'intervallo specificato). Se non possiamo dividere gli alberi, propaghiamo semplicemente il risultato della chiamata ricorsiva.

Infine, se entrambi i bambini esistono. Se uno di essi non è contenuto nell'intervallo, lo interrompiamo (se ci è permesso). Se non siamo autorizzati, aggiungiamo la sottostruttura alla lista dei risultati che si trova all'interno dell'intervallo dato.

Answer 2

Questo è praticamente semplice da risolvere. Per avere sottoalberi che non si sovrappongono, ho incluso un campo marcato, inizializzato su falso per ogni nodo.

L'algoritmo è il seguente:

traslare gli BST iniziando da root mediante metodo DFS. Ora se si incontra un nodo in DFS, che non è marcato e soddisfa il vincolo (rientra tra X e Y), allora c'è una soluzione con un sottoalbero radicato in quel nodo, ma non sappiamo quanto grande quella sottostruttura possa essere ? Così facciamo la seguente:

passare il suo figlio sinistro ea destra per un altro controllo metodo, che farà il seguente:

Traverse sottoalbero con radice nel nodo e attraversare in modo DFS fintanto che i vincoli sono soddisfatti e i nodi incontrati non sono contrassegnati. Non appena una qualsiasi condizione viene violata, quindi tornare.

Ora, il metodo DFS originale può essere richiamato sui vertici già contrassegnati ma la condizione if verrà valutata su false. Quindi l'obiettivo è raggiunto.

L'ho risolto utilizzando il linguaggio JAVA e per condizione che le chiavi siano comprese tra 10 e 21 (esclusive). Ecco il codice:

Un'altra cosa, se non viene stampato nulla dopo la sottostruttura con radice X con childs come, allora si tratta di una sottostruttura con nodo singolo.

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

Sentiti libero per qualsiasi domanda.

Answer 3

Questo può essere fatto in modo ricorsivo e manteniamo un elenco di sottoalberi a cui aggiungiamo ogni volta che viene trovata una sottostruttura compatibile. La funzione ricorsiva restituisce true quando il sottostruttura radicata sul nodo dell'argomento è interamente nell'intervallo. È la decisione del chiamante (il nodo genitore) di determinare cosa fare quando la chiamata recusruve del figlio restituisce vero o falso. Ad esempio, se il valore del nodo corrente è compreso nell'intervallo e anche i sottostrutture dei suoi figli sono completamente nell'intervallo, restituire semplicemente true. Ma se solo uno dei sottoalberi dei bambini si trova nell'intervallo e l'altro non è nel range, allora restituiamo false (poiché non tutto il sottoalbero del nodo corrente è nell'intervallo), ma aggiungiamo anche il bambino che era in l'intervallo per la lista. Se il valore del nodo corrente non è nel range torniamo falsa, ma abbiamo anche il check-sinistra o figlio destro, e aggiungerlo alla lista delle sottostrutture se è compatibile con:

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

Nel fare ricerca gamma, cavallo di battaglia funzione per la serie, scritta in una lingua generica, potrebbe in questo modo:

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

per il problema versione sottostruttura abbiamo bisogno di memorizzare nodi principali sottostruttura invece di chiavi e tenere traccia se siamo in sottostruttura o meno. Quest'ultimo può essere risolto passando il genitore saggio secondario nel richiamo di intervallo, che è anche richiesto per la creazione di nuove strutture. La funzione desiderata è sotto.Come si può vedere, il cambiamento principale è un argomento in più e node.key in [X, Y] ramo

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

Questo dovrebbe creare una collezione di nodi principali sottostruttura, in cui ogni sottostruttura è una copia della struttura di albero originale.