Rød-sort træ

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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[redigér | redigér wikikode]

Diagram der viser et eksempel på et rød-sort træ.
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 vigtigeste punkter i denne definition er punkterne 4 og 5, der er dem der sørger for, at træet må være balanceret.

Operationer[redigér | redigér wikikode]

Operation Køretid
Søgning O(lg n)
Indsættelse O(lg n)
Sletning O(lg n)

Søgning[redigér | redigér wikikode]

Søgning foregår som det almindeligvis foregår i binære søgetræer.

Indsættelse[redigér | redigér wikikode]

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[redigér | redigér wikikode]

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ældrer 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ældrer 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[redigér | redigér wikikode]

  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3 udg.). MIT Press. pp. 308. ISBN 978-0-262-53305-8. 
It Stub
Denne it-artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.