algorithm - Cómo calcular punteros en un árbol binario con el diseño de van Emde Boas

binary-tree cache-oblivious

Question

Me gustaría implementar un árbol binario sin memoria caché que se almacene en una matriz utilizando el diseño de van Emde Boas, utilizando punteros implícitos. Todos los elementos del árbol son enteros de 32 bits y el árbol será bastante grande, por lo que almacenar los punteros significaría al menos 3 veces más datos.

El problema es que no se me ocurre ninguna manera no iterativa de calcular los punteros a los elementos secundarios izquierdo y derecho, dado un índice de nodo (puedo rastrear cualquier información mientras atravieso el árbol). Muchos artículos / conferencias se refieren a tales árboles con punteros implícitos, pero no he visto un algoritmo para calcular los punteros. ¿Hay una manera eficiente de hacerlo?

Answer 1

Bob Copeland tiene una muy buena implementación de los árboles de van Emde Boas en GitHub . Utiliza punteros implícitos y calcula los punteros calculando primero el puntero de amplitud, después de lo cual los punteros de vEB son un condicional simple.