[FRAGE] - Löschen bei b-bäumen
Results 1 to 31 of 31
  1. #1
    Feierteifl's Avatar
    Title
    Master
    Join Date
    May 2002
    Location
    Wien/ Innsbruck
    Posts
    128
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Löschen bei b-bäumen

    könnte mir jemand erklären, wie das löschen in einem b-baum funzt?

    habe den knoten [7,11] mit den kindern von links nach rechts [6], [8], [12,14,15]....

    wie sieht das bitte aus, wenn ich hier [8] entferne??????

    der baum hat die ordnung 4

  2. #2

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Burgenland
    Posts
    598
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich denk mal dass man den Knoten einfach löschen kann ohne dass sich am restlichen B-Baum irgendetwas ändert.

    also Knoten [7,11] mit Kindern [6] und [12,14,15]

  3. #3
    Feierteifl's Avatar
    Title
    Master
    Join Date
    May 2002
    Location
    Wien/ Innsbruck
    Posts
    128
    Thanks
    2
    Thanked 0 Times in 0 Posts
    ist aber nicht in der Definition von b-bäumen angegeben, dass ein knoten mit l+1 kindern l schlüssel haben muss....

    ... oder hab ich das falsch verstanden.....

  4. #4
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich würd sagen,die 7 geht runter...
    ALL GLORY TO THE HYPNO TOAD...

  5. #5
    DoomedOne
    der 7ener kann nicht runter gehen, denn dann hätt 1 root 3 kinder.

  6. #6

    Title
    Veteran
    Join Date
    Mar 2002
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich würde meinen, dass 11 oben bleibt, aber die 7 zu 6 wandert....

    die anzahl der blätter ist ja um 1 größer als die anzahl der schlüssel...

  7. #7
    Feierteifl's Avatar
    Title
    Master
    Join Date
    May 2002
    Location
    Wien/ Innsbruck
    Posts
    128
    Thanks
    2
    Thanked 0 Times in 0 Posts
    würd ich auch am ehersten schätzen.... hätte nur gerne eine bestätigung....

    läuft es nicht eigentlich so, dass alles im grunde nach dem löschen wieder verschmolzen wird und dann neu aufgespalten....

    damit würde man auch auf das ergebnis kommen....

  8. #8
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    der 7ener kann nicht runter gehen, denn dann hätt 1 root 3 kinder.
    wieso?
    7 kleiner als 11=>
    7runter zur 6 =>
    [11]
    / \
    [6 7] [12 14 15]
    ALL GLORY TO THE HYPNO TOAD...

  9. #9

    Title
    Elite
    Join Date
    Dec 2001
    Posts
    340
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Shade

    wieso?
    7 kleiner als 11=>
    7runter zur 6 =>
    Code:
                  [11]
                  /  \
              [6 7]  [12 14 15]
    man sieht besser wie's gemeint ist..
    obwohl, anders wars natürlich auch klar
    Last edited by martin; 22-05-2002 at 02:23.
    I invented ctrl-alt-del but Bill [Gates] made it famous
    Dave Bradly, IBM PC designer

  10. #10
    nebo's Avatar
    Title
    Master
    Join Date
    Sep 2004
    Posts
    142
    Thanks
    0
    Thanked 1 Time in 1 Post
    Im Repetitorium wurde jetzt ja das Löschen von Knoten aus B-Bäumen erklärt. Ich konnte zum Repetitorium nicht kommen. Hat das jemand verstanden und kann es erklären? So wie es im Skriptum steht, kann das nicht funktionieren, oder?

    In diesem Tool schaut es auch recht kompliziert aus:
    http://www.engin.umd.umich.edu/CIS/c...s350/treetool/

  11. #11

    Title
    Veteran
    Join Date
    May 2005
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Cool

    gestern im repetitorium wurde das löschen aus b-bäumen so erklärt:
    mit deinem beispiel: du gehst von der oberen ebene eine ebene runter und verschmilzst alles - hier so: 6, 7, 11, 12, 14, 15 - dann m/2 abgerundet checkst du dir die 11. dann baust du dir daraus deinen baum auf. somit kommt das ergebnis von den leuten oben. also 11 vater; 6,7 linkes kind; 12,14,15 rechtes kind.
    es gibt eine voraussetzung für die richtigkeit eines b-baumes und das ist dass alle Kinder Blätter haben und diese Blätter auf derselben ebene sein müssen. stell dir vor unter 6, 8, und 12 14 15 gibt es noch leere Blätter -> sind alle aufderselben ebene. wenn du 8 löschst ist das blatt nur mehr auf der ebene mit 6, 12, 14 und 15 - das ist kein korrekter baum mehr!

  12. #12
    woddy's Avatar
    Title
    Master
    Join Date
    Oct 2004
    Location
    Tirol / Wien
    Posts
    145
    Thanks
    4
    Thanked 1 Time in 1 Post
    is der oben gezeichnete Baum überhaupt ein b-baum?

    i mein mit [12,14,15] ist die bedienung ja nicht mehr erfüllt und er gehört aufgespalten?

    erst dann kann man sich mal ums löschen kümmern ;-)

    mfg
    Yoda: Duuuunkel die andere Seite ist!
    ....
    Halts Maul und iss deinen Toast, wie alle andan a!
    App Store - Multitouch Full Screen Web Browser - fgBrowser

  13. #13

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    471
    Thanks
    3
    Thanked 14 Times in 10 Posts
    der baum hat die ordnung 4
    passt doch oder?

  14. #14

    Title
    Principal
    Join Date
    Nov 2003
    Location
    wien
    Posts
    84
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Raiden
    passt doch oder?
    Würd ich auch sagen!!!

  15. #15

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    Frage zu einem anderen Baum:

    Code:
    	  [8,10]
    	  /   |  \
    	[6] [9]  [11,12]
    ich will jetzt die 10 löschen, dann kann ich ja 2 gültige B-Bäume erstellen

    Code:
     	  [8,11]
     	  /   |  \
     	[6] [9]  [12]
    oder

    Code:
     	   [8]
     	  /	 \
     	[6]   [9,11,12]
    Welcher Baum wäre hier richtig? Der Baum ist übrigens 4ter Ordnung

  16. #16

    Title
    Veteran
    Join Date
    May 2005
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Smile Tube is watchin u

    Nein eigentlich nicht! ich denke, wenn wir nach dieser verschmelzungstheorie gehen, dann müsste es so verschmolzen werden : 6 8 9 11 12 dann holst du dir m/2, also den 9er hebst hoch und machst ihn zum vater. dann sind 6 und 8 das linke Kind und 11 und 12 das rechte kind

    9
    6 8 11 12

    voila!

  17. #17
    comar's Avatar
    Title
    Elite
    Join Date
    Oct 2004
    Location
    Wien/CZ
    Posts
    313
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Code:
     	   [8]
     	  /	 \
     	[6]   [9,11,12]

    ich würde dagen derhier ist richtig. Ob du jetzt die 9 zu dem rechten oder zu dem linken Nachbaren dazugibst ist Definitionssache.
    Aber du musst schauen, dass wenn zu groß wird, dass du dann ein Schlüssel in die Wurzel hinaufschiebst (und gegebenfalls dann die wider bearbeitest...)
    May the source be with you.

  18. #18

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    ich verschmelze also immer den ganzen Baum? Ist ja ein brutaler Aufwand dann diesen Baum immer wieder neu aufzubauen.

    Im Buch steht dazu ja nur: (Seite 93)

    ... entfernt ihn(Schlüssel) aus Knoten p. Enthält p nun zu wenige Kinder...

    aber in diesem Fall hätte p dann ja zuviele Kinder und dazu steht gar nichts im Skriptum

  19. #19
    comar's Avatar
    Title
    Elite
    Join Date
    Oct 2004
    Location
    Wien/CZ
    Posts
    313
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by spooky
    ich verschmelze also immer den ganzen Baum? Ist ja ein brutaler Aufwand dann diesen Baum immer wieder neu aufzubauen.

    Im Buch steht dazu ja nur: (Seite 93)

    ... entfernt ihn(Schlüssel) aus Knoten p. Enthält p nun zu wenige Kinder...

    aber in diesem Fall hätte p dann ja zuviele Kinder und dazu steht gar nichts im Skriptum
    wenn ein Knoten zu viele Kinder hat, dann tust du dasselbe wie beim Einfügen.
    May the source be with you.

  20. #20

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    klingt eigentlich logisch

    aber das wäre ja eigentlich ein Zustand der durch einfügen nicht möglich wäre, und das Ergebnis mit der 9 oben kann daher nicht zustande kommen

    EDIT: Scheint aber die richtige Lösung zu sein...

  21. #21

    Title
    Master
    Join Date
    Mar 2004
    Location
    Wien
    Posts
    165
    Thanks
    0
    Thanked 0 Times in 0 Posts
    aber ist es nicht auch so, dass die anzahl der schlüssel bei knoten der selben gleichmäßig aufgeteilt werden soll und wenn dies nicht möglich ist, sich die anzahl der schlüssel um max 1 unterscheiden soll?
    der 4er ist das sehr gut des kleinen mannes

  22. #22

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    Quote Originally Posted by minority
    aber ist es nicht auch so, dass die anzahl der schlüssel bei knoten der selben gleichmäßig aufgeteilt werden soll und wenn dies nicht möglich ist, sich die anzahl der schlüssel um max 1 unterscheiden soll?
    echt? wo steht das? Das würde nämlich einiges erklären

  23. #23
    Spree's Avatar
    Title
    Elite
    Join Date
    Oct 2002
    Posts
    295
    Thanks
    0
    Thanked 0 Times in 0 Posts
    - Jeder Knoten mit l + 1 Kindern hat l Schlüssel

    So steht es im Skriptum.. dann würde es doch gar nicht gehen, dass ein Knoten einen Schlüssel hat aber 3 Kinder.
    Da Big Pimp

  24. #24

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    ja das stimmt schon, aber das bezieht sich ja nicht auf die schlüssel in den Kinderknoten

  25. #25
    Spree's Avatar
    Title
    Elite
    Join Date
    Oct 2002
    Posts
    295
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hmm.. stimmt! Jetzt geht mir auch ein Lichterl auf
    Wenn ich jetzt alles gecheckt habe, darf ein Knoten eines Baumes der Ordnung m nur maximal m - 1 Schlüssel haben
    Da Big Pimp

  26. #26

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    genau .........

  27. #27
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    4,001
    Thanks
    347
    Thanked 504 Times in 266 Posts
    auf mtb gibt es paar sachen zu b-bäumen
    http://tigerente.htu.tuwien.ac.at/~m....php?parent=21
    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  28. #28
    Spree's Avatar
    Title
    Elite
    Join Date
    Oct 2002
    Posts
    295
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Das schau ich mir jetzt lieber nicht an.. Dann merk ich nämlich erst wirklich, was ich alles nicht kann und werd noch depressiv bis morgen
    Da Big Pimp

  29. #29

    Title
    Elite
    Join Date
    Oct 2004
    Posts
    492
    Thanks
    4
    Thanked 3 Times in 2 Posts
    naja ich hab das jetzt kurz durchgesehen, aber wissen tu ich immer noch nicht, ob die Anzahl der Schlüssel (auf einer Ebene) irgendwie ausgeglichen sein müssen oder nicht

  30. #30
    Spree's Avatar
    Title
    Elite
    Join Date
    Oct 2002
    Posts
    295
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Nachdem dazu nichts im Skriptum steht, glaub ich nicht dass sie irgendwie ausgeglichen sein müssen. Es dürfen halt die "Gesetze" des B-Baumes nicht gebrochen werden.

    Das einzige ist halt, aber das wurde eh schon geschrieben, dass die Blätter die gleiche Tiefe haben müssen...
    Da Big Pimp

  31. #31

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Das Thema wird im Skriptum wirklich nur sehr rudimentaer angesprochen. Wie es
    im Repetitorium gezeigt wurde, weisz ich nicht, aber wenn es so erklaert wurde,
    wie es daTube zusammengefasst hat, kommt es mir nicht richtig vor.

    Ich versuche mal zusammenzufassem, wie der Rest der Welt Elemente aus einem
    B-Baum loescht (man kann sich ueberzeugen, dass es wirklich von den meisten
    so gemacht wird, wenn man google nach "b-tree" befragt).

    Zuerst einmal: nur weil in einem Knoten keine Elemente mehr sind, ist dieser
    Knoten nicht auf der Stelle weg. Das kann sowieso nur in B-Baeumen vorkommen,
    deren Ordnung kleiner als fuenf ist (ist die Ordnung >= 5, muessen in jedem
    Knoten mindestens 2 Elemente sein). Ein Knoten ohne Elemente ist also nicht
    sofort weg, sondern hat einfach ein Element zu wenig, ein sogenannter Unterlauf.

    Es macht einen Unterschied, ob wir aus einem inneren Knoten, oder aus einem
    Blatt loeschen. Ich beschreibe den Vorgang zuerst fuer Blaetter.

    Ich benutze das oben genannte Beispiel:

    Code:
        [7, 11]
       /   |   \
    [6]   [8]   [12, 14, 15]
    Dieser Baum hat die Ordnung 4, das bedautet: jeder Knoten hat

    - mindestens 1 und maximal 3 Elemente (Ordnung / 2 - 1, bzw. Ordnung - 1)(0)
    - mindestens 2 und maximal 4 Kinder (Ordnung / 2, bzw. Ordnung)

    Wir loeschen das Element 8:

    Code:
        [7, 11]
       /   |   \
    [6]   [ ]   [12, 14, 15]
    Wir haben jetzt in einem Knoten ein Element zu wenig. Um wieder auf die
    Mindestanzahl zu kommen verschmelzen wir den Knoten mit einem seiner Nachbarn
    ([6] oder [12, 14, 15]) und demjenigen Element aus dem Elternknoten, das
    zwischen den beiden Knoten ist, die wir verschmelzen wollen. Dieser neue Knoten
    ersetzt unseren unterbesetzen Knoten. Das Elternelement wird dabei aus dem
    Elternknoten (sorry fuer die aehnlichen Bezeichnungen) entfernt, ebenso wie der
    verweis auf sein zweites Kind, denn diese Elemente sind jetzt sowieso alle in
    dem neuen Knoten.

    Ich verschmelzte in diesem Beispiel den unterbesetzten Knoten, mit seinem linken
    Nachbarn [6] und dem Elternelement, das zwischen diesen beiden Knoten liegt:

    Code:
           [11]
          /    \
    [6, 7]      [12, 14, 15]
    Jetzt haben wir wieder einen gueltigen B-Baum. Wenn wir den leeren Knoten, mit
    seinem rechten Nachbarn verschmolzen haetten, haetten wir einen Knoten bekommen,
    der zuviele Elemente enthaelt, und wir haetten diesen Knoten wieder aufspalten
    muessen. Das man nach dem verschmelzen wieder aufspalten muss, kann aber nur
    passieren, wenn der andere Knoten mindestens ein Element _mehr_ hat, als er
    mindestens haben muss. Denn wenn er nur die minimale Anzahl an Elementen haette
    (Ordnung / 2 - 1), dann haette der neue Knoten nach dem Verschmelzen genau
    (Ordnung - 2) Elemente (1 vom Elternknoten, (Ordnung / 2 - 2) vom Knoten in dem
    der Unterlauf passiert ist und (Ordnung / 2 - 1) vom Nachbarknoten), und die
    passen alle in einen Knoten.

    Wenn aber jetzt der Nachbarknoten, mit dem wir verschmelzen, mindestens ein
    Element mehr hat, als er unbedingt braucht, koennen wir das Merge sparen, und
    uns einfach ein Element von diesem Nachbarn ausleihen, denn das ist -- vor allem
    bei hoeherer Ordnung -- nich so aufwendig, wie zwei Knoten zu verschmelzen
    (vor allem, wenn man sie danach vielleicht sogar wieder teilen muss).

    Das "Vom-Nachbarn-Ausleihen" funktioniert folgendermaszen: wenn wir uns etwas
    vom linken Nachbarn ausleihen, holen wir uns das Element aus dem Elternknoten,
    das zwischen den beiden Knoten ist, in unseren unterbestzten Knoten, und das
    rechteste Element aus unserem linken Nachbarn, kommt in den Elternknoten. Leihen
    wir uns ein Element vom rechten Nachbarn, kommt wieder das entsprechende
    Elternelement in den Knoten mit dem Unterlauf, und das linkeste Kind aus dem
    Nachbarn, kommt in den Elternknoten.

    Anstatt also den leeren Knoten, mit 7 und [6] zu verschmelzen, haetten wir uns
    auch ein Element aus dem rechten Nachbarn ausleihen koennen:

    Code:
        [7, 12]
       /   |   \
    [6]   [11]   [14, 15]
    Nun zu dem Fall, dass wir ein Element aus einem inneren Knoten loeschen muessen.
    Wir gehen hier aehnlich vor, wie beim Loeschen eines Elements aus einem binaeren
    Baum: wir holen uns einen Ersatz von weiter unten. Wir bestimmen also entweder
    den Successor (kleinstes Element aus dem rechten Unterbaum) oder den
    Predecessor (groesztes Element aus dem linken Unterbaum), ueberschreiben das
    zu loeschende Element mit dem Erszatz-Element, und entfernen dieses aus dem
    Unterbaum. Successor, bzw. Predecessor sind _immer_ in einem Blatt, und wie
    man ein Element aus einem Blatt loescht, wissen wir schon.

    Wenn wir also aus unserem urspruenglichen Baum die 11 loeschen wollen, koennen
    wir sie entweder durch die 8 ersetzen:

    Code:
        [7, 8]
       /   |   \
    [6]   [ ]   [12, 14, 15]
    Unterlauf beheben:

    Code:
           [8]                               [7, 12]
          /   \                 ODER        /   |   \
    [6, 7]     [12, 14, 15]              [6]   [8]   [14, 15]
    oder wir ueberschreiben ihn mit der 12:

    Code:
        [7, 12]
       /   |   \
    [6]   [8]   [14, 15]
    -----
    (0) Wenn die Ordnung des B-Baums ungerade ist, dann gilt: jeder Knoten(1) hat
    mindestens floor(Ordnung / 2) und hoechstens (Ordnung - 1) Elemente(2), bzw.
    mindestens (floor(Orndung / 2) + 1) und hoechstens (Ordnung) Kinder
    (1) Das gilt nicht fuer die Wurzel
    (2) floor(x) heiszt x abgerundet

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •