Sarkan-melnie koki (Red Black Tree)

Koks ir struktūra, kas attēlo hierarhiskas attiecības starp datu laukiem. Koki ir viena no vissvarīgākajām datu struktūrām datoru zinātnē, jo ar to palīdzību var vieglāk organizēt informācijas glabāšanu un tās apstrādi.
Koks – mezglpunktu kopa (var būt tukša), kas satur sakni, kurai ir nulle vai vairāk apakškoku.
Sakne (root) – mezgls, kas ir koka pašā augšā (augšējais līmenis).
Zars (edge) – saite starp 2 līmeņiem.
Mezgls jeb mezglpunkts (node) – katrs lauks kokā. Tie ir domāti informācijas glabāšanai.
Lapa (leaf) – lauks, kuram nav apakšlīmeņu (nav bērnu).
Mezgla augstums (height) – garums garākajam ceļam no šī mezgla līdz kādai lapai. Lapām augstums ir 0.
Mezgla dziļums (depth) – garums ceļam no saknes līdz šim mezglam.
Sarkan-Melno koku atklāja 1972. gadā Baijers (Bayer), zem nosaukuma „simetriski binārie B-koki”.
Sarkan-Melnais koks ir viens no daudzajiem meklēšanas koku struktūrām, ar kuru palīdzību var nodrošināt galvenās funkcionālās operācijas O(lg n) laikā vissliktākajā gadījumā. Tas ir binārs meklēšanas koks ar vienu papildus glabāšanas bitu mezglam, tas ir, krāsu, kura var būt vai nu sarkana (red), vai nu melna (black). Veidojot saites, mezgli var tikt iekrāsoti jebkurā ceļā no saknes līdz lapai, līdz ar to Sarkan-Melnie koki nodrošina, ka šādi ceļi ir vairāk nekā divas reizes garāki nekā jebkuri citi, tā tad koks ir apmēram balansēts.
Sarkan-Melnais koks ir tāda saistīta datu struktūra, kam katrā iekšējā mezglā var būt tieši divi bērni. Ja bērnu vai vecāku mezgli neeksistē, tad attiecīgā mezgla norādes laukums satur vērtību NIL. Šajos kokos uzskata NIL kā ārēju mezglu (vai lapu) un atslēgas kā iekšējos koka mezglus. Sarkan-Melnā binārā meklēšanas koka mezglu x laukumi:
atslēga (key): x atslēga, key[x];
loceklis (satellite): locekļa x dati, satellite[x];
kreisais (left): norāde uz x kreiso bērnu, left[x];
labais (right): norāde uz x labo bērnu, right[x];
p (parent): mezgla x vecāki, p[x];
krāsa (color): mezgla krāsa, vai nu sarkana vai arī melna, color[x].
Ja kreisais, labais vai p nav norādīti mezglā, tad tie ir NIL.…