Scopri se un albero è una sottostruttura dell'altro

StackOverflow https://stackoverflow.com/questions/1017821

  •  06-07-2019
  •  | 
  •  

Domanda

Esistono due alberi binari T1 e T2 che memorizzano i dati dei caratteri, duplicati consentiti  Come posso sapere se T2 è una sottostruttura di T1? .
 T1 ha milioni di nodi e T2 ha centinaia di nodi.

È stato utile?

Soluzione

Traversa T1. Se il nodo corrente è uguale al nodo radice di T2, attraversare entrambi gli alberi (T2 e la sottostruttura corrente di T1) contemporaneamente. Confronta il nodo corrente. Se sono sempre uguali, T2 è una sottostruttura di T1.

Altri suggerimenti

Suggerisco un algoritmo che utilizza la preelaborazione:

1) Preelaborare l'albero T1, mantenendo l'elenco di tutte le possibili radici di sottostruttura (l'elenco della cache avrà un milione di voci);

2) Ordinare l'elenco delle radici memorizzato nella cache in ordine decrescente di dati, mantenuto nella radice. Puoi scegliere una funzione di ordinamento più elegante, ad esempio, analizzare un albero di caratteri in stringa.

3) Utilizzare la ricerca binaria per individuare l'albero secondario necessario. Puoi rifiutare rapidamente i sottotitoli, con il numero di nodi, non uguale al numero T2 di nodi (o con diversa profondità).

Nota che i passaggi 1) e 2) devono essere eseguiti una sola volta, quindi puoi testare molti candidati sottoalbero, usando lo stesso risultato preelaborato.

Se i tuoi alberi non sono ordinati in alcun modo, non vedo altro che fare una ricerca forza bruta : camminare attraverso l'albero T1 e controllare per vedere se raggiungi un nodo che corrisponde al primo nodo dell'albero T2 . In caso contrario, continua a attraversare T1 . In tal caso, controlla se i nodi successivi corrispondono, fino a quando non trovi la fine di T2 , nel qual caso hai un hit: il tuo albero T2 è effettivamente una sottostruttura di T1 .

Se conosci la profondità di ogni singolo nodo di T1 (da foglia a nodo), puoi saltare tutti i nodi che non sono profondi come la sottostruttura che stai cercando. Questo potrebbe aiutarti a eliminare molti confronti inutili. Supponi che T1 e T2 siano ben bilanciati, quindi l'albero T1 avrà una profondità totale di 20 ( 2 ** 20 > 1.000.000 ) e l'albero T2 avranno una profondità di 7 ( 2 ** 7 > 100 ). Dovrai solo percorrere i 13 primi layer di T1 (8192 nodi - ovvero 14 layer e 16384 nodi?) E potrai saltare circa 90 % di T1 ...

Tuttavia, se per sottotree intendi che i nodi foglia di T2 sono anche nodi foglia di T1 , allora potresti fare una prima traversata di T1 e calcola la profondità di ogni nodo (distanza da foglia a nodo) e quindi controlla solo i sottotitoli che hanno la stessa profondità di T2 .

