Cuprins:

1. B-arbori

2. Echilibrarea arborilor binari prin rotații

3. Arbori AVL

4. Arbori Rosu-Negru

• 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:

1. Fiecare nod are cel mult m fii

2. Fiecare nod intern are cel puțin ⌈m/2⌉ fii.

3. Fiecare non-frunză are cel puțin 2 fii.

4. Toate frunzele sunt pe același nivel

5. Un nod intern cu k fii conține k-1 valori

Inserția

1. Se caută recursiv locația pentru inserție conform arborilor de căutare.

2. Dacă locația pentru inserție este un nod cu locuri libere (sub numărul maxim de valori admise), se inserează direct.

3. Dacă nodul este plin atunci split:

   1. se alege mediana dintre {valorile din nod împreună cu valoarea pentru inserat}

   2. se crează două noduri, cel stâng cu valorile mai mici decât mediana, iar cel drept cu valori mai mari decât mediana.

   3. 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.

Inserția

1. Se caută recursiv locația pentru inserție conform arborilor binari de căutare.

2. La întoarcerea din recursie se recalculează factorii de echilibru în fiecare nod prin care am trecut.

3. Dacă ajungem să calculăm un factor de echilibru = -2 sau 2, vom repara arborele prin rotații.