Averigua si un árbol es un subárbol de otro

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

  •  06-07-2019
  •  | 
  •  

Pregunta

Hay dos árboles binarios T1 y T2 que almacenan datos de caracteres, se permiten duplicados.
 ¿Cómo puedo encontrar si T2 es un subárbol de T1? .
 T1 tiene millones de nodos y T2 tiene cientos de nodos.

¿Fue útil?

Solución

Atravesar T1. Si el nodo actual es igual al nodo raíz de T2, atraviese ambos árboles (T2 y el subárbol actual de T1) al mismo tiempo. Compara el nodo actual. Si siempre son iguales, T2 es un subárbol de T1.

Otros consejos

Sugiero un algoritmo que usa preprocesamiento:

1) Preprocese el árbol T1, manteniendo la lista de todas las raíces de subárbol posibles (la lista de caché tendrá millones de entradas);

2) Ordene la lista de raíces almacenadas en caché por el orden descendente de datos, guardado en la raíz. Puede elegir una función de clasificación más elegante, por ejemplo, analizar un árbol de caracteres en una cadena.

3) Use la búsqueda binaria para localizar el subárbol necesario. Puede rechazar rápidamente los subárboles, con el número de nodos, no igual al número T2 de nodos (o con una profundidad diferente).

Tenga en cuenta que los pasos 1) y 2) deben realizarse solo una vez, luego puede probar muchos candidatos de subárbol, utilizando el mismo resultado preprocesado.

Si sus árboles no están ordenados de ninguna manera, no veo otra forma que hacer una búsqueda de fuerza bruta : recorra el árbol T1 y verifique para ver si llega a un nodo que coincide con el primer nodo del árbol T2 . De lo contrario, continúe atravesando T1 . Si es así, verifique si los siguientes nodos coinciden, hasta que encuentre el final de T2 , en cuyo caso tiene un hit: su árbol T2 es de hecho un subárbol de T1 .

Si conoce la profundidad de cada nodo individual de T1 (de hoja a nodo), puede omitir cualquier nodo que no sea tan profundo como el subárbol que está buscando. Esto podría ayudarlo a eliminar muchas comparaciones innecesarias. Digamos que T1 y T2 están bien equilibrados, entonces el árbol T1 tendrá una profundidad total de 20 ( 2 ** 20 > 1,000,000 ) y el árbol T2 tendrán una profundidad de 7 ( 2 ** 7 > 100 ). Solo tendrá que caminar las 13 primeras capas de T1 (8192 nodos, ¿o son 14 capas y 16384 nodos?) Y podrá omitir aproximadamente 90 % de T1 ...

Sin embargo, si por subárbol quiere decir que los nodos hoja de T2 también son nodos hoja de T1 , entonces podría hacer un primer recorrido de T1 y calcule la profundidad de cada nodo (distancia de la hoja al nodo) y luego solo verifique los subárboles que tienen la misma profundidad que T2 .

Si tiene un límite de memoria / almacenamiento (es decir, no puede manipular previamente y almacenar los árboles en formas alternativas), probablemente no podrá hacer nada mejor que la búsqueda de fuerza bruta sugerida por algunas otras respuestas (transversal P1 busca la raíz coincidente de P2, recorra ambos para determinar si el nodo es de hecho la raíz de un subárbol coincidente, continúe con el recorrido original si no es una coincidencia). Esta búsqueda opera en O (n * m) donde n es el tamaño de P1 ym es el tamaño de P2. Con verificaciones de profundidad y otras optimizaciones potenciales dependiendo de los datos del árbol que tenga disponibles, este hombre se optimizará un poco, pero generalmente sigue siendo O (n * m). Dependiendo de sus circunstancias específicas, este puede ser el único enfoque razonable.

Si no está vinculado a la memoria / almacenamiento y no le importa un poco de complejidad, creo que esto podría mejorarse a O (n + m) reduciendo a problema de subcadena común más largo con la ayuda de un árbol de sufijos generalizado . Puede encontrarse alguna discusión sobre este problema similar aquí . Tal vez cuando tenga más tiempo, vuelva y edite con más detalles sobre una implementación.

Si se le da la raíz de ambos árboles, y dado que los nodos son del mismo tipo, ¿por qué entonces simplemente determinar que la raíz de T2 está en T1 no es suficiente?

Supongo que "dado un árbol T" significa dar un puntero a la raíz de T y al tipo de datos del nodo.

Saludos.

No estoy seguro, si mi idea es correcta. Sin embargo, para tu persuasión.

  1. Realice una caminata de postorder en Tree 1 & amp; Árbol 2, llámelo P1 y P2.
  2. Comparar P1 y amp; P2 Si son diferentes El árbol no es subárbol. Salir.
  3. Si son iguales, o P1 contenido en P2. Puedes decidir cuál es el subárbol.

