Raudonai juodas medis

Raudonai-juodas medis – besibalansuojantis (dvejetainis paieškos medis), informatikoje naudojama duomenų struktūra, išrasta 1972 . Tokio dvejetainio paieškos medžio realizacija sudėtingesnė, bet jis pasižymi geru blogiausių - geriausių vykdymo trukmės laikų santykiu ir gali būti labai naudingas praktikoje: galima realizuoti O (log n) sudėtingumo elemento įterpimą bei pašalinimą.

Terminologija

Efektingumo įrodymui įvedama tuščio, neturinčio duomenų, lapo sąvoka. Viršūnė neturinti vaikų (lapas) turi pseudo lapus, t. y. tuščias viršūnes.

Savybės

Raudonai-juodas medis turi atitikti šiuos 5 kriterijus:

1. Kiekvienas elementas yra arba raudonas, arba juodas.
2. Šaknis yra juoda
3. Visi tušti (NIL) lapai yra juodi
4. Raudonos viršūnės vaikai yra juodi
5. Kelyje nuo šaknies iki kiekvieno lapo yra vienodas skaičius juodų elementų.

An example of a red-black tree

Jeigu dvejetainės paieškos medis yra sukonstruotas atsižvelgiant į šiuos 5 kriterijus, tai ilgiausias kelias nuo šaknies iki lapų skirsis nuo trumpiausio ne daugiau kaip du kartus. Dėl šios savybės paieškos, elemento įterpimo bei pašalinimo operacijų sudėtingumas yra O (log n).

Trumpiausias atstumas bus tada, kai kelią sudarys vien tik juodos viršūnės. O ilgiausias atstumas bus tada, kai kas antra viršūnė bus raudona.

Gana dažnas nesusipratimas būna toks, kad Raudonai-juodo medžio lapais yra laikomi NIL (pseudo lapai). Juos dažnai piešiniuose praleidžia ir gali susidaryti įspūdis, kad 4 taisyklė yra pažeidžiama.

Operacijos

Skaitymo operacijos atliekamos lygiai taip pat, kaip ir (dvejetainiame paieškos medyje), tačiau atlikus įterpimo ar pašalinimo operaciją medžio savybės gali būti pažeistos.

Įterpimas

Visų pirma įkeliame elementą, tarsi tai būtų dvejetainis paieškos medis ir nudažom jį raudonai. Trečia Raudonai-juodo medžio taisyklė nėra pažeidžiama, bet gali būti pažeista ketvirta ir penkta taisyklės. (Pastaba: įsivesime naują sąvoka – dėdė, viršūnės protėvio vaikas, kuris nėra viršūnės tėvas)

Pastabos:

• 4, 5 žingsniuose pateikti atvejai galioja tada, kai koreguojamos viršūnės tėvas yra kairys protėvio vaikas. Jeigu jis bus dešinys, tai kairę reikės keisti į dešinę ir atvirkščiai:

Veiksmai:

1. Koreguojama viršūnė yra medžio šaknis, šią viršūnę nuspalvinam juodai, baigiam darbą.
2. Koreguojamos viršūnės tėvas yra juodas, baigiam darbą.
3. Koreguojamos viršūnės tėvas ir dėdė yra raudoni, mes juos nuspalviname juodai, protėvį raudonai. Koreguojama viršūnė dabar bus protėvis (koregavimą pradedam nuo pradžios).
4. Koreguojamos viršūnės tėvas yra raudonas, bet dėdė yra juodas (jeigu jo nėra, tai laikome, kad jis yra juodas) ir koreguojama viršūnė yra dešinys tėvo vaikas. Mes vykdome kairį posūkį apie tėvą. Po šio veiksmo koreguojama viršūne tampa buvęs viršūnės tėvas (koregavimą pradedam nuo pradžios).
5. Koreguojamos viršūnės tėvas yra raudonas, dėdė yra juodas arba jo apskritai nėra ir viršūnė yra kairys tėvo vaikas. Sukeičiam protėvio ir tėvo spalvas. Atliekame dešinį posūkį apie protėvį (koregavimą pradedam nuo pradžios). Nekeičiam koreguojamos viršūnės.

