data-structures - complexity - tree data structure

Quiere guardar un árbol binario en el disco para el juego "20 preguntas"

Question

En resumen, me gustaría aprender / desarrollar un método elegante para guardar un árbol binario en el disco (un árbol general, no necesariamente un BST). Aquí está la descripción de mi problema:

Estoy implementando un juego de "20 preguntas". He escrito un árbol binario cuyos nodos internos son preguntas y las hojas son respuestas. El hijo izquierdo de un nodo es la ruta que seguiría si alguien respondiera "sí" a su pregunta actual, mientras que el hijo correcto es una respuesta "no". Tenga en cuenta que este no es un árbol de búsqueda binario, solo un árbol binario cuyo hijo izquierdo es "sí" y el derecho es "no".

El programa agrega un nodo a un árbol si encuentra una hoja que es nula al pedirle al usuario que distinga su respuesta de la que estaba pensando la computadora.

Esto es claro, porque el árbol se construye a medida que el usuario juega. Lo que no es bueno es que no tengo una buena manera de guardar el árbol en el disco.

He pensado en guardar el árbol como una representación de matriz (para el nodo i, el hijo izquierdo es 2i + 1 y 2i + 2 correcto, (i-1) / 2 para el padre), pero no está limpio y termino con una gran cantidad de espacio perdido.

¿Alguna idea para una solución elegante para guardar un árbol binario disperso en el disco?

Answer 1

La forma más simple y arbitraria es simplemente un formato básico que se puede usar para representar cualquier gráfico.

<parent>,<relation>,<child>

Es decir:

"Is it Red", "yes", "does it have wings" 
"Is it Red", "no" , "does it swim"

No hay mucha redundancia aquí, y los formatos en su mayoría legibles por humanos, la única duplicación de datos es que debe haber una copia de un padre por cada hijo directo que tenga.

Lo único que realmente debes observar es que no generas accidentalmente un ciclo;)

A menos que eso sea lo que quieres.

El problema aquí es reconstruir el árbol después. Si creo el objeto "¿tiene alas?" Al leer la primera línea, tengo que ubicarlo de alguna manera cuando más tarde encuentro la línea que dice "¿tiene alas?", "Sí", "¿Tiene un pico?"

Esta es la razón por la que tradicionalmente uso estructuras de gráficos en memoria para tal cosa con punteros que van a todas partes.