Creo que debemos ir por la fuerza bruta, pero ¿por qué necesitas unir los árboles después de encontrar tu raíz de T2 en T1? No es lo mismo que cuando se supone que no debemos encontrar si el árbol es idéntico. (Entonces solo necesitamos comparar todo el árbol)

Se le dan los árboles T1 y T2, punteros, no los valores.

Si el nodo T2 (que es un puntero), está presente en el árbol T1.

Entonces el árbol T2 es un subárbol de T1.

Editar:

Solo si se dice que T2 es en realidad un árbol diferente por objeto, y necesitamos descubrir que si hay un Subárbol en T1, que es idéntico a T2.

Entonces esto no funcionará.

Y no tenemos otra opción que buscar las soluciones ya discutidas aquí.

Digamos que tenemos T1 como árbol padre y T2 como árbol que podría ser un subárbol de T1. Haz lo siguiente. Se supone que T1 y T2 son árboles binarios sin ningún factor de equilibrio.

1) Buscar la raíz de T2 en T1. Si no se encuentra, T2 no es un subárbol. Buscar el elemento en BT llevará O (n) tiempo.

2) Si se encuentra el elemento, haga un pedido anticipado de T1 desde el elemento raíz del nodo de T2. Esto llevará o (n) tiempo. Haga un pedido anticipado de T2 también. Tomará O (n) tiempo. El resultado del recorrido previo al pedido se puede almacenar en una pila. La inserción en la pila solo tomará O (1).

3) Si el tamaño de dos pilas no es igual, T2 no es un subárbol.

4) Pop un elemento de cada pila y comprobar la igualdad. Si se produce una falta de coincidencia, T2 no es un subárbol.

5) Si todos los elementos coinciden T2 es un subárbol.

Supongo que su árbol son árboles inmutables , por lo que nunca cambiará ningún subárbol (no hace set-car! en el esquema Scheme), pero usted es construyendo nuevos árboles a partir de hojas o de árboles existentes.

Entonces aconsejaría mantener en cada nodo (o subárbol) un código hash de ese nodo. En lenguaje C, declare que los árboles son 

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

luego calcule el hash en tiempo de construcción, y cuando compare nodos para igualdad primero compare su hash para igualdad; la mayoría de las veces el código hash sería diferente (y no se molestará en comparar contenido).

Aquí hay una posible función de construcción de hoja: 

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 función para calcular un código hash es 

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

La función para construir un nodo a partir de dos subárboles sleft & amp; sright es 

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 función de comparación (de dos árboles tx & amp; ty ) aprovecha que si los códigos hash son diferentes, los comparados son diferentes 

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

}

La mayoría de las veces la prueba tree_hash (tx)! = tree_hash (ty) tendría éxito y no tendrá que repetirla.

Lea sobre hash consing .

Una vez que tenga una función equal_tree tan eficiente basada en hash, puede usar las técnicas mencionadas en otras respuestas (o en manuales).

Una de las formas simples es escribir el método is_equal () para el árbol y hacer lo siguiente, 

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

Tenga en cuenta que is_equal () se puede optimizar utilizando hashcode para el árbol. Se puede hacer de manera simple tomando la altura del árbol o el número de hijos o el rango de valores como código hash. 

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

Cuando el árbol es similar a una lista vinculada, tomará tiempo O (n). También podemos usar algo de heurística al elegir a los niños para comparar. 

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

Otra forma es serializar ambos árboles como cadena y encontrar si la segunda cadena (serializada desde T2) es una subcadena de la primera cadena (serializada desde T1).

El siguiente código serializa en pre-pedido. 

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

Y podemos usar un algoritmo optimizado, por ejemplo, Knuth & # 8211; Morris & # 8211; Algoritmo de Pratt para encontrar (posiblemente en tiempo O (n)) la existencia de la subcadena y eventualmente encontrar si un árbol es un subárbol de otro.

Nuevamente, la cadena se puede comprimir eficientemente con Burrows & # 8211; Wheeler_transform. Y es posible bzgrep para buscar subcadenas en los datos comprimidos.

Otra forma es ordenar los subárboles en el árbol por altura y número de hijos. 

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

    return nchildren < other->nchildren;
}

Tenga en cuenta que habrá O (n ^ 2) subárboles. Para reducir el número, podemos usar un rango basado en la altura. Por ejemplo, solo podemos estar interesados ??en los subárboles de altura 1000 a 1500.

Cuando se generan los datos ordenados, es posible hacer una búsqueda binaria en él y encontrar si está subconjunto en el tiempo O (lg n) (considerando que no hay duplicado en los datos ordenados).

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top