Pašalinimas

Įterpdami elementą į medį sprendėm dviejų vienas po kito einančių raudonų elementų problemą (tai pažeidė vieną iš taisyklių). Ištrinant elementą iš medžio, reikės tikrinti ar mes nesumažinome viename kelyje juodų elementų skaičiaus. Jeigu iš medžio šalinamas lapas (kraštinis elementas), tai galime iš karto vykdyti veiksmus. Jeigu šalinamas ne lapas, o kita viršūnė, tai tada yra randama tinkamiausia reikšmė (dešinėje – mažiausias elementas, kairėje – didžiausias), kuri galėtų pakeisti šalinamą viršūnę. Sukeičiame reikšmes ir atliekame pašalinimo operaciją jau su rastu elementu (jį žymėsime X). Tai būtinai bus arba lapas, arba viršūnė su vienu vaiku. Pastaba : .

• Jeigu viršūnė X turi vaiką, sukeičiame ją su vaiku.
• Jeigu viršūnė X yra raudona, tai mes ją sukeitėme su juodu vaiku (po sukeitimo vaikas tapo X tėvu). Nepažeidžiama nė viena Raudonai-juodo medžio savybė – galime baigti (žiūrėti koregavimo pabaigą).
• Jeigu viršūnė X yra juoda, bet vaikas raudonas, tai mes vaiką nuspalvinam juodai (po sukeitimo vaikas tapo X tėvu). Nepažeidžiama nė viena Raudonai-Juodo medžio savybė – galime baigti(žiūrėti koregavimo pabaigą).
• Viršūnė X neturėjo vaikų arba ji turėjo juodą vaiką (po apkeitimo vaikas tapo viršūnės X tėvu), koregavimą pradedame nuo juos.

Pastabos:

• Jei atskirai nebus nurodoma, kad yra keičiama koreguojamoji viršūnė, kalbama apie tą pačią viršūnę
• Analizuojam tą atvejį, kai koreguojama viršūnė yra kairys tėvo vaikas. Jeigu jis bus dešinys, tai kairę reikės keisti į dešinę ir atvirkščiai
• Įsivesime naują sąvoką – brolis, koreguojamos viršūnės tėvo kitas vaikas
• Visus žingsnius reikia vykdyti iš eilės, jeigu nenurodyta pradėti iš naujo.

Koregavimas:

1. Koreguojama viršūnė yra šaknis arba ji nėra juoda, baigiam koregavimą.
2. Jeigu koreguojamos viršūnės brolio spalva yra raudona, tai brolio spalvą keičiam į juodą, tėvo į raudoną. Atliekam kairį posūkį apie tėvą. Koreguojama viršūnė nėra keičiama
3. Koreguojamos viršūnės brolio abu vaikai yra juodi (NIL reikšmė reiškia juoda spalvą!). Keičiam brolio spalvą į raudoną. Koreguojama viršūnė tampa koreguojamos viršūnės tėvas (Nesumaišyti su viršūne X. Ši viršūnė koregavimo pradžioje buvo koreguojama viršūnė, jos rodyklė yra įsimenama, kad vėliau ją galima būtų ištrinti!), pradedam žingsnius nuo pradžių
4. Koreguojamos viršūnės brolio abiejų vaikų spalva nėra juoda, bet brolio dešinys vaikas yra juodas. Brolio kairį vaiką nuspalvinam juodai, brolį – raudonai, atliekam dešinį posūkį apie brolį. Koreguojama viršūnė nėra keičiama
5. Koreguojamos viršūnės brolio abiejų vaikų spalva nėra juoda, tai brolį nuspalvinam tėvo spalva, tėvą nuspalvinam juodai. Brolio dešinį vaiką juodai, atliekam kairį posūkį apie tėvą. Koreguojama viršūnė nėra keičiama.
6. Užbaigti koregavimą.

Koregavimas baigiamas, nuspalviname juodai medžio šaknį ir koreguojamą viršūnę. Pašaliname X viršūnę.

Šaltiniai

1. CS 660: Red–Black tree notes 2008-05-09 iš Wayback Machine projekto.
2. Mathworld: Red–Black Tree