Tutorial: Arbori în C++ - Teorie și Practică

📚 Introducere în Arbori

Ce este un arbore?
Un arbore este o structură de date ierarhică formată din noduri conectate prin muchii, fără cicluri. Fiecare arbore are un nod rădăcină și fiecare nod poate avea zero sau mai mulți copii.

Terminologie de Bază

Termen	Definiție	Exemplu
Nod (Node)	Element fundamental al arborelui care conține date	Un nod cu valoarea 10
Rădăcină (Root)	Nodul de la vârful arborelui, fără părinte	Primul nod inserat
Frunză (Leaf)	Nod fără copii	Nodurile terminale
Înălțime (Height)	Lungimea celui mai lung drum de la rădăcină la frunză	h = 3 pentru un arbore cu 4 nivele
Adâncime (Depth)	Distanța de la rădăcină la un nod specific	d = 2 pentru un nod la nivelul 3

🎯 Teorie - Tipuri de Arbori

Arbore Binar

Un arbore în care fiecare nod are maximum 2 copii (stâng și drept).

Proprietăți:

Număr maxim de noduri la nivelul i: 2^i
Număr maxim de noduri într-un arbore de înălțime h: 2^(h+1) - 1
Înălțime minimă pentru n noduri: ⌊log₂(n)⌋

Binary Search Tree (BST)

Un arbore binar cu proprietatea că pentru fiecare nod:

Toate valorile din subarborele stâng sunt mai mici
Toate valorile din subarborele drept sunt mai mari

Complexitate Timp:
• Căutare: O(log n) mediu, O(n) worst case
• Inserare: O(log n) mediu, O(n) worst case
• Ștergere: O(log n) mediu, O(n) worst case

Arbore AVL

Un BST auto-echilibrat unde diferența de înălțime între subarborii stâng și drept este maximum 1.

Factor de Echilibru: height(left) - height(right) ∈ {-1, 0, 1}

Avantaje:
• Garantează O(log n) pentru toate operațiile
• Păstrează arborele echilibrat automat
• Ideal pentru aplicații cu multe căutări

Heap (Min/Max)

Un arbore binar complet cu proprietatea heap:

Max Heap: Părintele ≥ Copiii
Min Heap: Părintele ≤ Copiii

Utilizări:
• Priority Queue
• Heap Sort
• Algoritmul lui Dijkstra

💻 Implementare Binary Search Tree

Structura Nod

struct Nod {
    int data;
    Nod* left;
    Nod* right;
    
    // Constructor
    Nod(int val) : data(val), left(nullptr), right(nullptr) {}
};

Clasa BST Îmbunătățită

class BST {
private:
    Nod* root;
    
    // Funcții helper recursive
    Nod* insertHelper(Nod* node, int value) {
        if (!node) {
            return new Nod(value);
        }
        
        if (value < node->data) {
            node->left = insertHelper(node->left, value);
        }
        else if (value > node->data) {
            node->right = insertHelper(node->right, value);
        }
        
        return node;
    }
    
    Nod* findMin(Nod* node) {
        while (node && node->left) {
            node = node->left;
        }
        return node;
    }
    
    Nod* deleteHelper(Nod* node, int value) {
        if (!node) return nullptr;
        
        if (value < node->data) {
            node->left = deleteHelper(node->left, value);
        }
        else if (value > node->data) {
            node->right = deleteHelper(node->right, value);
        }
        else {
            // Nod găsit - 3 cazuri
            
            // Caz 1: Nod frunză
            if (!node->left && !node->right) {
                delete node;
                return nullptr;
            }
            
            // Caz 2: Un singur copil
            if (!node->left) {
                Nod* temp = node->right;
                delete node;
                return temp;
            }
            if (!node->right) {
                Nod* temp = node->left;
                delete node;
                return temp;
            }
            
            // Caz 3: Doi copii - găsește succesorul
            Nod* successor = findMin(node->right);
            node->data = successor->data;
            node->right = deleteHelper(node->right, successor->data);
        }
        
        return node;
    }
    
