| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
gast00
Gast
|
 Verfasst am: 18. Mai 2005 22:35 Titel: Bruder-Bäume |
 |
|
hi, ich bin bei dem thema b-bäume (bruder-bäume). kann mir bitte jemand kurz erklären, was mit der aussage "JEDER INNERE KNOTEN MIT AUSNAHME DER WURZEL hat wenigstens  Söhne". m steht für die ordnung wie z.b b-baum der ordnung 3. trotzdem ist mir nicht ganz klar, obwohl ich überall im internet nachgeguckt habe, wie ich einen b-baum konstruiere. Ich weiß dass die tiefe aller knoten gleich sein muss, aber wieviele äste in an einen knoten dranhängen muss, das verstehe ich nicht ganz. |
|
| Nach oben |
|
 |
|
|
webster
Gast
|
| Verfasst am: 19. Mai 2005 01:50 Titel: |
|
|
| Wie definiert ihr Söhne? Unmittelbare Nachfolger, oder auch indirekte Nachfolger? Wie auch immer, was genau verstehst du daran nicht? |
|
| Nach oben |
|
|
Henning
Gast
|
| Verfasst am: 14. Jun 2005 09:10 Titel: Re: Bruder-Bäume |
|
|
| gast00 hat Folgendes geschrieben: | | hi, ich bin bei dem thema b-bäume (bruder-bäume). kann mir bitte jemand kurz erklären, was mit der aussage "JEDER INNERE KNOTEN MIT AUSNAHME DER WURZEL hat wenigstens [latex]m/2[\latex] Söhne". |
Im B-Baum muss je nach Lösch- oder Einfügeoperation die Ordnung m beibehalten werden. Wenn du löschst und edamit einen Unterlauf verursachst - sprich die Ordnung in einem Knoten verletzt wird, hast du zwei Möglichkeiten:
1.) Knoten mit Nachbarknoten verschmelzen
2.) Falls der Nachbarknoten mehr Elemente als die Ordnung es vorschreibt beinhaltet, kannst du diese aufteilen.
[latex]\frac{m}{2}[\latex] soll hier die Bedingung beschreiben, dass, falls verschmolzen wird, nicht gleichzeitig die Ordnung m verletzt wird.
BSP: m = 2
linker Knoten 2, rechter Knoten 2
du löschst im rechten Knoten, erzeugst damit einen Unterlauf und musst die Ordnung m wieder herstellen. Da beide vorher nur die Mindestanzahl an Knoten beinhaltet haben kannst du also nciht ausgleichen.
Das Verschmelzen passiert nun über den nächst höher stehenden knoten. alle übrigen elemente des unterlaufenden knoten (hier 1) müssen und m+1 nach rechts gerückt werden, damit die m (=2) elemente des knotens und das element, dass auf den rechten knoten zeigt (die suche muss weiterhin richtig delegiert werden deswegen die +1) in den unterlaufenden knoten eingefügt werden kann.
nun muss nur noch im nächst höheren knoten der verweis auf den vorher unterlaufenden knoten auf den eintrag übertragen werden, der vorher auf den linken nachbarn gezeigt hat.
Im extremfall, können so unterläufe bis hin zur wurzel erzeugt werdens |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login