Arbori binari: parcurgeri și arbori de căutare

Un arbore binar are pentru fiecare nod cel mult doi copii, numiți stâng și drept. Pozițiile lor contează: un singur copil stâng nu este aceeași structură cu un singur copil drept. Preordinea, inordinea și postordinea descriu trei momente diferite de prelucrare a rădăcinii.

Un arbore binar de căutare, BST, adaugă o regulă asupra valorilor: cele din subarborele stâng sunt mai mici, iar cele din subarborele drept mai mari. Vom folosi chei distincte, ignorând inserările repetate.

Cum funcționează

În preordine vizităm rădăcina, apoi subarborele stâng și apoi pe cel drept. În inordine parcurgem stânga, rădăcina, dreapta. În postordine parcurgem stânga, dreapta, rădăcina. Toate folosesc aceeași structură recursivă; diferă poziția operației de prelucrare. Cazul de bază este copilul absent.

Reprezentăm nodurile într-un tablou de structuri cu valoare, indicele copilului stâng și indicele copilului drept. Indicele zero înseamnă absență, iar nodurile reale sunt 1..used. Această reprezentare separă forma arborelui de adresele de memorie și permite aceeași logică într-un vector. Capacitatea este 101, pentru maximum 100 de inserări; numărul logic de noduri poate fi mai mic dacă apar dubluri.

Inserarea într-un BST compară valoarea cu nodul curent și continuă într-un singur subarbore. Când ajunge la indicele zero, creează un nod nou. Funcția întoarce rădăcina subarborelui actualizat, iar apelantul o reține în câmpul potrivit. Dacă valoarea există deja, nu alocăm un nod. O altă politică pentru dubluri ar trebui definită explicit, de exemplu printr-un contor în nod.

Un BST simplu nu este automat echilibrat. Inserarea valorilor deja sortate poate crea un lanț. Nici forma de arbore binar complet nu rezultă din regula de căutare: complet înseamnă niveluri umplute de la stânga, în timp ce BST descrie relații între valori. Heap-ul folosește forma completă și o altă regulă de ordine, între părinte și copii, fără separarea globală stânga-mai-mic și dreapta-mai-mare.

Exemplu urmărit pas cu pas

Inserăm 4,2,6,1,3. Rădăcina este 4, copilul stâng 2 și cel drept 6. Valorile 1 și 3 devin copiii lui 2. Preordinea este 4,2,1,3,6; inordinea 1,2,3,4,6; postordinea 1,3,2,6,4.

Inordinea este crescătoare deoarece toate cheile din stânga unui nod sunt mai mici, iar cele din dreapta mai mari. Această proprietate nu este adevărată pentru un arbore binar oarecare. Repetarea inserării lui 2 nu schimbă arborele în convenția implementată.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
struct Node {
    int value, left, right;
};
Node tree[101];
int used = 0;
int insert(int root, int value) {
    if (root == 0) {
        ++used;
        tree[used] = {value, 0, 0};
        return used;
    }
    if (value < tree[root].value)
        tree[root].left = insert(tree[root].left, value);
    else if (value > tree[root].value)
        tree[root].right = insert(tree[root].right, value);
    return root;
}
void preorder(int x) {
    if (!x)
        return;
    std::cout << tree[x].value << ' ';
    preorder(tree[x].left);
    preorder(tree[x].right);
}
void inorder(int x) {
    if (!x)
        return;
    inorder(tree[x].left);
    std::cout << tree[x].value << ' ';
    inorder(tree[x].right);
}
void postorder(int x) {
    if (!x)
        return;
    postorder(tree[x].left);
    postorder(tree[x].right);
    std::cout << tree[x].value << ' ';
}
int main() {
    int n, root = 0;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        root = insert(root, x);
    }
    preorder(root);
    std::cout << '\n';
    inorder(root);
    std::cout << '\n';
    postorder(root);
    std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
struct Node {
    int value, left, right;
};
std::vector<Node> tree(101);
int used = 0;
int insert(int root, int value) {
    if (root == 0) {
        ++used;
        tree[used] = {value, 0, 0};
        return used;
    }
    if (value < tree[root].value)
        tree[root].left = insert(tree[root].left, value);
    else if (value > tree[root].value)
        tree[root].right = insert(tree[root].right, value);
    return root;
}
void preorder(int x) {
    if (!x)
        return;
    std::cout << tree[x].value << ' ';
    preorder(tree[x].left);
    preorder(tree[x].right);
}
void inorder(int x) {
    if (!x)
        return;
    inorder(tree[x].left);
    std::cout << tree[x].value << ' ';
    inorder(tree[x].right);
}
void postorder(int x) {
    if (!x)
        return;
    postorder(tree[x].left);
    postorder(tree[x].right);
    std::cout << tree[x].value << ' ';
}
int main() {
    int n, root = 0;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        root = insert(root, x);
    }
    preorder(root);
    std::cout << '\n';
    inorder(root);
    std::cout << '\n';
    postorder(root);
    std::cout << '\n';
}

De ce funcționează și cât costă

Inserarea păstrează invariantul BST, deoarece alege subarborele compatibil cu toate comparațiile anterioare. Prin inducție, inordinea sortează subarborele stâng, apoi vizitează cheia și subarborele drept, rezultând o ordine crescătoare globală.

Fiecare parcurgere vizitează toate nodurile o dată, deci costă O(n), cu stivă O(h). Inserarea și căutarea costă O(h), unde h poate fi n pentru un arbore dezechilibrat. Construirea prin n inserări poate ajunge la O(n²); nu promitem automat O(n log n).

Greșeli frecvente

Nu aplica formulele copiilor 2i și 2i+1 unei reprezentări arbitrare cu indici alocați la inserare. Nu presupune că inordinea sortează orice arbore binar. Verifică politica pentru dubluri și capacitatea înainte de a extinde exemplul.

Exersează

Inserează 1,2,3,4 într-un BST gol. Ce formă obții și care este costul căutării lui 4?

Rezolvare explicată: Obții un lanț spre dreapta. Căutarea vizitează toate cele patru noduri; generalizat, această ordine de inserare poate produce cost liniar.

Continuă să înveți

Arbori cu rădăcină, recursivitate și heap.

Întrebări frecvente

Ce înseamnă preordine, inordine și postordine?

Poziția rădăcinii față de parcurgerea subarborilor: înaintea lor, între stânga și dreapta, respectiv după amândoi.

De ce inordinea unui BST este sortată?

Regula BST separă toate cheile mai mici în stânga și pe cele mai mari în dreapta. Inordinea respectă exact această separare la fiecare nod.

Căutarea într-un BST este mereu logaritmică?

Nu. Costul depinde de înălțime. Un arbore degenerat în lanț produce timp liniar; echilibrarea necesită mecanisme suplimentare.

Un heap este un arbore de căutare?

Nu în general. Heap-ul compară părinții cu copiii și păstrează extremul la rădăcină, fără regula globală a subarborilor unui BST.

Cum tratăm cheile duplicate?

Exemplul le ignoră. Alte aplicații pot păstra un contor sau o regulă explicită de plasare, care trebuie respectată și la căutare și ștergere.