Arbore binar complet

Un arbore binar complet are toate nivelurile pline. Dacă rădăcina este pe nivelul 0 și ultimul nivel este h, numărul total de noduri este 2^{h+1}-1. De exemplu, arborele cu 1 rădăcină și 2 fii are 3 noduri și este complet.

Un arbore binar aproape complet are toate nivelurile, în afară eventual de ultimul, pline; nodurile ultimului nivel ocupă primele locuri de la stânga. Arborele cu nodurile 1, 2, 3, 4, în această ordine pe niveluri, este aproape complet, dar nu complet: nivelul ultim conține numai nodul 4, fiul stâng al lui 2. Aceasta este forma folosită de heap.

Pentru reprezentarea secvențială a unui arbore binar aproape complet, cu indici de la 1, fiii nodului de pe poziția $i$ sunt pe $2i$ și $2i+1$, când aceste poziții nu depășesc $n$; tatăl său este pe $[i/2]$. Cu indici de la 0, pozițiile fiilor sunt $2i+1$ și $2i+2$, iar tatăl este pe $[(i-1)/2]$. Pe nivelul $k$ încap cel mult $2^k$ noduri, iar un arbore complet cu ultimul nivel $h$ are $2^{h+1}-1$ noduri, dintre care $2^h$ sunt frunze. Înălțimea arborelui aproape complet cu $n$ noduri este $[{\log }_{2}n]$, dacă rădăcina este pe nivelul 0. Nu este nevoie de pointeri: poziția în vector determină legăturile.

Exemplul 1 — fiul stâng prin indice.

#include <iostream>
using namespace std;
int main() {
    int v[] = {0, 1, 2, 3, 4};
    int i = 2, n = 4;
    if (2 * i <= n) cout << v[2 * i];
    if (2 * i + 1 <= n) cout << " " << v[2 * i + 1];
}

Pozițiile sunt 1–4, iar v[0] este neutilizat. Pentru i=2, fiul stâng se află pe poziția 4 și are valoarea 4; poziția 5 a fiului drept depășește n, deci nodul 2 are un singur fiu și programul afișează 4. Forma arborelui nu impune ordinea valorilor; condiția de ordine apare separat la heap.

Exemplul 2 — niveluri, înălțime și frunze pentru $n=10$. Programul află nivelul fiecărui nod împărțind repetat indicele la 2 până la 1 și numără frunzele, adică nodurile $i$ pentru care $2i>n$:

#include <iostream>
using namespace std;
int main() {
    int n = 10, frunze = 0, h = 0;
    for (int i = 1; i <= n; ++i) {
        int x = i, nivel = 0;
        while (x > 1) { x /= 2; ++nivel; }
        cout << nivel << " ";
        if (nivel > h) h = nivel;
        if (2 * i > n) ++frunze;
    }
    cout << "\n" << h << " " << frunze;
}

Se afișează 0 1 1 2 2 2 2 3 3 3, apoi 3 5. Nivelurile conțin 1, 2, 4 și 3 noduri: primele trei sunt pline, iar ultimul are 3 noduri în loc de 8, așezate la stânga. Înălțimea este $[{\log }_{2}10]=3$. Frunzele sunt nodurile 6, 7, 8, 9 și 10; nodul 5 are fiii 10 și 11, dar 11 depășește $n$, deci doar fiul 10 există. Un arbore aproape complet cu $n$ noduri are $n-[n/2]$ frunze, adică nodurile de pe pozițiile $[n/2]+1,\dots ,n$.

Arbore complet. Cu 3 niveluri pline (înălțimea 2) sunt $2^3-1=7$ noduri, iar cu 4 niveluri pline sunt 15, dintre care 8 frunze. Un număr de noduri care nu are forma $2^{h+1}-1$ nu poate forma un arbore complet. De aceea arborele cu 4 noduri este aproape complet, dar nu complet.

Exemplu în formatul examenului. Un arbore binar aproape complet cu 11 noduri este memorat într-un vector cu indici de la 1. Care sunt fiii și tatăl nodului de pe poziția 5?

• a) fiii 9 și 10, tatăl 2
• b) fiii 10 și 11, tatăl 2
• c) fiii 10 și 11, tatăl 3
• d) fiul 10, tatăl 2

Răspunsul corect este b). Fiii sunt pe pozițiile $2\cdot 5=10$ și $2\cdot 5+1=11$, iar ambele nu depășesc $n=11$. Tatăl este pe poziția $[5/2]=2$. Varianta a) folosește $2i-1$ și $2i$ în loc de $2i$ și $2i+1$, iar varianta c) calculează greșit tatăl, ca $[5/2]+1$. Varianta d) ar fi corectă pentru un arbore cu 10 noduri. În acest arbore, nodul de pe poziția 6 nu are fii, deoarece $2\cdot 6=12>11$.

Greșeli frecvente

• Greșit: arborele cu patru noduri dispuse pe niveluri este complet.
  Corect: este aproape complet; pentru două niveluri pline sunt necesare 3 noduri, iar pentru trei niveluri pline, 7.
• Greșit: la indexarea de la 1, fiul stâng al poziției i este la 2i+1.
  Corect: este la 2i.
• Greșit: „complet” înseamnă că valorile sunt sortate.
  Corect: numește forma arborelui, nu ordinea cheilor.

Înainte și după