    void inorderHelper(Nod* node) {
        if (node) {
            inorderHelper(node->left);
            cout << node->data << " ";
            inorderHelper(node->right);
        }
    }
    
    int heightHelper(Nod* node) {
        if (!node) return -1;
        return 1 + max(heightHelper(node->left), heightHelper(node->right));
    }

public:
    BST() : root(nullptr) {}
    
    void insert(int value) {
        root = insertHelper(root, value);
    }
    
    void remove(int value) {
        root = deleteHelper(root, value);
    }
    
    bool search(int value) {
        Nod* current = root;
        while (current) {
            if (value == current->data) return true;
            if (value < current->data) current = current->left;
            else current = current->right;
        }
        return false;
    }
    
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }
    
    int height() {
        return heightHelper(root);
    }
};

⚠️ Erori comune în codul original:
• În funcția deleteValue, condiția pentru copilul stâng/drept era inversată
• Lipsea destructor pentru eliberarea memoriei
• Nu se verifica duplicatele la inserare

⚙️ Operații pe Arbori

1. Parcurgeri (Traversals)

// Preordine: Rădăcină -> Stânga -> Dreapta
void preorder(Nod* node) {
    if (node) {
        cout << node->data << " ";
        preorder(node->left);
        preorder(node->right);
    }
}

// Inordine: Stânga -> Rădăcină -> Dreapta (sortare pentru BST)
void inorder(Nod* node) {
    if (node) {
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
}

// Postordine: Stânga -> Dreapta -> Rădăcină
void postorder(Nod* node) {
    if (node) {
        postorder(node->left);
        postorder(node->right);
        cout << node->data << " ";
    }
}

// Parcurgere pe nivel (BFS) - ca în codul tău original
void levelOrder(Nod* root) {
    if (!root) return;
    
    queue q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; i++) {
            Nod* current = q.front();
            q.pop();
            
            cout << current->data << " ";
            
            if (current->left) q.push(current->left);
            if (current->right) q.push(current->right);
        }
        cout << endl; // Newline după fiecare nivel
    }
}

2. Operații Avansate

// Găsește cel mai mic strămoș comun (LCA)
Nod* findLCA(Nod* root, int a, int b) {
    if (!root) return nullptr;
    
    // Dacă ambele valori sunt mai mici, LCA e în stânga
    if (a < root->data && b < root->data) {
        return findLCA(root->left, a, b);
    }
    
    // Dacă ambele valori sunt mai mari, LCA e în dreapta
    if (a > root->data && b > root->data) {
        return findLCA(root->right, a, b);
    }
    
    // Altfel, nodul curent este LCA
    return root;
}

// Verifică dacă arborele este BST valid
bool isBST(Nod* root, int minVal = INT_MIN, int maxVal = INT_MAX) {
    if (!root) return true;
    
    if (root->data <= minVal || root->data >= maxVal) {
        return false;
    }
    
    return isBST(root->left, minVal, root->data) && 
           isBST(root->right, root->data, maxVal);
}

// Găsește diametrul arborelui
int diameter(Nod* root, int& maxDiam) {
    if (!root) return 0;
    
    int leftHeight = diameter(root->left, maxDiam);
    int rightHeight = diameter(root->right, maxDiam);
    
    maxDiam = max(maxDiam, leftHeight + rightHeight);
    
    return 1 + max(leftHeight, rightHeight);
}

🎯 Probleme Practice

Problema 1: Găsește al K-lea cel mai mic element

Ușor

Cerință: Într-un BST, găsește al K-lea cel mai mic element.

int kthSmallest(Nod* root, int k, int& count) {
    if (!root) return -1;
    
    // Parcurgere inordine
    int left = kthSmallest(root->left, k, count);
    if (left != -1) return left;
    
    count++;
    if (count == k) return root->data;
    
    return kthSmallest(root->right, k, count);
}