[0x1111111 "Is It Red"           => [ ''yes'' => 0xF752347 , ''no'' => 0xFF6F664 ], 
 0xF752347 "does it have wings"  => [ ''yes'' => 0xFFFFFFF , ''no'' => 0x2222222 ], 
 0xFF6F664 "does it swim"        => [ ''yes'' => "I Dont KNOW :( " , ... etc etc ]

Entonces la conectividad "hijo / padre" es meramente metadatos.

Answer 2

No estoy seguro de que sea elegante, pero es simple y explicable: asigne una ID única a cada nodo, ya sea raíz o hoja. Un entero de conteo simple servirá.

Al guardar en el disco, recorra el árbol, almacenando cada ID de nodo, ID de enlace "sí", ID de enlace "no" y el texto de la pregunta o respuesta. Para enlaces nulos, use cero como el valor nulo. Puede agregar una bandera para indicar si la pregunta o respuesta, o más simplemente, verificar si ambos enlaces son nulos. Deberías obtener algo como esto:

1,2,3,"Does it have wings?"
2,0,0,"a bird"
3,4,0,"Does it purr?"
4,0,0,"a cat"

Tenga en cuenta que si utiliza el enfoque de enteros secuenciales, guardar la ID del nodo puede ser redundante, como se muestra aquí. Podrías ponerlos en orden por ID.

Para restaurar desde el disco, lea una línea y luego agréguela al árbol. Es probable que necesite una tabla o matriz para mantener los nodos referenciados hacia adelante, por ejemplo, al procesar el nodo 1, necesitará hacer un seguimiento de 2 y 3 hasta que pueda completar esos valores.

Answer 3

Puedes almacenarlo recursivamente:

 void encodeState(OutputStream out,Node n) {
        if(n==null) {
            out.write("[null]");
        } else {
           out.write("{");
           out.write(n.nodeDetails());
           encodeState(out, n.yesNode());
           encodeState(out, n.noNode());
           out.write("}");
        }
  }

Diseña tu propio formato de salida menos texty. Estoy seguro de que no necesito describir el método para leer el resultado resultante.

Este es un recorrido transversal en profundidad. La primera parte funciona también.

Answer 4

Una forma simple de lograr esto es recorrer el árbol dando salida a cada elemento a medida que lo hace. Luego, para volver a cargar el árbol, simplemente itere a través de su lista, insertando cada elemento de nuevo en el árbol. Si su árbol no se equilibra a sí mismo, es posible que desee reordenar la lista de tal manera que el árbol final esté razonablemente equilibrado.

Answer 5

En java, si tuviera que hacer una clase serializable, puede simplemente escribir el objeto de la clase en el disco y leerlo de nuevo usando flujos de entrada / salida.

Answer 6

Guardaría el árbol así:

<node identifier>
node data
[<yes child identfier>
  yes child]
[<no child identifier>
  no child]
<end of node identifier>

donde los nodos secundarios son solo ejemplos recursivos de lo anterior. Los bits en [] son ​​opcionales y los cuatro identificadores son solo constantes / valores enum.

Answer 7

Aquí está el código C ++ usando PreOrder DFS:

void SaveBinaryTreeToStream(TreeNode* root, ostringstream& oss)
{
    if (!root)
    {
        oss << ''#'';
        return;
    }

    oss << root->data;
    SaveBinaryTreeToStream(root->left, oss);
    SaveBinaryTreeToStream(root->right, oss);
}
TreeNode* LoadBinaryTreeFromStream(istringstream& iss)
{
    if (iss.eof())
        return NULL;

    char c;
    if (''#'' == (c = iss.get()))
        return NULL;

    TreeNode* root = new TreeNode(c, NULL, NULL);
    root->left  = LoadBinaryTreeFromStream(iss);
    root->right = LoadBinaryTreeFromStream(iss);

    return root;
}

En main() , puedes hacer:

ostringstream oss;
root = MakeCharTree();
PrintVTree(root);
SaveBinaryTreeToStream(root, oss);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream(iss);
PrintVTree(root);
ClearTree(root);

/* Output:
               A

       B               C

   D               E       F

     G           H   I
ABD#G###CEH##I##F##
ABD#G###CEH##I##F##
               A

       B               C

   D               E       F

     G           H   I
 */

El DFS es más fácil de entender.

*********************************************************************************

Pero podemos usar el análisis de nivel BFS usando una cola

ostringstream SaveBinaryTreeToStream_BFS(TreeNode* root)
{
    ostringstream oss;

    if (!root)
        return oss;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty())
    {
        TreeNode* tn = q.front(); q.pop();

        if (tn)
        {
            q.push(tn->left);
            q.push(tn->right);
            oss << tn->data;
        }
        else
        {
            oss << ''#'';
        }
    }

    return oss;
}
TreeNode* LoadBinaryTreeFromStream_BFS(istringstream& iss)
{
    if (iss.eof())
        return NULL;

    TreeNode* root = new TreeNode(iss.get(), NULL, NULL);
    queue<TreeNode*> q; q.push(root); // The parents from upper level
    while (!iss.eof() && !q.empty())
    {
        TreeNode* tn = q.front(); q.pop();

        char c = iss.get();
        if (''#'' == c)
            tn->left = NULL;
        else
            q.push(tn->left = new TreeNode(c, NULL, NULL));

        c = iss.get();
        if (''#'' == c)
            tn->right = NULL;
        else
            q.push(tn->right = new TreeNode(c, NULL, NULL));
    }

    return root;
}

En main() , puedes hacer:

root = MakeCharTree();
PrintVTree(root);
ostringstream oss = SaveBinaryTreeToStream_BFS(root);
ClearTree(root);
cout << oss.str() << endl;
istringstream iss(oss.str());
cout << iss.str() << endl;
root = LoadBinaryTreeFromStream_BFS(iss);
PrintVTree(root);
ClearTree(root);

/* Output:
               A

       B               C

   D               E       F

     G           H   I
ABCD#EF#GHI########
ABCD#EF#GHI########
               A

       B               C

   D               E       F

     G           H   I
 */

Answer 8

Haría un recorrido de nivel. Es decir, básicamente estás haciendo un algoritmo de búsqueda de primer orden .

Tienes:

1. Crea un qeueue con el elemento raíz insertado en él
2. Dequeue un elemento de la cola, llámalo E
3. Agregue los hijos izquierdo y derecho de E a la cola. Si no hay izquierda o derecha, simplemente ponga una representación de nodo nulo.
4. escribe el nodo E en el disco.
5. Repita desde el paso 2.

Secuencia de paso de nivel: F, B, G, A, D, I, C, E, H

Lo que almacenará en el disco: F, B, G, A, D, NullNode, I, NullNode, NullNode, C, E, H, NullNode

Cargarlo desde el disco es aún más fácil. Simplemente lea de izquierda a derecha los nodos que almacenó en el disco. Esto te dará los nodos izquierdo y derecho de cada nivel. Es decir, el árbol se completará de arriba a abajo de izquierda a derecha.

Paso 1 leyendo en:

F

Paso 2 leyendo en:

  F 
B

Paso 3 leyendo en:

  F 
 B  G

Paso 4 leyendo en:

   F 
 B  G
A

Y así ...

Nota: Una vez que tiene una representación de nodo NULL, ya no necesita enumerar sus hijos en el disco. Al cargar de nuevo sabrá saltar al siguiente nodo. Entonces, para árboles muy profundos, esta solución seguirá siendo eficiente.