Patstāvīgais darbs kursā "Algoritmi un datu struktūras". Sarkanmelnie koki

Binārie koki parasti tiek izmantoti dinamisku datu glabāšanai. Meklēšanas, ievietošanas un dzēšanas operācijas šādā kokā ir iespējams veikt daudz ātrāk, ja tas ir līdzsvarots. Pretējā gadījumā, ja koks ir liels, tad tā darbības ātrums un efektivitāte var būtiski samazināties, līdz pat saistīto sarakstu līmenim.
Paņēmieni bināro koku līdzsvarošanai ir samērā vienkārši īstenojami, taču var ievērojami palielināt izpildes laiku. Ja ir nepieciešams izpildīt lielu skaitu ievietošanas un dzēšanas operāciju, tad priekšrocības ātrdarbības ziņā, salīdzinot ar saistītiem sarakstiem ir samērā nelielas.
Sarkanmelnie koki ir viens no šādiem paņēmieniem – nosakot kārtību, kādā lauki tiek iekrāsoti, ir iespējams panākt, ka koks veidojas samērā balansēts. Meklēšanas operācijas tiek izpildītas ātrāk nekā saistītajos sarakstos un papildus pointeri tiek izmantoti lietderīgi.

Koks – mezglpunktu kopa, kas satur sakni, kurai ir 0 vai vairāk apakškoku. Katrs apakškoks atbilst koka definīcijai.

Sakārtots koks – koks, kuram bērni ir sakārtoti noteiktā kārtībā, t.i. viennozīmīgi var noteikt, kurš ir pirmais, kurš – otrais, utt.

Binārs koks – sakārtots koks, kuram ir ne vairāk kā 2 bērni. Katram bērnam ir viennozīmīgi nosakāms, vai tas ir kreisais vai labais.…