Red Black Tree - "balanciert löschen"



  • hallo

    ich habe - nach langem inet-suche - meine eigene rb-tree implementiet, jedoch ist es mir noch nicht klar, wie ich nach einem delete performant balanciert bleiben kann... hat einer eine idee? den baum jedesmal neu aufzubauen ist doch eher nicht so toll...

    ps: ja, ich weiss, dass es schon zig implementierungen gibt, die man benutzen könnte... und ja! ich habe zu viel zeit! ich bin momentan arbeitslos und versuche mich fit zu halten...



  • Wenn du e so viel zeit kannst du ja auch selber drauf kommen wies geht. 😃 scnr 😃

    Willst du die funktion linear oder rekursiv schreiben ?

    mfg



  • linear! oder besser gesagt iterativ...

    klar könnte ich selber drauf kommen, aber ein denkanstoss tut gut...



  • nein du musst den baum natuerlich nicht immer neu aufbauen!

    das loeschen im r/b baeumen:

    - analog zum einfuegen
    - benutzt den gleichen algo wie fuer das loeschen im binaer baum
    - wichtig ist weiter
      - loescht du einen knoten mit der farbe rot
        ==> kann es zu Verletzunge der r/b eigenschaften kommen
      - knoten schwarzer farbe 
        ==> die Anzahl der scharzen Knoten auf auf dem Pfad von k-aender
      - ist der vaterknoten vom loeschenden knoten rot und der der ihn
        ersetzt (kind oder vorgaenger/nachfolger aus dem linken/rechten Teilbau)
        ==> geeignet links/rechts/doppel-rotationen
            und korrektur der farben
    

    in google findest sicher was ueber r/b baeume
    sonst halt linux code anschaun 🙂

    //EDIT linear ist auf jeden Fall zu bevorzugen!



  • ja mit googlen habe ich bisher alles gefunden, was ich zur bisherigen implementierung gebraucht habe, aber das löschen scheint irgendwie speziell zu sein... auf jedem fall steht auf den sonst sehr ausführlichen links nix oder nicht viel drüber!

    aber danke für deine hilfe! evtl. komme ich damit weiter (muss erst noch nach denken 😉 )



  • ist bei mir auch nicht von einem auf den anderen Tag gegangen,
    wenn du draufkommst das bei meiner Aufzaehlung da was nicht stimmt das kann gut sein, ich weis auch nicht mehr obs so gehoert, glaub aber schon


Log in to reply