Se sei limitato dalla memoria / archiviazione (cioè non puoi pre-manipolare e conservare gli alberi in forme alternative), probabilmente non sarai in grado di fare qualcosa di meglio della ricerca della forza bruta suggerita da altre risposte (attraversa P1 cercando la radice corrispondente di P2, attraversa entrambi per determinare se il nodo è in realtà la radice di un sottoalbero corrispondente, continua con l'attraversamento originale se non è una corrispondenza). Questa ricerca opera in O (n * m) dove n è la dimensione di P1 e m è la dimensione di P2. Con i controlli di profondità e altre potenziali ottimizzazioni a seconda dei dati dell'albero disponibili, quest'uomo può essere ottimizzato un po ', ma è comunque generalmente O (n * m). A seconda delle circostanze specifiche, questo potrebbe essere l'unico approccio ragionevole.

Se non hai limiti di memoria / archiviazione e non ti dispiace un po 'di complessità, credo che questo potrebbe essere migliorato a O (n + m) riducendo a problema di sottostringa comune più lungo con l'aiuto di un albero di suffisso generalizzato . Qualche discussione su questo per un problema simile può essere trovata qui . Forse quando avrò più tempo, tornerò e modificherò con più dettagli su un'implementazione.

Se viene data la radice di entrambi gli alberi e dato che i nodi sono dello stesso tipo, perché allora accertarsi che la radice di T2 sia in T1 non è sufficiente?

Suppongo che "dato un albero T" significa dato un puntatore alla radice di T e al tipo di dati del nodo.

Saluti.

Non sono sicuro che la mia idea sia corretta. Tuttavia, per il tuo persual.

  1. Esegui una camminata post-ordine nell'albero 1 & amp; Albero 2, chiamalo P1 e P2.
  2. Confronta P1 e amp; P2. Se sono diversi. L'albero non è sottotetto. Esci.
  3. Se sono uguali o P1 contenuto in P2. Puoi decidere quale è l'albero secondario.

Penso che dobbiamo andare con la forza bruta, ma perché devi abbinare gli alberi dopo aver trovato la tua radice di T2 in T1. Non è lo stesso di quando non dovremmo scoprire se l'albero è identico (solo allora dobbiamo confrontare l'intero albero)

Ti vengono dati gli alberi T1 e T2, i puntatori, non i valori.

Se il nodo T2 (che è un puntatore), è presente nella struttura ad albero T1.

Quindi l'Albero T2 è sottotree di T1.

Modifica:

Solo se si dice che T2 è in realtà un albero diverso per oggetto, e dobbiamo scoprire che se c'è un sottotree in T1, che è identico a T2.

Quindi questo non funzionerà.

E non abbiamo altra scelta che cercare le soluzioni già discusse qui.

Supponiamo di avere T1 come albero principale e T2 come albero che potrebbe essere una sottostruttura di T1. Eseguire le seguenti operazioni. Il presupposto è che T1 e T2 siano alberi binari senza alcun fattore di bilanciamento.

1) Cerca la radice di T2 in T1. Se non trovato T2 non è una sottostruttura. La ricerca dell'elemento in BT richiederà tempo O (n).

2) Se viene trovato l'elemento, esegui il pre-ordine di attraversamento di T1 dall'elemento radice nodo di T2. Questo richiederà o (n) tempo. Esegui anche l'attraversamento del pre-ordine di T2. Ci vorrà O (n) tempo. Il risultato dell'incrocio del preordine può essere memorizzato in una pila. L'inserimento nello stack richiederà solo O (1).

3) Se la dimensione di due pile non è uguale, T2 non è una sottostruttura.

4) Pop un elemento da ogni pila e verificare l'uguaglianza. In caso di mancata corrispondenza, T2 non è una sottostruttura.

5) Se tutti gli elementi corrispondenti a T2 sono una sottostruttura.

Suppongo che il tuo albero sia alberi immutabili quindi non cambi mai alcun sottostruttura (non fai set-car! nel linguaggio Scheme), ma solo tu sei costruire nuovi alberi dalle foglie o dagli alberi esistenti.

Quindi consiglierei di mantenere in ogni nodo (o sottostruttura) un codice hash di quel nodo. Nel linguaggio C, dichiarare gli alberi 

 struct tree_st {
   const unsigned hash;
   const bool isleaf;
   union {
     const char*leafstring; // when isleaf is true
     struct { // when isleaf is false
        const struct tree_st* left;
        const struct tree_st* right;
     };
   };
 };

quindi calcola l'hash in fase di costruzione e, quando si confrontano i nodi per l'uguaglianza, prima confrontare il loro hash per l'uguaglianza; il più delle volte il codice hash sarebbe diverso (e non ti preoccuperai di confrontare i contenuti).

Ecco una possibile funzione di costruzione delle foglie: 

struct tree_st* make_leaf (const char*string) {
   assert (string != NULL);
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   t->hash = hash_of_string(string);
   t->isleaf = true;
   t->leafstring = string;
   return t;
}

La funzione per calcolare un codice hash è 

