Ce este un copac roșu-negru?

Arborele roșu-negru este un tip de arbore de căutare binară (BST) auto-echilibrat. Într-un copac roșu-negru, fiecare nod respectă aceste reguli:

  1. Fiecare nod are doi copii, colorate fie roșu, fie negru.
  2. Fiecare nod de frunze de copac este întotdeauna negru.
  3. Fiecare nod roșu are ambii copii ai săi de culoare neagră.
  4. Nu există două noduri roșii adiacente (Un nod roșu nu poate avea un părinte roșu sau un copil roșu).
  5. Fiecare cale de la rădăcină la un nod cu frunze de copac are același număr de noduri negre (numite „înălțime neagră”).
Arborele rosu negru copaci de cautare binari auto echilibrati explicati cu

Introducerea în copaci roșu-negru

Un nod este introdus inițial într-un copac roșu-negru la fel ca orice copac de căutare binară. Noul nod primește apoi o culoare roșie. După ce acel nod a fost inserat, arborele trebuie validat pentru a se asigura că niciuna dintre cele cinci proprietăți nu a fost încălcată. Dacă o proprietate a fost încălcată, există trei cazuri potențiale care necesită fie o rotație la stânga, o rotație la dreapta și / sau o recolorare a nodurilor. Cazurile sunt dependente de „unchiul” nodului curent. Mai exact, dacă nodul „unchiului” este negru sau roșu. Pentru mai multe informații despre inserare, puteți găsi cele trei cazuri Aici.

Arborele roșu-negru înclinat spre stânga

Un arbore roșu-negru înclinat spre stânga (LLRB) este un tip de arbore de căutare binar auto-echilibrat. Este o variantă a arborelui roșu-negru și garantează aceeași complexitate asimptotică pentru operațiuni, dar este conceput pentru a fi mai ușor de implementat.

Proprietățile copacilor roșii-negri înclinați spre stânga

Toți algoritmii de copac roșu-negru care au fost propuși sunt caracterizați de un timp de căutare în cel mai rău caz delimitat de un mic multiplu constant de log N într-un copac de N chei, iar comportamentul observat în practică este de obicei același multiplu mai rapid decât cel mai rău caz legat, apropiat de logul optim N noduri examinate care ar fi observate într-un arbore perfect echilibrat.

În mod specific, într-un arbore de 2-3 roșu-negru înclinat spre stânga construit din N taste aleatorii: -> O căutare aleatorie reușită examinează log2 N – 0,5 noduri. -> Înălțimea medie a copacului este de aproximativ 2 log2 N