Sarkanmelns koks: pašizlīdzināti bināro meklēšanas koki, kas izskaidroti ar piemēriem

Kas ir sarkan-melns koks?

Sarkanmelnais koks ir pašbalansējošs binārā meklēšanas koks (BST). Sarkanmelnā kokā katrs mezgls ievēro šos noteikumus:

  1. Katrā mezglā ir divi bērni, kuru krāsa ir vai nu sarkana, vai melna.
  2. Katrs koka lapu mezgls vienmēr ir melns.
  3. Katrā sarkanajā mezglā abi bērni ir melnā krāsā.
  4. Nav divu blakus esošu sarkanu mezglu (sarkanā mezglā nevar būt sarkans vecāks vai sarkans bērns).
  5. Katrā ceļā no saknes līdz koka lapas mezglam ir vienāds melno mezglu skaits (saukts par "melno augstumu").

Ievietošana sarkan-melnos kokos

Mezgls sākotnēji tiek ievietots sarkan-melnā kokā tāpat kā jebkurš binārā meklēšanas koks. Pēc tam jaunajam mezglam tiek piešķirta sarkana krāsa. Pēc šī mezgla ievietošanas koks ir jāpārbauda, ​​lai pārliecinātos, ka neviens no pieciem rekvizītiem nav pārkāpts. Ja kāda īpašība ir pārkāpta, ir trīs potenciālie gadījumi, kad nepieciešama vai nu pagriešana pa kreisi, pa labi un / vai mezglu pārkrāsošana. Gadījumi ir atkarīgi no pašreizējā mezgla "tēvoča". Precīzāk, vai mezgls "onkulis" ir melns vai sarkans. Lai iegūtu vairāk informācijas par ievietošanu, trīs gadījumus var atrast šeit.

Kreisi noliektais sarkanais – melnais koks

Kreisi noliekts sarkanais-melnais (LLRB) koks ir pašbalansējošs binārā meklēšanas koks. Tas ir sarkanā-melnā koka variants un garantē tādu pašu asimptotisko sarežģītību darbībās, taču ir veidots tā, lai to būtu vieglāk īstenot.

Kreisā pusē noliekto sarkanmelno koku īpašības

Visiem piedāvātajiem sarkanmelnā koka algoritmiem raksturīgs sliktākā meklēšanas laiks, ko ierobežo mazs log N konstants reizinājums N atslēgu kokā, un praksē novērotā uzvedība parasti ir tā pati daudzkārtne ātrāk nekā sliktākajā gadījumā saistīts, tuvu optimālajam log N pārbaudītie mezgli, kas būtu novērojami pilnīgi līdzsvarotā kokā.

Konkrēti, kreisās puses sarkanā-melnā 2-3 kokā, kas uzbūvēts no N nejaušiem taustiņiem: -> Izlases veiksmīga meklēšana pārbauda log2 N- 0,5 mezglus. -> Vidējais koka augstums ir aptuveni2 log2 N