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

Diagram der viser et eksempel på et rød-sort træ.

Et rød-sort træ er et træ der opfylder følgende 5 egenskaber^[1]:

1. Alle knuder er enten røde eller sorte.
2. Rod-knuden er sort.
3. Alle blade er sorte.
4. Ingen rød knude har en rød knude som forælder.
5. 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:

1. Find den korrekte plads til elementet i træet vha. en søgning.
2. Indsæt elementet med farven rød.
3. Hvis elementet blev indsat under en sort knude er træet gyldigt, så vi kan stoppe.
4. Hvis elementet blev indsat under en rød knude har vi et brud på regel 4.
   1. Foretag en kombination af omfarvninger og rotationer for at flytte problemet højere op i træet.
   2. Gentag dette indtil problemet løser sig selv, eller vi når rodknuden.
   3. 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:

1. Find elementet i træet, og slet det som i et almindeligt søgetræ.
2. Hvis knuden var rød er der intet problem, så vi kan stoppe.
3. Hvis knuden var sort har vi et brud med regel 5.
   1. 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".
   2. Foretag en kombination af omfarvninger og rotationer for at flytte den dobbelt-sorte knude højere op i træet.
   3. Gentag dette indtil problemet løser sig selv, eller vi når rodknuden.
   4. 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

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3 udgave). MIT Press. s. 308. ISBN 978-0-262-53305-8.

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.