unsigned tree_hash(const struct tree_st *t) {
  return (t==NULL)?0:t->hash;
}

La funzione per costruire un nodo da due sottoalberi sleft & amp; sright è 

struct tree_st*make_node (const struct tree_st* sleft,
                          const struct tree_st* sright) {
   struct tree_st* t = malloc(sizeof(struct tree_st));
   if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
   /// some hashing composition, e.g.
   unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
   t->hash = h;
   t->left = sleft;
   t->right = sright;
   return t;
 }

La funzione di confronto (di due alberi tx & amp; ty ) sfrutta il fatto che se gli hashcode sono diversi i confronti sono diversi 

bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
  if (tx==ty) return true;
  if (tree_hash(tx) != tree_hash(ty)) return false;
  if (!tx || !ty) return false;
  if (tx->isleaf != ty->isleaf) return false;
  if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
  else return equal_tree(tx->left, ty->left) 
              && equal_tree(tx->right, ty->right);

}

Il più delle volte il test tree_hash (tx)! = tree_hash (ty) ha esito positivo e non dovrai ricorrere.

Leggi hash consing .

Una volta che hai una funzione equal_tree basata su hash così efficiente puoi usare le tecniche menzionate in altre risposte (o nei manuali).

Uno dei modi semplici è scrivere il metodo is_equal () per l'albero e fare quanto segue, 

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}

Nota che is_equal () può essere ottimizzato usando l'hashcode per l'albero. Può essere fatto in modo semplice prendendo l'altezza dell'albero o il numero di bambini o l'intervallo dei valori come hashcode. 

bool is_equal(TNode*other) {
    if(x != other->x) return false;
    if(height != other->height) return false;
    if(nchildren != other->nchildren) return false;
    if(hashcode() != other->hashcode()) return false;
    // do other checking for example check if the children are equal ..
}

Quando l'albero è simile a un elenco collegato, ci vorrà O (n) tempo. Possiamo anche usare un po 'di euristica scegliendo i bambini da confrontare. 

bool contains_subtree(TNode*other) {
    // optimization
    if(nchildren < other->nchildren) return false;
    if(height < other->height) return false;

    // go for real check
    if(is_equal(other)) return true;
    if(left == NULL || right == NULL) {
          return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
    }
    if(left->nchildren < right->nchildren) { // find in smaller child tree first
          return (left->contains_subtree(other)) || right->contains_subtree(other);
    } else {
          return (right->contains_subtree(other)) || left->contains_subtree(other);
    }
}

Un altro modo è serializzare entrambi gli alberi come stringhe e scoprire se la seconda stringa (serializzata da T2) è una sottostringa della prima stringa (serializzata da T1).

Il seguente codice serializza in preordine. 

   void serialize(ostream&strm) {
            strm << x << '(';
            if(left)
                    left->serialize(strm);
            strm << ',';
            if(right)
                    right->serialize(strm);
            strm << ')';
    }

E possiamo usare alcuni algoritmi ottimizzati, ad esempio Knuth & # 8211; Morris & # 8211; Algoritmo Pratt per trovare (possibilmente in O (n) tempo) l'esistenza della sottostringa e alla fine scoprire se un albero è un sotto-albero di un altro.

Ancora una volta la stringa può essere compressa in modo efficiente con Burrows & # 8211; Wheeler_transform. Ed è possibile bzgrep cercare una sottostringa nei dati compressi.

Un altro modo è quello di ordinare i sottoalberi nell'albero per altezza e numero di bambini. 

bool compare(TNode*other) {
    if(height != other->height)
        return height < other->height;

    return nchildren < other->nchildren;
}

Nota che ci saranno sotto-alberi O (n ^ 2). Per ridurre il numero possiamo usare un intervallo in base all'altezza. Ad esempio, possiamo essere interessati solo ai sottoalberi di altezza compresa tra 1000 e 1500.

Quando vengono generati i dati ordinati, è possibile fare una ricerca binaria in esso e scoprire se è un sottoinsieme nel tempo O (lg n) (considerando che non ci sono duplicati nei dati ordinati).

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top