• Vstavi elemente 1, 2, 3, 4, 5, 6 v RČD.

Najprej vstavimo 1 in 2. Ko vstavimo prvi element 1 je ta koren drevesa in ga pobarvamo črno. Potem vstavimo element 2, ki je rdeče barve in s tem držijo vse lastnosti RČD.

1. korak

Vstavimo element 3. S tem kršimo pravilo, saj ima rdeče vozlišče le črne sinove. Ker stric ne obstaja, očeta(2) pobarvamo črno, starega očeta(1) pa rdeče. Naredimo levo rotacijo.

2. korak in 3. korak

Vstavimo element 4. Kršimo pravilo, ker obstaja stric(3) in je rdeče barve, moramo starega očeta(2) pobarvati rdeče, njegova sinova pa črno. Kršimo tudi pravilo, ki pravi, da mora biti koren črn, zato ga pobarvamo na črno.

4. korak, 5. korak in 6. korak

Vstavimo element 5 in 6. Kršimo pravilo, ker je stric(4) elementa 6 rdeč, obarvamo starega očeta(1) na rdeče, sinova pa črno. Dodamo liste nil. S tem korakom je naloga končana, saj ne kršimo nobenega pravila RČD.

7. korak in 8. korak

• Izbriši element 4 iz drevesa

Prvotno drevo

Odstranili smo element 4.

1. korak

Ker smo odstranili element 4, smo kršili pravilo, ki pravi, da mora biti po vseh poteh od korena do praznih vozlišč enako število črnih vozlišč.

Najprej prebarvamo očeta(1) vozlišča 4 na črno, brata(5) vozlišča 4 na rdeče in njegovega sina(6) na črno.

3. korak

Naredimo še levo rotacijo na očetu. Nato dodamo liste nil. Sedaj so ohranjene vse lastnosti in naloga je končana.

4. korak

• 1. naloga V RČD vstavi elemente 10, 20, 30, 40, 50!

• 2. naloga Iz RČD iz prve naloge odstrani element 40!

• 3. naloga V RČD iz prve naloge vstavi poljubnih 5 elementov!

• 4. naloga Popravi drevo tako, da bodo držale vse lastnosti(prebarvaj in rotiraj)

• 5. naloga Nariši drevo kjer bo prikazana desna rotacija.

Katera od naštetih lastnosti RČD ni pravilna?

Katere izjave so pravilne(več možnih odgovorov)?

Preveri odgovor

Kako moramo popraviti drevo, da bo pravilno in bodo držale vse lastnosti?

Preveri odgovor

Ugotovi resničnost danih izjav.

Brisanje v RČD je podobno brisanju v običajnem iskalnem dvojiškem drevesu, le da moramo paziti na lastnosti RČD:

	Svet	1
1.	Če element v drevesu nima sina ga lahko odstranimo.
2.	Če je bilo izbrisano črno vozlišče so vse lasnoti pravilne.
3.	Če ima element v drevesu samo enega od sinov, ga odstranimo in povečamo ustrezen kazalec njegovega očeta
4.	Če je bilo izbrisano črno vozlišče, ima pot, ki ga je vsebovala eno vozlišče več.
5.	Če ima element oba sina, ga nadosmestimo s prvim največjim iz levega poddrevesa.

V tabeli označi izjave glede na sliko svetov na levi za pravilne ali nepravilne.

Oznake postavljaš s klikanjem:

	prvi klik
	drugi klik
	tretji klik

Preveri rešitev

Označi pravilne trditve.

Preveri odgovor

• //penelope.fmf.uni-lj.si/r2wiki/index.php/Glavna_stran/SeminarskeNaloge/2009_1sem/Rde%C4%8De-%C4%8Drno_drevo/ime2
• //penelope.fmf.uni-lj.si/r2wiki/images/f/fa/Prosojice.pdf
• //en.wikipedia.org/wiki/Red-black_tree#Insertion
• //wiki.fmf.uni-lj.si/wiki/Rde%C4%8De-%C4%8Drno_drevo
• //rc.fmf.uni-lj.si/matija/OpravljeneDiplome/Petra_Tome_Diploma.pdf
• //www.nauk.si/materials/366/out/index.html#state=4