Complexitate: O(k) timp, O(h) spațiu
Hint: Folosește parcurgerea inordine care dă elementele sortate într-un BST.

Problema 2: Inversează un Arbore Binar

Ușor

Cerință: Inversează un arbore binar (oglindește-l).

Nod* invertTree(Nod* root) {
    if (!root) return nullptr;
    
    // Swap copiii
    Nod* temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    // Recursiv pentru subarbori
    invertTree(root->left);
    invertTree(root->right);
    
    return root;
}

Problema 3: Construiește BST din Array Sortat

Mediu

Cerință: Având un array sortat, construiește un BST echilibrat.

Nod* sortedArrayToBST(vector& arr, int start, int end) {
    if (start > end) return nullptr;
    
    int mid = start + (end - start) / 2;
    Nod* root = new Nod(arr[mid]);
    
    root->left = sortedArrayToBST(arr, start, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, end);
    
    return root;
}

Exemplu: [1, 2, 3, 4, 5, 6, 7] → BST echilibrat cu rădăcina 4

Problema 4: Serializare și Deserializare BST

Dificil

Cerință: Implementează funcții pentru a serializa un BST într-un string și a-l reconstrui.

// Serializare folosind preordine
void serialize(Nod* root, string& result) {
    if (!root) {
        result += "# "; // Marker pentru NULL
        return;
    }
    
    result += to_string(root->data) + " ";
    serialize(root->left, result);
    serialize(root->right, result);
}

// Deserializare
Nod* deserialize(istringstream& stream) {
    string val;
    stream >> val;
    
    if (val == "#") return nullptr;
    
    Nod* root = new Nod(stoi(val));
    root->left = deserialize(stream);
    root->right = deserialize(stream);
    
    return root;
}

Problema 5: Găsește Calea cu Suma K

Mediu

Cerință: Verifică dacă există o cale de la rădăcină la frunză cu suma K.

bool hasPathSum(Nod* root, int targetSum) {
    if (!root) return false;
    
    // Am ajuns la o frunză?
    if (!root->left && !root->right) {
        return root->data == targetSum;
    }
    
    int remainingSum = targetSum - root->data;
    return hasPathSum(root->left, remainingSum) || 
           hasPathSum(root->right, remainingSum);
}

🚀 Demo Interactiv BST

Testează Operațiile BST

> Consolă BST
> Inserează valori pentru a începe...

Arborele va apărea aici...

📊 Comparație Complexități

Structură	Căutare	Inserare	Ștergere	Spațiu
BST (mediu)	O(log n)	O(log n)	O(log n)	O(n)
BST (worst)	O(n)	O(n)	O(n)	O(n)
AVL Tree	O(log n)	O(log n)	O(log n)	O(n)
Red-Black Tree	O(log n)	O(log n)	O(log n)	O(n)
B-Tree	O(log n)	O(log n)	O(log n)	O(n)

🎓 Sfaturi și Trucuri

✅ Best Practices

Folosește pointeri inteligenți (unique_ptr, shared_ptr) pentru gestionarea memoriei
Implementează destructor pentru a evita memory leaks
Consideră folosirea template-urilor pentru tipuri generice
Adaugă validare pentru input și tratare de excepții
Pentru arbori mari, consideră implementări iterative în loc de recursive

❌ Greșeli Comune

Uitarea să verifici nullptr înainte de accesare
Memory leaks din cauza lipsei delete
Modificarea structurii în timpul parcurgerii
Confuzie între succesor și predecesor
Implementare greșită a ștergerii cu doi copii

📚 Resurse Suplimentare

Pentru studiu aprofundat:

📖 "Introduction to Algorithms" - Cormen, Leiserson, Rivest, Stein
🌐 GeeksforGeeks - Tree Data Structure
💻 LeetCode - Tree Problems Collection
🎥 YouTube - Abdul Bari's DSA Playlist
📝 CP-Algorithms - Binary Search Trees