Rød-sort træ
Et rød-sort træ er en form for selv-balancerende binært søgetræ. Formålet med at have træet selv-balancerende er, at garantere, at højden på træet er O(lg n).
Definition
Et rød-sort træ er et træ der opfylder følgende 5 egenskaber[1]:
- Alle knuder er enten røde eller sorte.
- Rod-knuden er sort.
- Alle blade er sorte.
- Ingen rød knude har en rød knude som forælder.
- Enhver sti fra rod-knuden til et blad indeholder det samme antal sorte knuder.
De vigtigste punkter i denne definition er punkterne 4 og 5, der er dem der sørger for, at træet må være balanceret.
Operationer
Operation | Køretid |
---|---|
Søgning | O(lg n) |
Indsættelse | O(lg n) |
Sletning | O(lg n) |
Søgning
Søgning foregår som det almindeligvis foregår i binære søgetræer.
Indsættelse
Idéen bag indsættelse i et rød-sort træ er som følger:
- Find den korrekte plads til elementet i træet vha. en søgning.
- Indsæt elementet med farven rød.
- Hvis elementet blev indsat under en sort knude er træet gyldigt, så vi kan stoppe.
- Hvis elementet blev indsat under en rød knude har vi et brud på regel 4.
- Foretag en kombination af omfarvninger og rotationer for at flytte problemet højere op i træet.
- Gentag dette indtil problemet løser sig selv, eller vi når rodknuden.
- Hvis problemet er flyttet op i rodknuden kan vi blot farve knuden sort, og så er problemet løst.
Sletning
Idéen bag sletning i et rød-sort træ er som følger:
- Find elementet i træet, og slet det som i et almindeligt søgetræ.
- Hvis knuden var rød er der intet problem, så vi kan stoppe.
- Hvis knuden var sort har vi et brud med regel 5.
- Farv den slettede knudes forældre en ekstra gang sort. Dvs., hvis den var rød, farv den sort, hvis den var sort farv den "dobbelt-sort".
- Foretag en kombination af omfarvninger og rotationer for at flytte den dobbelt-sorte knude højere op i træet.
- Gentag dette indtil problemet løser sig selv, eller vi når rodknuden.
- Hvis problemet er flyttet op i rodknuden kan vi blot farve knuden sort, og så er problemet løst.
Grunden til, den slettede knudes forældre farves en ekstra gang sort er, at brud på regel 5 er et globalt problem, dvs. et der omhandler hele træet. Ved at omdanne dette globale problem til et problem med regel 1 (dvs., en knude med den ugyldige farve "dobbelt-sort"), har vi gjort problemet lokalt, og kan derfor nemmere gribe det an.
Kilder
Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |
Medier brugt på denne side
Forfatter/Opretter: Cburnett, Licens: CC BY-SA 3.0
Example red-black tree