leerer B-Baum Auslastung beim einfügen

Question

Stimm diese Aussage, oder nicht, mit Begründung bitte?

"Beim Einfügen in geordneter Reihenfolge (entweder auf- oder absteigend) in einenanfangs leeren B-Baum ist dessen Auslastung (also der „Füllgrad“ seiner Knoten) besonders hoch!"

Danke im Voraus! Wünsche einen schönen Tag.

Answer 1

Da beim B-Baum immer kleiner gleich oder größer ausgeschlossen werden kann, ist die Zeit zum Suchen und Hinzufügen O(log₂(n+1))

Das heißt abhängig von der Anzahl der Knoten ja, aber nur logarithmisch.

Die Angabe ist nur theoretisch optimal (nämlich wenn links und rechts immer gleich viele Elemente vorhanden sind (ähnlich einem AVL-Baum)). Dann kann mit jedem Suchen immer 50 % des jeweiligen Teilbaums ausgeschlossen werden. Dadurch wir die Suche und auch das Einfügen logarithmisch und abhängig von der Anzahl der bereits vorhandenen Knoten.

[Mit der binären Suche im Array verhält es sich genau so. Da muss das Array allerdings sortiert vorliegen, was beim Baum immer der Fall ist.]

Wenn wir jetzt einen Baum erstellen, zu dem wir nach und nach Elemente in bereits geordneter Reihenfolge einfügen, dann wird emtweder der linke oder der rechte aber nie beide Teilbäume erweitert. Das bedeutet dann bei der Suche, dass nicht mehr ein Teilbaum ausgeschlossen werden kann, weshalb dann die Laufzeit linear wird, also O(n).

Gruß

Felix

Comments

Die Auslastung meint hier denke ich die Tiefe in Relation zu der Anzahl der gespeicherten Elemente. Bei einem ideal ausgeglichenen Baum ist die Tiefe im Vergleich zur Anzahl der Elemente log₂(n).

Du würdest aber eine Tiefe von n haben bei einer Liste von n Elementen. Also nicht wirklich vorteilhaft und nicht ausgeglichen