Cómo guardar un árbol binario de búsqueda en un archivo

Escrito por amber d. walker | Traducido por juliana star
  • Comparte
  • Twittea
  • Comparte
  • Pin
  • E-mail
Cómo guardar un árbol binario de búsqueda en un archivo
Los árboles binarios de búsqueda tienen una apariencia similar a los árboles genealógicos. (Hemera Technologies/AbleStock.com/Getty Images)

Un árbol binario de búsqueda es una estructura de datos en la que los registros de la información, llamados "nodos", tienen punteros a otros nodos denominados "hijos". Esto le da a los nodos una apariencia similiar a un árbol genealógico cuando se grafican. Los nodos adquieren su lugar en el árbol en función de si serán evaluados como mayores o menores que otros nodos. Los hijos izquierdos siempre son menores que su padre y los hijos derechos siempre son mayores. Los árboles binarios de búsqueda son importantes en las ciencias computacionales debido a que permiten hacer ordenamientos y búsquedas en un tiempo promedio de O(n log n).

Nivel de dificultad:
Moderado

Otras personas están leyendo

Necesitarás

  • Un compilador
  • Un árbol binario de búsqueda existente

Lista completaMinimizar

Instrucciones

  1. 1

    Crea una función de almacenamiento que reciba el nodo raíz. Al trabajar con árboles en ciencias computacionales, el algoritmo más efectivo casi siempre será recursivo, y almacenar el árbol en un archivo no será la excepción. A continuación aparece una estructura de ejemplo de la función recursiva de almacenamiento (en Java).

    public void store(Node n) throws IOException { ... }

  2. 2

    Escribe la información del nodo raíz en el archivo. Este método usará el "recorrido en preorden" (Raíz, Hijo izquierdo, Hijo derecho) para moverse a través de todos los nodo del árbol, debido a que este método hará más sencillo reconstruir el árbol a partir del orden de los nodos en el archivo. La función recursiva se verá asi:

    public void store(Node n) throws IOException { write(savefile, n); } Store

    La función almacenar debe invocarse a sí misma con el hijo izquierdo:

    public void store(Node n) throws IOException { write(savefile, n); store(n.left); } Store should call itself with the Right Child: public void store(Node n) throws IOException { write(savefile, n); store(n.left); store(n.right) GO }

  3. 3

    Revisa nuevamente que la función pase la lista de verificación recursiva. Para evitar errores de desbordamiento de la pila, siempre debes verificar que una función recursiva cumpla las siguientes condiciones:

    ¿La función tiene un estado de salida? Sí, siempre y cuando el árbol no tenga una profundidad infinita, eventualmente llegará a un nodo que no tenga un hijo izquierdo ni derecho y terminará.

    ¿Cada iteración de la función se acerca al estado de salida? Sí, presumiendo que el árbol no sea circular y que ningún nodo tenga uno de sus propios ancestros como hijos.

    Por lo tanto, esta función pasa la lista de verificación.

  4. 4

    Reconstruye el árbol mediante el archivo. Cuando llegue el momento de cargar el árbol desde el archivo, simplemente deberás insertar cada nodo según sea cargado del archivo usando tu algoritmo estándar de inserción. Este debe iniciar en la raíz y moverse hacia abajo usando el recorrido en preorden, colocando el nodo nuevo en el primer espacio vacío en el que pueda quedarse. Esto debe reconstruir el árbol exactamente como se creó originalmente en un tiempo promedio de O(n log n).

Consejos y advertencias

  • Atrapa la excepción StackOverflowException. Si bien es poco probable que uses todo el espacio de la pila en una función recursiva correctamente escrita, si estás trabajando con Java asegúrate de atrapar la excepción StackOverflowException con todas tus funciones recursivas, de manera que puedas trabajar con ellas de forma limpia.
  • Atrapa la excepción IOException. Si la escritura en el archivo falla en algún momento del proceso, es mejor saber en qué momento se está escribiendo en el archivo, en vez de darte cuenta al leer un archivo corrupto.
  • No almacenes los punteros en el archivo. Un sencillo error guardará directamente las variables de los hijos izquierdos y derechos de cada nodo. En la mayoría de los lenguajes, estos se implementarían como punteros a direcciones de memoria. No hace falta decir que esas direcciones de memoria cambiarán en cada ejecución, por lo que almacenarlas en un archivo sería inútil.

No dejes de ver

Filtrar por:
  • Mostrar todos
  • Artículos
  • Galerías de fotos
  • Videos
Ordenar:
  • Más relevante
  • Más popular
  • Más reciente

No se encuentran artículos disponibles

No se encuentran slideshows disponibles

No se encuentran videos disponibles