tipos - clasificacion de arboles estructura de datos

Encuentre si el primer árbol es un subconjunto del segundo árbol

Question

Revisé todo Internet para averiguar cómo verificar si un árbol es un subconjunto de otro. Por subconjunto, me refiero a que la función issubset debe return 1 si todos los elementos del primer árbol aparecen en el segundo árbol y 0 caso contrario. Tenga en cuenta que, según el orden de inserción de los elementos, dos árboles con el mismo conjunto de elementos pueden tener formas muy diferentes. Dados los siguientes ejemplos como árboles:

Elements of the first tree
             4
           /  /
         2     6
        / /   / /
       1   2  5  7 


Elements of the second Tree
            6
          /   /
         4     7
        /  /
       2    5
      / /
     1   2    

El siguiente código atraviesa los árboles y luego verifica los valores:

int issubset(nodeT **tree1, nodeT **tree2) {

    if( *tree2 == NULL)
        return TRUE;
    if(*tree1 == NULL)
        return FALSE;

    if(are_identical(&(*tree1),&(*tree2)))
        return TRUE;

    return issubset(&(*tree1)->pLeft, &(*tree2)) || issubset(&(*tree2)->pRight, &(*tree2));
}

int are_identical(nodeT **tree1, nodeT **tree2) {
    nodeT **temp;
    int iFound = 0, i, r;   
    if( *tree2 == NULL)
        return TRUE;

    if( (*tree1) ==NULL && (*tree2) ==NULL) {
        return FALSE;
    }

    if( (*tree1)->iValue != (*tree2)->iValue) {
        if(iFound = 0)
            return TRUE;

        i = issubset(&(*tree1)->pLeft, &(*tree2));
        if( i ==0) {
            r = issubset(&(*tree1)->pRight, &(*tree2));
            return r;
        }

        return i;
    }   

    return((*tree1)->iValue == (*tree2)->iValue && are_identical(&(*tree1)->pLeft, &(*tree2)->pLeft) && 
           are_identical(&(*tree1)->pRight, &(*tree2)->pRight) );
}

Después de ejecutar mi código con los ejemplos dados, mi salida devuelve que el primer árbol no es un subconjunto del segundo, cuando en realidad es un subconjunto.

Answer 1

Los árboles binarios de búsqueda admiten una iteración ordenada eficiente sobre los elementos. Mantenga un iterador sobre los elementos de cada árbol en orden no decreciente. Repita lo siguiente hasta que se determine un resultado:

• Si el primer iterador no tiene más elementos, devuelve TRUE .
• Si el segundo iterador no tiene más elementos, devuelve FALSE .
• Si el elemento actual del primer iterador es menor que el del segundo, devuelva FALSE .
• Si el elemento actual del primer iterador es igual al del segundo, actualice ambos iteradores.
• Si el elemento actual del primer árbol es mayor que el del segundo, actualice el segundo iterador. (Puede optimizar esto omitiendo algunos elementos).

La implementación básica es el caso más desfavorable O(n + m) donde n y m son los tamaños respectivos de los dos árboles. Con la optimización mencionada, también puede enlazar esto con O(n log m) si el árbol más grande está equilibrado, lo cual es útil si el segundo árbol es mucho más grande que el primero. (Si los árboles están balanceados o no, el límite de O(n + m) aún se aplica).

Answer 2

No estoy seguro de entender su pregunta, pero aún trato de darle mi respuesta. Según su ejemplo, supongo que está trabajando con árboles de búsqueda binarios. Pero no sé qué tipo de árbol binario estás usando, asumiré un esquema general. Supongo que si el árbol está algo equilibrado, entonces quizás puedas obtener un mejor algoritmo.

Dado que tiene árboles de búsqueda binarios, puede suponer una search(root, key) función search(root, key) que devuelve un puntero válido a un nodo que contiene la key si esta se encuentra o NULL caso contrario.

Además, supongo que sabes la cantidad de nodos de cada árbol. Entonces podrías devolver 0 si tree1 tiene nodos menores que tree . De lo contrario, el enfoque es el siguiente:

int tree1_contained_in_tree2(node * tree1, node * tree2)
{
  if (tree1 == NULL) // am I visiting a empty tree?
    return 1;

  // so I am sure tree1 is not NULL ==> I search the contained key in tree2
  if (search(tree2, tree1->key) == NULL)
    return 0; // tree1->key does not belong to tree2

  // here tree1->key belongs to tree1 so, I test with the subtrees of root
  return tree1_contained_in_tree2(tree1->left, tree2) && 
         tree1_contained_in_tree2(tree1->right, tree2);    
}

Prefiero usar punteros simples a nodos en lugar de punteros dobles. Creo que puedes adaptar mi enfoque al tuyo.

El algoritmo es O(n log m) si tree2 está equilibrado ( O(nm) contrario) donde n es el número de nodos de tree1 m el número de nodos de tree2