Almacenamiento de matriz eficiente para árbol binario

Question

Tenemos que escribir los nodos de un árbol binario en un archivo. ¿Cuál es la forma más eficiente de escribir un árbol binario en el espacio? Podemos almacenarlo en formato de matriz con el padre en la posición i y sus hijos en 2i, 2i+1. Pero esto perderá mucho espacio en el caso de árboles binarios dispersos.

Answer 1

Un método que me gusta es almacenar el recorrido de preorden, pero también incluye los nodos 'nulos' allí. Almacenar los nodos 'nulos' elimina la necesidad de almacenar también el orden del árbol.

Algunas de las ventajas de este método

• Puede hacer un mejor almacenamiento de pre/post + finde método en los casos más prácticas.
• La serialización solo toma un recorrido
• La deserialización se puede hacer en una sola pasada.
• El recorrido inorden se puede obtener en una sola pasada sin construir el árbol, lo que podría ser útil si la situación así lo requiere.

Por ejemplo decir que tenía un árbol binario de enteros de 64 bits, puede almacenar un bit adicional después de cada nodo diciendo si el siguiente es un nodo nulo o no (el primer nodo siempre es el raíz). Nodos nulos, puede representar por un solo bit.

Entonces, si hay n nodos, el uso del espacio sería de 8n bytes + n-1 bits indicadores + n + 1 bits para nulos nulos = 66 * n bits.

En el orden pre/post + terminará utilizando 16n bytes = 128 * n bits.

Así ahorras un espacio de 62 * n bits sobre este método pre/post + inorder.

Considérese el árbol

 100 
    / \ 
    / \ 
    /  \ 
    10  200 
/\  /\ 
. .  150 300 
     /\ /\ 
     . . . . 

donde el '' son los nodos nulos.

Usted serializarlo como 100 10 . . 200 150 . . 300 . .

Ahora cada uno (incluyendo sub-estructuras) 'recorrido en preorden con nulo' tiene la propiedad de que el número de nodos nulos = número de nodos + 1.

Esto le permite crear el árbol, dada la versión serializada en una sola pasada, ya que el primer nodo es la raíz del árbol. Los nodos que siguen son el subárbol izquierdo seguido de la derecha, que se puede ver por qué ser así:

100 (10 . .) (200 (150 . .) (300 . .)) 

Para crear el recorrido en orden, se utiliza una pila y empujar cuando vea un nodo y el pop (en una lista) cuando veas un nulo. La lista resultante es el recorrido inorden (una explicación detallada de esto se puede encontrar aquí: C++/C/Java: Anagrams - from original string to target;).

Answer 2

Puede guardar el recorrido in-order y pre/post-order del árbol binario en el archivo y reconstruir el árbol de estos recorridos.

Answer 3

El método 2i, 2i + 1 (Binary Heap) es de hecho la mejor manera si tiene un árbol (casi) completo.

De lo contrario, no podrá escapar almacenando un ParentId (índice padre) con cada nodo.

Answer 4

Piensa en XML. Es un tipo de serialización de árbol. Por ejemplo:

<node id="1"> 
    <node id="2">         1 
    </node>          / \ 
    <node id="3">        2  3 
     <node id="4">        /\ 
     </node>          4 5 
     <node id="5"> 
     </node> 
    </node> 
</node> 

Entonces, ¿por qué los espacios y las etiquetas? Podemos omitirlos, paso a paso:

<1> 
    <2></> 
    <3> 
    <4></> 
    <5></> 
    </> 
</> 

Quitar los espacios: <1><2></2><3><4></><5></></></>.

quitar los paréntesis angulares: 12/34/5///

Ahora el problema es: ¿qué pasaría si un nodo tiene un subárbol izquierdo vacío y el subárbol derecho no vacío? Luego podemos usar otro carácter especial, '#' para representar un subárbol izquierdo vacío.

Por ejemplo:

1 
/ \ 
     2 
    /\ 
    3 

Este árbol se puede serializar como: 1#23///.