data structures - delete - ¿Cuál es la representación de un árbol del hijo de la izquierda y el hermano de la derecha? ¿Por qué lo usarías?

b+ tree

Question

Muchas estructuras de datos almacenan árboles de múltiples vías como árboles binarios utilizando una representación llamada representación "hijo izquierdo, hermano derecho" . ¿Qué significa esto? ¿Por qué lo usarías?

Answer 1

La representación del hijo derecho e hija (LCRS) es una forma de codificar un árbol de múltiples vías (una estructura de árbol en la que cada nodo puede tener cualquier número de hijos) utilizando un árbol binario (una estructura de árbol en la que cada nodo puede tener a lo más dos hijos).

Motivación

Para motivar cómo funciona esta representación, comencemos considerando un árbol de múltiples vías simple, como este aquí:

                   A
                 //|/ /
               / / | /  /
              B C  D  E  F
              |   /|/   / /
              G  H I J K   L

(¡Disculpas por la obra de arte ASCII de baja calidad!)

En esta estructura de árbol, podemos navegar hacia abajo desde cualquier nodo en el árbol a cualquiera de sus hijos. Por ejemplo, podemos migrar de A a B, de A a C, de A a D, etc.

Si quisiéramos representar un nodo en un árbol como este, normalmente usaríamos algún tipo de estructura de nodo / clase de nodo como esta aquí (escrito en C ++):

struct Node {
    DataType value;
    std::vector<Node*> children;
};

En la representación de LCRS, representamos el árbol de múltiples vías de una manera en que cada nodo requiere a lo sumo dos punteros. Para ello, remodelaremos un poco el árbol. En lugar de tener cada nodo en el árbol, los punteros a todos sus hijos, estructuraremos el árbol de una manera ligeramente diferente al hacer que cada nodo almacene un puntero a uno de sus hijos (en LCRS, el niño más a la izquierda). Luego, cada nodo almacenará un puntero a su hermano derecho, el siguiente nodo en el árbol que es el hijo del mismo nodo principal. En el caso del árbol anterior, podríamos representar el árbol de la siguiente manera:

            A
           /
          /
         /
        B -> C -> D -> E -> F
       /         /         /
      G         H->I->J   K->L

Tenga en cuenta que en esta nueva estructura aún es posible navegar desde un nodo principal a su kth hijo (indexado a cero). El procedimiento para hacerlo es el siguiente:

• Desciende al lado izquierdo del nodo actual. (Este es el primer nodo en la lista de sus hijos).
• Sigue al niño con el puntero derecho k veces. (Esto te lleva al kth hijo del nodo).
• Devuelve ese nodo.

Por ejemplo, para encontrar el tercero (hijo con indexación cero) del nodo raíz A, descenderíamos al hijo situado más a la izquierda (B), luego seguiremos tres enlaces a la derecha (visitando B, C, D y finalmente E). Luego llegamos al nodo para E, que contiene el tercer hijo del nodo A.

La razón principal para representar el árbol de esta manera es que aunque cualquier nodo puede tener cualquier número de hijos, la representación requiere a lo sumo dos punteros para cada nodo: un nodo para almacenar el hijo del extremo izquierdo y un puntero para almacenar el hermano derecho. Como resultado, podemos almacenar el árbol de múltiples vías utilizando una estructura de nodos mucho más simple:

struct Node {
    DataType data;
    Node* leftChild;
    Node* rightSibling;
};

Esta estructura de nodo tiene exactamente la misma forma de un nodo en un árbol binario (datos más dos punteros). Como resultado, la representación LCRS hace posible representar un árbol de múltiples vías arbitrario utilizando solo dos punteros por nodo.

Análisis

Veamos ahora la complejidad de tiempo y espacio de las dos representaciones diferentes del árbol de varias vías y algunas operaciones básicas en él.

Comencemos por observar el uso total de espacio requerido para la representación inicial de "matriz dinámica de elementos secundarios". ¿Cuánto uso total de memoria habrá para un árbol de n nodos? Bueno, sabemos lo siguiente:

1. Cada nodo, independientemente de su número de hijos, contribuye con espacio para los datos sin procesar almacenados (sizeof (datos)) y la sobrecarga de espacio de la matriz dinámica. La matriz dinámica (normalmente) tiene un puntero almacenado (que apunta a la matriz asignada), una palabra de máquina para el número total de elementos en la matriz dinámica y (opcionalmente) una palabra de máquina para la capacidad asignada de la matriz. Esto significa que cada nodo ocupa espacio de sizeof (Data) + sizeof (Node *) + 2 * sizeof (palabra de máquina).

