binary search tree: find: Invariante

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

binary search tree: find: Invariante

Beitrag von sbechtel »

Hallo,

ich habe ein Frage zur Invariante der Methode find der abstrakten Datenstruktur binary search tree.

Wenn der Key nicht im Baum ist, zeigt in der letzten Iteration p auf null. Das ist nach der 1. Invariante auch OK (es steht dabei, dass p auf einen Knoten mit Höhenlevel i zeigt, oder auf void), aber die 2. Invariante wird meiner Auffassung nach verletzt. Wenn p nicht auf einen Knoten zeigt, dann kann folglich K auch nicht in der Range dieses Knotens sein und Invariante zwei wird verletzt. Meiner Meinung nach macht eine Ausnahmereglung in Invariante eins die zweite Invariante nicht wahrer.

Wenn ich mich jetzt nicht vertue, könnte man das Problem auch ziemlich einfach abfangen, indem man die Abbruchbedingung formuliert als:

p.key = K oder ((K <= p.key und p.left = void) oder (K >= p.key und p.right = void))

Also, ist mein Einwand berechtigt, oder übersehe ich etwas?

VG Sebastian

Zurück zu „Archiv“