Rdeče-črno drevo

Iz MaFiRaWiki

V podčlanku /METARAM najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Rdeče-črno drevo je delno poravnano iskalno dvojiško drevo z nadzorovano rastjo. Vsako vozlišče je bodisi rdeče bodisi črne barve. Poleg kazalcev na sinova, vozlišča vsebujejo še kazalec na očeta in informacijo o barvi. Za višino rdeče - črnega drevsa velja: h <= 2 log (n + 1). Torej višina rdeče - črnega drevesa ni več kot dvakrat večja od višine polnega drevesa.

Vsebina

Lastnosti

Rdeče - črno drevo zadošča naslednjim lastnostim:

  • Če je vozlišče rdeče, potem sta oba sinova črna.
  • Za poljubno vozlišče velja, da poti do vsakega lista vsebujejo enako število črnih vozlišč.
  • Koren drevesa je črn.

Operacije nad rdeče - črnim drevesom

Za vstavljanje podatkov v rdeče - črno drevo velja: Obstaja algoritem, ki vstavi podatek v rdeče - črno drevo in ohrani lastnosti rdeče - črnega drevesa; časovna zahtevnost algoritma je O (log n).

Za izločanje podatkov iz rdeče - črnega drevesa velja: Obstaja algoritem, ki odstrani podatek iz rdeče - črnega drevesa in ohrani lastnosti rdeče - črnega drevesa; časovna zahtevnost algoritma je O (log n).

Implementacija rdeče - črnega drevesa

Implementacija:

Osnovne operacije:

 Clear[Pripravi, DDrevo, Sestavi, Koren, LeviSin, DesniSin, JePrazno]
 Pripravi[] := DDrevo[]
 Sestavi[p_, ls_, ds_] := DDrevo[ls, p, ds]
 Koren[DDrevo[_, k_, _]] := k
 LeviSin[DDrevo[l_, _, _]] := l
 DesniSin[DDrevo[_, _, d_]] := d
 JePrazno[d_DDrevo] := Length[d] == 0

Pregled drevesa:

 Clear[Preglej, Obisci] 
 (* Vmesni ali LKD pregled drevesa. *)
 Preglej[d_] := If[! JePrazno[d], Preglej[LeviSin[d]]; Obisci[Koren[d]]; \
 Preglej[DesniSin[d]]] 
 Obisci[d_] := Print[d]

Risanje drevesa:

 Clear[RisiDrevo, Risi]
 RisiDrevo[d_] := If[! JePrazno[d], Show[Graphics[Risi[d, 0, {0, 0}]]]]
 Risi[d_, n_, {x_, y_}] :=   If [
 JePrazno[d], {}, Join[{  If[Mod[n, 2] == 0, RGBColor[0, 0, 0],
 RGBColor[1, 0, 0]], Disk[{x, y}, 0.1], Text[Koren[d], {x + 0.15, y}]},
 If[JePrazno[LeviSin[d]], {}, {Line[{{x, y}, {x - 2^(-n), y - 1}}]}], 
 If[JePrazno[DesniSin[d]], {}, {Line[{{x,y}, {x + 2^(-n), y - 1}}]}],  
 Risi[LeviSin[d], n + 1, {x - 2^(-n),y - 1}], Risi[DesniSin[d], n + 1, {x + 2^(-n), y - 1}]]]
 (* Poskrbimo, da vedno dobimo izrisano drevo. *)
 Format[d_DDrevo] := RisiDrevo[d]

Zgledi:

Zgled1:

Input:

Clear[drevo, drevo2]
drevo = Pripravi[];
JePrazno[drevo]

Output:

True

Input:

drevo2 = Sestavi[1, Sestavi[2, drevo, drevo], drevo]

Output:

slika:Image_2.jpg

Input:

LeviSin[drevo2]

Output:

2

Input:

Koren[drevo2]

Output:

1



Zgled2:

Input:

Clear[n]
n = Sestavi[1,Sestavi[2,Sestavi[4, Pripravi[], Pripravi[]],
Sestavi[5, Sestavi[7, Pripravi[], Pripravi[]], Pripravi[]]],
Sestavi[3, Sestavi[6, Pripravi[], Pripravi[]], Pripravi[]]];
RisiDrevo[n]

Output:

slika:Image_3.jpg

Input:

Preglej[drevo3]

Output:

4 2 7 5 1 6 3

Uporaba in prednosti

Rdeče-črna drevesa omogočajo zagotovilo za najtežje primere vstavljanja, brisanja in iskanja, kar se tiče časa. Ne le, da jih to dela uporabne in kakovostne v aplikacijah v katerih je časovna zahtevnost pomembna, temveč so tudi pomemben del v ostalih podatkovnih strukturah.

AVL drevesa so bolj natančno uravnotežena kot rdeče-črna drevesa, kar pomeni da v najtežjih primerih potrebujejo več rotacij pri vstavljanju ali brisanju podatkov.


Glej tudi

Osebna orodja