Conţinut
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:
- Fiecare nod are doi copii, colorate fie roșu, fie negru.
- Fiecare nod de frunze de copac este întotdeauna negru.
- Fiecare nod roșu are ambii copii ai săi de culoare neagră.
- Nu există două noduri roșii adiacente (Un nod roșu nu poate avea un părinte roșu sau un copil roșu).
- 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ă”).
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
#Arborele #roșunegru #copaci #căutare #binari #autoechilibrați #explicați #exemple
Arborele roșu-negru: copaci de căutare binari auto-echilibrați explicați cu exemple