2. A través de todas las matrices dinámicas en el árbol, habrá n - 1 punteros a los niños, ya que de los n nodos en el árbol n - 1 de ellos tienen padres. Eso agrega un factor extra (n - 1) * sizeof (Nodo *).

Por lo tanto, el uso total del espacio es

n · (tamaño de (Datos) + tamaño de (Nodo *) + 2 * tamaño de (palabra de máquina)) + (n - 1) * tamaño de (Nodo *)

= n * sizeof (Data) + (2n - 1) * sizeof (Node *) + 2n * sizeof (palabra de máquina)

Ahora, contrastemos eso con un árbol LCRS. Cada nodo en un árbol LCRS almacena dos punteros (2 * sizeof (Node *)) y un elemento de datos (sizeof (Data)), por lo que su espacio total es

n * sizeof (Data) + 2n * sizeof (Node *)

Y aquí vemos la victoria: observe que no estamos almacenando 2n * sizeof (palabra de máquina) memoria adicional para realizar un seguimiento de los tamaños de matriz asignados. Esto significa que la representación de LCRS usa considerablemente menos memoria que un árbol de múltiples vías regular.

Sin embargo, las operaciones básicas en la estructura del árbol LCRS tienden a tomar más tiempo que sus operaciones correspondientes en el árbol de múltiples vías normal. Específicamente, en un árbol multidireccional representado en la forma estándar (cada nodo almacena una matriz de punteros secundarios), el tiempo requerido para navegar desde un nodo a su kth secundario viene dado por el tiempo requerido para seguir un solo puntero. Por otro lado, en la representación de LCRS, el tiempo requerido para hacer esto viene dado por el tiempo requerido para seguir los punteros k + 1 (un puntero izquierdo izquierdo, luego los punteros secundarios derecho). Como resultado, si el árbol tiene un factor de ramificación grande, puede ser mucho más lento realizar búsquedas en una estructura de árbol LCRS que en la estructura de árbol de múltiples vías correspondiente.

Por lo tanto, podemos pensar que la representación de LCRS ofrece un intercambio de espacio-tiempo entre el espacio de almacenamiento de la estructura de datos y los tiempos de acceso. La representación de LCRS tiene menos sobrecarga de memoria que el árbol de múltiples vías original, mientras que el árbol de múltiples vías ofrece búsquedas de tiempo constante de cada uno de sus hijos.

Casos de uso

Debido a la compensación de espacio-tiempo involucrada en la representación de LCRS, la representación de LCRS normalmente no se usa a menos que se cumpla uno de los dos criterios:

1. La memoria es extremadamente escasa, o
2. No se requiere el acceso aleatorio de los hijos de un nodo.

El caso (1) podría surgir si necesitara almacenar un árbol de múltiples vías asombrosamente enorme en la memoria principal. Por ejemplo, si necesita almacenar un árbol filogenético que contiene muchas especies diferentes sujetas a actualizaciones frecuentes, entonces la representación de LCRS podría ser apropiada.

El caso (2) surge en estructuras de datos especializadas en las que la estructura de árbol se está utilizando de manera muy específica. Por ejemplo, muchos tipos de estructuras de datos de pila que utilizan árboles de múltiples vías pueden optimizarse en el espacio usando la representación LCRS. La razón principal de esto es que en las estructuras de datos del montón, las operaciones más comunes tienden a ser

1. Remueve la raíz de un árbol y procesa cada uno de sus hijos, o
2. Unir dos árboles juntos haciendo que un árbol sea hijo del otro.

La operación (1) se puede hacer de manera muy eficiente en la representación de LCRS. En una representación de LCRS, la raíz del árbol nunca tiene un hijo derecho (ya que no tiene hermanos), y por lo tanto, eliminar la raíz simplemente significa despegar el nodo raíz y descender a su subárbol izquierdo. A partir de ahí, el procesamiento de cada niño se puede hacer simplemente recorriendo la espina derecha del árbol restante y procesando cada nodo por turno.

La operación (2) también se puede hacer de manera muy eficiente. Recuerde desde arriba que en una representación de LCRS, la raíz de un árbol nunca tiene un hijo derecho. Por lo tanto, es muy fácil unir dos árboles en la representación de LCRS de la siguiente manera. Comenzando con dos árboles como este:

    R1             R2
   /               /
 (children 1)    (children 2)

Podemos fusionar los árboles de esta manera:

             R1
            /
           R2
          /  /
(children 2) (children 1)

Esto se puede hacer en tiempo O (1), y es bastante simple. El hecho de que la representación de LCRS tenga esta propiedad significa que muchos tipos de colas de prioridad del montón, como el montón binomial o el montón de emparejamiento de rangos se representan típicamente como árboles LCRS.

¡Espero que esto ayude!