Toda estructura de árbol multidireccional o k-ario estudiada en informática admite una representación como árbol binario , que tiene varios nombres, entre ellos representación hijo-hermano , [1] árbol binario hijo izquierdo, hermano derecho , [2] árbol doblemente encadenado o cadena filial-heredero . [3]
En un árbol binario que representa un árbol multidireccional T , cada nodo corresponde a un nodo en T y tiene dos punteros : uno al primer hijo del nodo y otro a su hermano siguiente en T. Los hijos de un nodo forman así una lista enlazada simple . Para encontrar el k -ésimo hijo de un nodo n , es necesario recorrer esta lista:
procedimiento kth-child(n, k): niño ← n.niño mientras k ≠ 0 y niño ≠ nulo: niño ← niño.hermano-próximo k ← k − 1 devolver hijo // puede devolver nulo
El proceso de conversión de un árbol k-ario a un árbol binario LC-RS a veces se denomina transformada de Knuth . [4] Para formar un árbol binario a partir de un árbol k-ario arbitrario mediante este método, la raíz del árbol original se convierte en la raíz del árbol binario. Luego, comenzando con la raíz, el hijo más a la izquierda de cada nodo en el árbol original se convierte en su hijo izquierdo en el árbol binario, y su hermano más cercano a la derecha en el árbol original se convierte en su hijo derecho en el árbol binario.
Los árboles doblemente encadenados fueron descritos por Edward H. Sussenguth en 1963. [5]
Al transformar un árbol k-ario en un árbol binario LC-RS, cada nodo está vinculado y alineado con el hijo izquierdo, y el siguiente más cercano es un hermano. Por ejemplo, tenemos un árbol ternario a continuación:
1 /|\ / | \ / | \ 2 3 4 / \ | 5 6 7 / \ 8 9
Podemos reescribirlo colocando el nodo hijo izquierdo un nivel por debajo de sus padres y colocando el hermano al lado del hijo en el mismo nivel: será lineal (la misma línea).
1 / / / 2---3---4 / / 5---6 7 / 8---9
Podemos transformar este árbol en un árbol binario girando cada hermano 45° en el sentido de las agujas del reloj. [6]
1 / 2 / \ 5 3 \ \ 6 4 / 7 / 8 \ 9
La representación LCRS es más eficiente en términos de espacio que un árbol multidireccional tradicional, pero tiene el costo de que la búsqueda de los hijos de un nodo por índice se vuelve más lenta. Por lo tanto, la representación LCRS es preferible si
El caso (1) se aplica cuando se necesitan árboles multidireccionales grandes, especialmente cuando los árboles contienen un gran conjunto de datos. Por ejemplo, si se almacena un árbol filogenético , la representación LCRS podría ser adecuada.
El caso (2) surge en estructuras de datos especializadas en las que la estructura de árbol se utiliza de formas muy específicas. Por ejemplo, muchos tipos de estructuras de datos de montón que utilizan árboles multidireccionales se pueden optimizar en términos de espacio mediante el uso de la representación LCRS. (Los ejemplos incluyen montones de Fibonacci , montones de emparejamiento y montones débiles ). La razón principal de esto es que en las estructuras de datos de montón, las operaciones más comunes tienden a ser
La operación (1) es muy eficiente. En la representación LCRS, organiza el árbol para que tenga un hijo derecho porque no tiene un hermano, por lo que es fácil eliminar la raíz.
La operación (2) también es eficiente. Es fácil unir dos árboles. [7]
Este artículo incorpora material de dominio público de Paul E. Black. "Representación de árboles en forma de árbol binario". Diccionario de algoritmos y estructuras de datos . NIST .