6.4

[Freeek]

Hi Leute ...

täusch ich mich, oder ist der verlangte Pseudocode nicht eh schon 1:1 im Skriptum drinnen ?
Könnte mich auch täuschen, hat sich schon jemand damit befasst ?

Greetz, Freeek

[Shine]

Hi Leute ...

täusch ich mich, oder ist der verlangte Pseudocode nicht eh schon 1:1 im Skriptum drinnen ?


Genau das gleiche hab ich mir auch gedacht, wär aber bisschen dumm, wenn ma's nur abschreiben soll, aber vielleicht sind ihnen keine bsp mehr eingefallen...
ich erkenn jedenfalls nicht wirklich einen unterschied zu dem Algo im Skript.. Vielleicht kann ja jemand was genaueres dazu sagen..
mfg Shine

[Plastiktiger]

Zuerst hab ich mir das auch gedacht, jedoch die Angabe hat mich etwas verwirrt: i soll die Tiefe sein, an der S eingefügt wird. Vielleicht ist das so gemeint, dass erst an Tiefe i begonnen werden soll, S einzufügen. Dann ist die Frage allerdings, auf welchem Ast soll ich denn anfangen einzufügen? Ich mein wenn S nur einen Teil des einzufügenden Elements ist, dann kenn ich ja dessen "Vorgeschichte" nicht. Sollte S aber vollständig vorhanden sein, so ist es wirklich der Algo aus dem Skript...... Scary

[wolti]

Naja. Vielleicht ist es auch so gedacht. Wenn du aufruft

Einfügen (p,S, i).

Schlüssel S = {b1, ..., bn}

Du startest beim Routerknoten und gehst auf jedenfall solange runter, bis auf Tiefe i bist. Dort erst probierst du den Schlüssel einzufügen. Da gibts zwei Fälle:

1) Es gibt schon Routerknoten bis in diese Tiefe. Dann läuft das einfügen analog.

2) Es gibt noch keine Routerknoten. Du erzeugst einfach Routerknoten bis in diese Tiefe runter und speicherst dort den Schlüssel.

Im Aglo im Skriptum würdest du ja, wenn du vorher bei einem Routerknoten warst, und nach links/rechts gehen würdest, und dort wäre NULL, den Datenknoten anhängen.
In unserem Fall verstehe ich das so, daß du bis zur Tiefe i Routerknoten erzeugst, obwohl man sie nicht brauchen würde.

Grüße,
Wolti

:EDIT:
Hmm. Siehe Hals post. Das ist kein gültiger Radix-Trie nachher mehr.

[hal]

2) Es gibt noch keine Routerknoten. Du erzeugst einfach Routerknoten bis in diese Tiefe runter und speicherst dort den Schlüssel.

Im Aglo im Skriptum würdest du ja, wenn du vorher bei einem Routerknoten warst, und nach links/rechts gehen würdest, und dort wäre NULL, den Datenknoten anhängen.
In unserem Fall verstehe ich das so, daß du bis zur Tiefe i Routerknoten erzeugst, obwohl man sie nicht brauchen würde.

Ich denke das macht daher Sinn:

1) Es führt noch zu einem gültigen Radix-Trie


Negativ, verletzt die Regel "hat ein Routerknoten nur einen Nachfolger, so ist es immer ein weiterer Routerknoten".

[Freeek]

Also isses der Pseudocode aus dem Skriptum, oder ??

Greetz, Freeek

[hal]

Also isses der Pseudocode aus dem Skriptum, oder ??

wolti und ich haben sich darauf geeinigt. Seltsam isses trotzdem.

[Petzi]

ich denk auch dass das der Pseudocode vom Skriptum ist, der da verlangt wird

naja solang man den erklären kann und weiß worum es geht, dürfte es eh keine Probleme geben...