B-arbori
Echilibrarea arborilor binari prin rotații
Arbori AVL
Arbori Rosu-Negru
Există situații când nu este suficient să utilizăm un arbore de căutare clasic și în același timp să se păstreze timpul O(log n) pentru operațiile de căutare, inserție și stergere.
Adeseori creăm arbori degenerați, mai ales când setul de date nu este uniform distribuit, sau când utilizatorul introduce date deja sortate.
Avem nevoie de o soluție care să garanteze înălțimea de tip O(log n) a arborelui pentru orice intrare.
Inventați de Rudolf Bayer și Edward M. McCreight în cadrul Boeing Research Labs, în 1970.
Definiția lui Knuth: Un B-arbore de ordin m satisface:
Fiecare nod are cel mult m fii
Fiecare nod intern are cel puțin ⌈m/2⌉ fii.
Fiecare non-frunză are cel puțin 2 fii.
Toate frunzele sunt pe același nivel
Un nod intern cu k fii conține k-1 valori
B-arbore de ordin 3
B-arbore de ordin 5
Inserția
Se caută recursiv locația pentru inserție conform arborilor de căutare.
Dacă locația pentru inserție este un nod cu locuri libere (sub numărul maxim de valori admise), se inserează direct.
Dacă nodul este plin atunci split:
se alege mediana dintre {valorile din nod împreună cu valoarea pentru inserat}
se crează două noduri, cel stâng cu valorile mai mici decât mediana, iar cel drept cu valori mai mari decât mediana.
mediana va urca în nodul părinte, posibil cauzând alte splitări. Dacă nu există părinte, atunci se creează un nod nou, iar înălțimea arborelui crește cu 1.
Rotație dreapta
Rotație stânga
Rotație dreapta-stânga
Rotație stânga-dreapta
inventat de Georgy Adelson-Velsky și Evgenii Landis, în 1962.
Arborii AVL sunt arbori binari echilibrați conform unei măsuri numită factorul de echilibru:
Factorul de echilibru = înălțimea subarborelui drept - înalțimea subarborelui stâng.
Într-un arbore AVL toate operațiile mențin factorul de echilibru -1, 0 sau 1 în orice nod.
Inserția
Se caută recursiv locația pentru inserție conform arborilor binari de căutare.
La întoarcerea din recursie se recalculează factorii de echilibru în fiecare nod prin care am trecut.
Dacă ajungem să calculăm un factor de echilibru = -2 sau 2, vom repara arborele prin rotații.
Inventat de Leonidas J. Guibas și Robert Sedgewick, în 1978, pe baza unui articol al lui Rudolf Bayer (despre B-arbori binari simetrici, 1972)
Arborii Roșu-Negru:
au fiecare nod colorat roșu sau negru (culoarea se poate codifica folosind 1 bit din câmpul de valoare, cum ar fi bitul de semn)
au rădăcina colorată negru
nu pot avea două noduri roșii consecutive
fiecare drum dinspre rădăcină către frunză are același număr de noduri negre
Dorim să inserăm X
Inserția
Se caută recursiv locația pentru inserție conform arborilor binari de căutare, nodul nou inserat X, va fi roșu.
Dacă tatăl lui X este negru, stop. Altfel, există două noduri roșii consecutive care încalcă regula arborelui: X și tatăl lui X:
Dacă X nu are bunic, swap culoarea tatălui.
Dacă X are unchi roșu atunci (tata, unchi) fac swap de culoare cu bunicul care devine roșu și acum se repară bunicul pornind de la început verificarea cu nodul curent = bunicul.
Dacă X și tatăl lui X nu sunt ambii fii drepți sau fii stângi, rotesc întâi X peste tatăl, și repar culoarea lui tatăl, de la începutul verificării.
Dacă X nu are unchi sau are unchi negru, se rotește tatăl peste bunic și fac swap de culoare.
Arborii 2-3-4 (B-arbori de ordin 4) sunt izomorfi cu arborii rosu-negru.