Atree: implementación de Tree simple y eficiente sin punteros

• Apter Trees en C++
• Un árbol representado de forma simple usando solo dos vectores: [valor del nodo, índice del padre)
• La mayoría de los árboles se implementan como árboles binarios, donde cada nodo incluye su valor y punteros a sus nodos hijo izquierdo/derecho
• Este tipo de estructura de datos suele requerir implementación recursiva y puede ser lenta por el comportamiento de caché y las llamadas frecuentes a malloc()
• El concepto de quién "posee" un nodo del árbol puede volverse complejo en software de múltiples capas
• Los árboles Apter son mucho más rápidos, más fáciles de razonar y más fáciles de implementar

Cómo funciona

• Se implementa con dos arreglos del mismo tamaño
  • Un vector (arreglo) de datos d
  • Un vector p de índices de padre. El índice del vector d se usa como clave (c)
  • A menudo la clave/índice c es de tipo entero
• Si Coco es el padre de Molly y Arca, y Arca tiene un hijo llamado Cricket, la estructura queda así
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• El nodo cuyo padre es 0 y cuya clave es 0 es el nodo raíz (en los árboles Apter el nodo raíz es obligatorio, o bien -1 significa "sin padre", pero aquí eso se omite)
• Las computadoras pueden manipular vectores muy rápido. Como esto es mucho más veloz que las operaciones con punteros, comparar la notación Big-O de los algoritmos en la práctica no tiene mucho sentido

Importancia

• Este estilo de implementación es el más elegante entre las implementaciones de árboles que el autor ha visto
• Si se usa una biblioteca adecuada de operaciones con vectores, es fácil de entender y de encontrar errores
• Por su simplicidad, puede adaptarse fácilmente a otros escenarios de uso
• Se puede iterar rápidamente sobre los valores ignorando el vector de índices de padre, lo que equivale a tener un Deep Map gratis
• Es amigable con GPU y fácil de usar en entornos embebidos
• La seguridad puede mantenerse fácilmente evitando que el tamaño de los vectores crezca más allá de cierto límite

Origen

• El autor está intentando encontrar a la persona que inventó esta técnica y supone que ya tenía nombre en la era orientada a vectores de los años 60 y 70
• Vio por primera vez una descripción completa tal como la explicó Apter, aunque también está ampliamente documentada en K3
• APL implementa árboles de la forma tradicional, pero usa una técnica similar para grafos vectoriales
• También es conocida entre usuarios de J, y existe una explicación sobre la implementación de árboles en J en Rosetta Code
• John Earnest explica con más detalle la implementación de árboles vectoriales, incluyendo el enfoque de "índice con desplazamiento" para manejar elementos eliminados
• Un enfoque más complejo consiste en rastrear la profundidad de cada elemento

Otras implementaciones comunes de árboles

• Existen implementaciones como el árbol del kernel de FreeBSD, los árboles de klib, la clase Tree de Ruby y clases de árboles declarativos en Python
• No realizan exactamente la misma función que los árboles Apter, y algunas son mucho más grandes debido a su generalización

Estado actual de este código

• Es un intento de implementarlo como ejercicio para aprender C++17
• Todavía no está listo para usarse y el autor necesita aprender más sobre C++

Opinión de GN⁺

• Apter Trees simplifica las estructuras de árbol complejas existentes y permite una gestión de datos rápida y eficiente
• La implementación de árboles basada en vectores minimiza la sobrecarga de memoria y puede mejorar el rendimiento mediante acceso lineal
• Este artículo resulta interesante para explorar enfoques innovadores de estructuras de datos en ingeniería de software

[GN⁺]

Opiniones en Hacker News

• Un usuario expresó su sorpresa al ver que su trabajo estaba enlazado en Hacker News. Comentó que le interesan mucho las estructuras de datos ligeras basadas en arreglos, y mencionó en particular una implementación que se usa con frecuencia para árboles de nodos en el skinning de modelos 3D. Explicó que, si el arreglo se ordena para que los nodos padre aparezcan antes que sus hijos, recalcular la transformación global de todos los nodos puede resolverse con un simple bucle.
• Otro usuario, en respuesta a un comentario que decía que iterar los nodos hijos en este estilo de árbol es O(N), mencionó que en realidad es fácil generalizar el diseño de atree agregando punteros al "primer hijo" y al "siguiente hermano". También recomendó modificar la estructura de datos para que soporte las operaciones necesarias.
• Un usuario afirmó que almacenar los nodos en un arreglo y usar índices como punteros es esencial para implementar algoritmos de árboles. En particular, aconsejó considerar estructuras separadas para nodos internos y nodos hoja si se necesita acceder a los hijos de un nodo, con el fin de ahorrar memoria.
• Otro usuario comentó que le parecía algo extraño que una forma de representar árboles con un arreglo de padres recibiera tanto interés en Hacker News. Consideró que eso muestra hasta dónde puede llevar una buena presentación una idea básica.
• Un usuario señaló que este proyecto no es más que reemplazar los punteros del sistema por punteros propios.
• Otro usuario sugirió probar una implementación tradicional de árbol con un pool de nodos si lo que se busca es reducir los malloc y mejorar la localidad de los datos.
• Hubo un comentario recomendando consultar la explicación de Aaron Hsu usando APL.
• Un usuario propuso cambiar la estructura para empaquetar juntos todos los hijos de un nodo. Mencionó que así se podría encontrar la lista completa de hijos de un nodo con búsqueda binaria y obtener propiedades favorables para la caché.
• Hubo un comentario sobre llamar a los índices dentro del arreglo "handles" o "index-handles", y mencionó que esta forma de representar árboles recuerda a estructuras de datos clásicas como el heap y los conjuntos disjuntos.
• Por último, hubo un comentario explicando que los índices de un arreglo también pueden considerarse una especie de "puntero", y que las implementaciones tradicionales de árboles requieren malloc por la necesidad de agregar o quitar nodos dinámicamente. Mencionó que una implementación con arreglos puede ser adecuada si el tamaño del árbol es limitado y no se eliminan nodos con frecuencia.