Me gustaría implementar un árbol binario sin memoria caché que se almacena en una matriz utilizando el diseño de van Emde Boas, utilizando punteros implícitos. Todos los elementos en el á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.Cómo calcular punteros en un árbol binario con el diseño de van Emde Boas
El problema es que no se me ocurre ninguna forma no iterativa de calcular punteros a los secundarios izquierdo y derecho, dado un índice de nodo (puedo rastrear cualquier información al atravesar el árbol). Muchos documentos/conferencias se refieren a dichos árboles con punteros implícitos, pero no he visto un algoritmo para calcular los punteros. ¿Hay una forma eficiente de hacerlo?
¿Necesita calcularlo desde un índice? Me parece que solo necesita calcular un nodo hijo particular a partir de un nodo actual. Si está dispuesto a conocer el nivel actual, mantener una pila de compensaciones en la ruta al nodo actual y tener una matriz de todas las compensaciones en diferentes niveles, debería poder hacerlo. No sé cuánto agregará el seguimiento aéreo que agregarán esas pilas, puede que no valga la pena. – btilly
Tiene razón, no necesito calcularlo a partir de un índice arbitrario. No estoy seguro de entender la idea con una matriz para todas las compensaciones? ¿Quieres decir compensaciones para todos los artículos en un nivel específico? –
¿Ha marcado [este documento] (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.762&rep=rep1&type=pdf) fuera? Explican cómo diseñar un árbol utilizando el diseño de Van Emde Boas en la sección 2.1. – jswolf19