Kann es einen leeren B-tree geben?

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Kann es einen leeren B-tree geben?

Beitrag von robertH »

Hallo zusammen,

ich habe mich gefragt, ob es einen leeren B-tree geben kann? Es heißt in der Implementationsinvariante ja, dass M>1 und n>=1 in der Wurzel gelten muss. Demnach würde ich sagen, dass es keinen leeren B-tree geben kann. Da nun aber in B-tree: insert http://wiki.algo.informatik.tu-darmstad ... ee:_insert darauf getestet wird, ob dieser leer ist und in B-tree: find nicht oder vielleicht nicht getestet wird (implementation: obvious) http://wiki.algo.informatik.tu-darmstad ... tree:_find bin ich mir nicht sicher.
Meines Erachtens dürfte man entweder nur Konstruktoren zulassen, die mindestens einen Key verlangen und dann kann man sich Test auf leere B-trees sparen in den Methoden
oder man muss in der Implementationsinvariante http://wiki.algo.informatik.tu-darmstad ... php/B-tree den Zusatz hinzufügen, "if the tree is non-empty".

Zurück zu „Archiv“