Binäre Baumstruktur - "Links" statt Zeiger auf Elternknoten

[sunny1975]

Hallo Allerseits,

wir habe folgende Aufgabenstellung erhalten:

"Ein optimaler, links-orientierter binärer Baum, der die Heap-Bedingung erfüllt (kurz: Heap), soll dynamisch implementiert (die Knoten im Baum werden also zur Laufzeit des Programms dynamisch allokiert) und persistent gemacht werden. Aus Gründen der Speicherplatzersparnis wird in einem Knoten kein Zeiger auf den Elternknoten unterhalten, sondern jeder Knoten enthält neben dem Atom zwei sogenannte Links: Ein Link wird aus der Adresse des Elternknotens und der Adresse des entsprechenden Kindknotens durch die bitweise Exklusiv-ODER-Verknüpfung berechnet. Hierbei wird angenommen, dass die Adresse des Elternknotens der Wurzel und die Adresse des Kindknotens eines Blattes 0 ist.
(...)"

Kann mir kein Bild davon machen, was mit "Links" gemeint sein könnte. Kann mir jemand auf die Sprünge helfen. Bin für jeden Hinweis dankbar.

Viele Grüsse, sunny

PS: Die Aufgabe ist komplett unter http://www.cs.fhm.edu/~prinz/vorlesung/Praktikum/html/Heap.html beschrieben.

[elise]

vielleicht doch nicht ganz richtig..
muss ich nochmal denken...

[finix]

sunny1975 schrieb:

Kann mir kein Bild davon machen, was mit "Links" gemeint sein könnte. Kann mir jemand auf die Sprünge helfen. Bin für jeden Hinweis dankbar.

Kleine Anregung:

node* parent = new node;
node* left = new node;
node* right = new node;

// ...

long left_link = reinterpret_cast<long>(parent) ^ reinterpret_cast<long>(left);
long right_link = reinterpret_cast<long>(parent) ^ reinterpret_cast<long>(right);

[otze]

und wie soll man das am ende wieder auseinanderpuzzlen können?

[ness]

selbst wenn (zu xor gibts de ne umkehroperation - xor?), was soll das bringen. "...aus gründen der Speicherplatzersparnis..." hä? was bringt ein xor speicherplatzersparnis?

[finix]

ness schrieb:

selbst wenn (zu xor gibts de ne umkehroperation - xor?), was soll das bringen. "...aus gründen der Speicherplatzersparnis..." hä? was bringt ein xor speicherplatzersparnis?

2 * sizeof(void*) < 3 * sizeof(void*), meinst du nicht?

[maximAL]

otze schrieb:

und wie soll man das am ende wieder auseinanderpuzzlen können?

hmm, frag ich mich auch grad (vorallem, da ichs auch grad gebrauch könnte )