Invariante bei BTrees, Löschen und Einfügen

Moderator: AI 2

TobiTobske
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 15. Jan 2014 20:50

Invariante bei BTrees, Löschen und Einfügen

Beitrag von TobiTobske »

Hallo, ich habe mal eine grundlegende Frage zu BTrees, genauer gesagt zum Einfügen und Löschen von Werten bei BTrees.

Inwiefern ist für uns AI2ler das Einhalten der Invariante (also wann der Pointer überhaupt auf einen Knoten/ein Blatt/eine Wurzel zeigen kann) relevant?
Je nachdem, ob man diese Regel berücksichtigt oder nicht, ergeben sich logischerweise mehrere Möglichkeiten, Werte eines Baumes zu löschen oder hinzufügen.
Ich war eben gerade noch in einer Sprechstunde, und dort wurde mir gesagt, dass es für uns AI2ler weniger wichtig ist, die Invariante konsequent anzuwenden, sondern dass es darauf ankommt, dass der Baum nach den Operationen immer noch die Bedingungen erfüllt (also maximal 2m-1, mindestens m-1 Keys in den Knoten und alle Blätter auf einer Ebene).

Kann das hier von jemandem bestätigt werden? Ich weiß jetzt nämlich nicht, ob ich in der Klausur die Invariante berücksichtigen soll oder nicht. Wäre super, wenn sich jemand Offizielles dazu äußern könnte, denn dann weiß man wo man dran ist. :wink:

m_flaig
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Invariante bei BTrees, Löschen und Einfügen

Beitrag von m_flaig »

Hallo,

ja, das kann ich bestätigen. Das Einhalten der Invariante ist irrelevant. Niemand bekommt deswegen Punktabzug.

Viele Grüße,
Maximilian Flaig

msssm
Neuling
Neuling
Beiträge: 3
Registriert: 28. Aug 2014 17:20

Re: Invariante bei BTrees, Löschen und Einfügen

Beitrag von msssm »

Wird in der Klausur bei den Erläuterungen erwartet, dass man mit Begriffen wie Rekursionsanker, Invariante etc. umgehen kann oder reicht eine schlüssige Erklärung der Sortieralgorithmen?

Gruß
msssm

Antworten

Zurück zu „AI 2“