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

Question

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

Answer 1

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

Answer 2

Si los árboles no se ordenan de ninguna manera, no veo ninguna otra manera que hacer una fuerza bruta búsqueda: caminar a través del árbol T1 y comprobar para ver si se llega a un nodo que coincide con la primera nodo del árbol T2. De lo contrario, continúe atravesando T1. Si es así, comprueba si los siguientes nodos coinciden, hasta que encuentres el final de T2, en cuyo caso tienes un hit: tu árbol T2 es de hecho un subárbol de T1.

Si conoce la profundidad de cada nodo de T1 (de hoja a nodo), puede omitir los nodos que no sean tan profundos como el subárbol que está buscando. Esto podría ayudarlo a eliminar una gran cantidad de comparaciones innecesarias. Decir que T1 y T2 son bien equilibrado, entonces árbol T1 tendrá una profundidad total de 20 (2**20>1,000,000) y el árbol de T2 tendrá una profundidad de 7 (2**7>100). Usted sólo tendrá que caminar las 13 primeras capas de T1 (8192 nodos -, o es que 14 capas y 16.384 nodos) y será capaz de saltar alrededor del 90% de T1 ...

Sin embargo, si por subárbol significa que los nodos hoja de T2 también son nodos hoja de T1, entonces podría hacer una primera pasada de T1 y calcular la profundidad de cada nodo (distancia de hoja a nodo) y luego solo verificar los subárboles que tienen la misma profundidad que T2.

Answer 3

que sugieren un algoritmo, que utiliza preprocesamiento:

1) Pre-proceso del árbol T1, manteniendo la lista de todas las posibles raíces de subárbol (la lista de caché tendrá un millones de entradas);

2) Ordene la lista de raíces en caché por orden descendente de datos, mantenida 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) Utilice 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 de nodos T2 (o con la 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.

Answer 4

No estoy seguro, si mi idea es correcta. Sin embargo, para su persual.

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

Answer 5

Si está atado/guardado de memoria (es decir, no puede pre manipular y almacenar los árboles en formas alternativas), probablemente no podrá hacer nada mejor que la búsqueda de fuerza bruta sugerida por otro respuestas (recorra P1 buscando 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 cruce original si no coincide). Esta búsqueda opera en O (n * m) donde n es el tamaño de P1 ym es el tamaño de P2. Con las comprobaciones de profundidad y otras posibles optimizaciones según los datos de árbol que tenga disponibles, este hombre se optimizará un poco, pero en general sigue siendo O (n * m). Dependiendo de sus circunstancias específicas, este puede ser el único enfoque razonable.

Si no tiene memoria/almacenamiento y no le importa un poco la complejidad, creo que esto podría mejorarse a O (n + m) reduciendo a un problema longest common substring con la ayuda de generalized suffix tree. Se puede encontrar alguna discusión sobre esto para un problema similar here. Tal vez cuando tenga más tiempo, regrese y edite con más detalles sobre una implementación.

Answer 6

Si se les da la raíz de ambos árboles, y dado que los nodos son del mismo tipo, ¿por qué entonces es tan difícil saber que la raíz de T2 está en T1?

Estoy asumiendo que "da un árbol T" significa dar un puntero a la raíz de T y el tipo de datos del nodo.

Atentamente.

Answer 7

creo que tenemos que ir por la fuerza bruta, pero ¿por qué necesita para que coincida con los árboles después de encontrar la raíz de T2 en T1. No es lo mismo que cuando no se supone que debemos encontrar si el árbol es idéntico. (Entonces solo tenemos que comparar todo el árbol)

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

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

Luego, el Tree T2 es un subárbol de T1.

---

Editar:

Sólo si su dicho de que T2 es en realidad un árbol diferente por objeto sabia, y tenemos que saber que si hay un subárbol en T1, que es idéntica a la T2.

Entonces esto no funcionará.

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

Answer 8

Digamos que tenemos T1 como árbol padre y T2 como un árbol que podría ser un subárbol de T1. Haz lo siguiente. La suposición hecha es 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. La búsqueda del elemento en BT tomará O (n) el tiempo.

2) Si se encuentra el elemento, hacer pre-orden de recorrido de T1 desde el elemento raíz nodo de T2 se encuentra. Esto tomará un (a) tiempo. Realice un pedido por adelantado de T2 también. Tomará O (n) tiempo. El resultado del recorrido previo a la orden puede almacenarse 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) Inserta un elemento de cada pila y verifica la igualdad. Si se produce un desajuste, T2 no es un subárbol.

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

Answer 9

que suponer que su árbol son árboles inmutables por lo que nunca cambia ningún subárbol (no haces set-car! en el Esquema jerga), pero sólo se están construyendo nuevos árboles de hojas o de los árboles existentes.

Entonces yo le aconsejaría a tener en cada nodo (o rama) un código hash de ese nodo. En el lenguaje C, declarar el árbol-s para ser

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

después calcular el hash en el momento de la construcción, y cuando la comparación de nodos para la igualdad primer comparar su hash para la igualdad; la mayoría de las veces el código hash sería diferente (y no se molestará en comparar el contenido).

Aquí es una posible función de la construcción de la 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 & sright se

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

El com la función (de dos árboles tx & ty) toman ventaja de que si los hashcodes son diferentes las comparands son diferentes pare

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

}

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

Lee sobre hash consing.

Una vez que tenga una función tan eficiente basada en hash equal_tree, podría utilizar las técnicas mencionadas en otras respuestas (o en los manuales).

Answer 10

Uno de la manera normal es escribir 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 mediante el uso de código hash para el árbol. Se puede hacer de una manera simple tomando la altura del árbol o el número de hijos o el rango de los 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á O (n) tiempo. También podemos usar algo de heurística mientras elegimos 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 tanto de árboles como de cuerda y encontrar si la segunda cadena (serializado desde la T2) es subcadena de la primera cadena (serializado de T1).

El siguiente código se serializa en el pedido por adelantado.

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

y podemos utilizar algún algoritmo optimizado, por ejemplo, Knuth–Morris–Pratt algorithm de encontrar (tiempo posiblemente en O (n)) la existencia de la sub-cadena y eventualmente encontrar si un árbol es un sub-árbol de la otra .

Nuevamente, la cuerda se puede comprimir de manera eficiente con Burrows-Wheeler_transform. Y es posible bzgrep buscar subcadena 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 de 1000 a 1500.

Cuando se generan los datos ordenados, es posible realizar una búsqueda binaria y encontrar si está subconjunto en O (lg n) hora (teniendo en cuenta que no hay duplicados en los datos clasificados).