4.1: BST remove Invariante 2.

Thomi
Neuling
Neuling
Beiträge: 7
Registriert: 21. Apr 2015 14:48

4.1: BST remove Invariante 2.

Beitrag von Thomi »

Hallo,
die Invariante aus dem Wiki sagt ja, dass für i >= 0 Iterationen der zu löschende Key k in der Reichweite des Pointers p liegt und p.key != k gilt. Habe ich das so richtig verstanden?
Wenn ja wäre diese Invariante doch bereits in Iteration 0 verletzt wenn der zu löschende Key k = root.key da p ja nach null Iterationen=root ist? Oder liege ich da falsch?

Meine Implementierung, besitzt einen zweiten Pointer p', welcher der direkte Vorgänger von p ist, sodass ich gleich prüfen kann, ob p.key == k.
Dies würde aber die genannte Invariante auch dauerhaft verletzen, sollte aber funktionieren, da ich ja dann noch Zugriff auf p' habe und die benötigte Anpassung vornehmen kann. Ist meine Art der Implementierung auch in Ordnung, oder muss ich eine andere Lösung finden? Habe dafür zwar auch schon eine Idee, aber die finde ich Vergleichsweise vom Codeaufbau nicht so schön.

Viele Grüße,
Thomas

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: 4.1: BST remove Invariante 2.

Beitrag von R_Egert »

Hallo,

Die Invariante gilt ja nach jedem gültigen Schritt im Algorithmus. Direkt in Iterationsschritt 0 (Induction Base) wird ja die Wurzel passend entfernt falls sie direkt dem zu löschenden Knoten entspricht und der Algorithmus terminiert. Andernfalls wird p auf root gesetzt und der Key von root != gesuchter Key. Somit ist in beiden Fällen die Invariante erfüllt.

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Thomi
Neuling
Neuling
Beiträge: 7
Registriert: 21. Apr 2015 14:48

Re: 4.1: BST remove Invariante 2.

Beitrag von Thomi »

Ah okay danke :)

Ich hatte wirklich nicht bedacht, dass die Invariante erst nach einem korrekten Iterationsdurchlauf wieder stimmen muss.

Thomas

Antworten

Zurück zu „Archiv“