Barrapunto

¿serán algo así [aymanh.com]?

Sí, más o menos. Lo de usar índices en lugar de punteros es muy importante para evitar desaprovechar la cache de datos, pues puede provocar que el programa se ralentize un orden de magnitud a base de fallos de cache. En el caso de CPUs de 64 bits, los punteros para manejo de estructuras de datos complejas, son directamente inviables.

Normalmente se tiende a rizar un poco el rizo en el uso de índices. En el caso concreto de un árbol (ya sea binario, enario, B, etc.), se puede usar la propia topología del árbol a modo de contador implícito, necesitando menos bits para direccionar más nodos.

Ejemplo incompleto, para que se vea la idea:

enum eNodeConfig
{

NC_RefTypeBits = 2,
NC_SubContextBits = 16,
NC_IndexBits = 14,
NC_SubContextMask = (1<<NC_SubContextBits)-1,
NC_IndexMask = (1<<NC_IndexBits)-1,

};

struct NodeGlobalRef // sizeof(NodeGlobalRef) = 4 bytes (32 bits)
{

unsigned char type : NC_RefTypeBits; // S-simple, M-multiplexed, T-look-up-table
unsigned short subcontext : NC_SubContextBits ;
unsigned short index : NC_IndexBits;

};
struct NodeLocalRef // sizeof(NodeLocalRef) = 2 (16 bits)
{

unsigned char type : NC_RefTypeBits ; // S-simple, M-multiplexed, T-look-up-table
unsigned short index : NC_IndexBits;

};
struct NodeM_Local // sizeof(NodeM_Local) = 16 (256 bits)
{ // 16 * 16 bits = 64 bytes

enum eNodeM_Cfg // Para dimensionar este nodo de múltiples referencias, en C++ se podría usar un template en lugar del enum.
{

NC_MaxRefs = 16

};

NodeLocalRef nodes[NC_MaxRefs];

// ... añadir elementos de control para el árbol, etc.

};

//...

Se puede observar que sólo he puesto 14 bits para direccionamiento, se correspondería con el bloque de reserva de memoria, i.e., se haría una reserva de memoria por cada 2^14 nodos direccionables (16384). En el caso de grafos la gestión de la localidad es algo más complicada que en el caso de los árboles, pues la localidad tendría que gestionarse de manera explícita en la estructura de datos (imagina como si se tratase de un sistema solar, tendrías los nodos cercanos unidos por referencias locales, y los saltos interplanetarios, mediante referencias globales).

No respondí adecuadamente en el post anterior: Efectivamente, es posible tener un arbol binario sin punteros ni índices, sería el caso de una lista ordenada (p.e. para hacer una búsqueda dicotómica/binaria). El caso que comentaba en el otro post, era para un caso de un arbol sin restricciones, con reasignaciones, balanceado, etc.