Construção e Percursos em Árvores Binárias

A manipulação de árvores binárias é fundamental na ciência da computação. A estrutura básica de um nó pode ser definida utilizando ponteiros para os subnós esquerdo e direito. Abaixo, apresentamos a implementação da criação de uma árvore a partir de uma string em pré-ordem, onde o caractere # indica um nó nulo.

#include <iostream>
#include <string>
#include <algorithm>

struct Node {
    char value;
    Node* left;
    Node* right;
    
    Node(char val) : value(val), left(nullptr), right(nullptr) {}
};

// Construção da árvore a partir de uma string em pré-ordem
Node* buildFromPreorder(const std::string& data, int& idx) {
    if (idx >= data.length() || data[idx] == '#') {
        idx++;
        return nullptr;
    }
    Node* current = new Node(data[idx++]);
    current->left = buildFromPreorder(data, idx);
    current->right = buildFromPreorder(data, idx);
    return current;
}

// Percurso em pré-ordem
void traversePreOrder(Node* root) {
    if (root) {
        std::cout << root->value << " ";
        traversePreOrder(root->left);
        traversePreOrder(root->right);
    }
}

// Percurso em-ordem
void traverseInOrder(Node* root) {
    if (root) {
        traverseInOrder(root->left);
        std::cout << root->value << " ";
        traverseInOrder(root->right);
    }
}

// Percurso pós-ordem
void traversePostOrder(Node* root) {
    if (root) {
        traversePostOrder(root->left);
        traversePostOrder(root->right);
        std::cout << root->value << " ";
    }
}

Propriedades Recursivas: Altura e Nós Folha

A natureza recursiva das árvores permite calcular propriedades estruturais de forma elegante. A altura da árvore é determinada pelo caminho mais longo da raiz até uma folha, enquanto a identificação de nós folha requer a verificação de ausência de filhos.

// Cálculo da altura da árvore
int calculateHeight(Node* root) {
    if (!root) return 0;
    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);
    return std::max(leftHeight, rightHeight) + 1;
}

// Impressão de nós folha em pré-ordem
void printLeafNodes(Node* root) {
    if (root) {
        if (!root->left && !root->right) {
            std::cout << root->value << " ";
        }
        printLeafNodes(root->left);
        printLeafNodes(root->right);
    }
}

Árvore Binária de Busca (BST): Inserção, Busca e Remoção

A Árvore Binária de Busca (BST) mantém a propriedade onde os valores à esquerda são menores e os à direita são maiores ou iguais. A operação de remoção é a mais complexa, pois exige a reestruturação da árvore para manter a invariante da BST. Nesta implementação, ao remover um nó com dois filhos, substituímos seu valor pelo maior valor de sua subárvore esquerda (predecessor).

struct BSTNode {
    int data;
    BSTNode* leftChild;
    BSTNode* rightChild;
    BSTNode(int val) : data(val), leftChild(nullptr), rightChild(nullptr) {}
};

BSTNode* insertNode(BSTNode* root, int val) {
    if (!root) return new BSTNode(val);
    if (val < root->data) {
        root->leftChild = insertNode(root->leftChild, val);
    } else {
        root->rightChild = insertNode(root->rightChild, val);
    }
    return root;
}

BSTNode* searchNode(BSTNode* root, int target) {
    if (!root || root->data == target) return root;
    if (target < root->data) return searchNode(root->leftChild, target);
    return searchNode(root->rightChild, target);
}

// Encontra o nó com o maior valor (predecessor)
BSTNode* findMaxNode(BSTNode* node) {
    while (node->rightChild != nullptr) {
        node = node->rightChild;
    }
    return node;
}

BSTNode* deleteNode(BSTNode* root, int val) {
    if (!root) return nullptr;
    
    if (val < root->data) {
        root->leftChild = deleteNode(root->leftChild, val);
    } else if (val > root->data) {
        root->rightChild = deleteNode(root->rightChild, val);
    } else {
        // Nó com apenas um filho ou sem filhos
        if (!root->leftChild) {
            BSTNode* temp = root->rightChild;
            delete root;
            return temp;
        } else if (!root->rightChild) {
            BSTNode* temp = root->leftChild;
            delete root;
            return temp;
        }
        
        // Nó com dois filhos: obtém o predecessor (maior da subárvore esquerda)
        BSTNode* predecessor = findMaxNode(root->leftChild);
        root->data = predecessor->data;
        root->leftChild = deleteNode(root->leftChild, predecessor->data);
    }
    return root;
}

Aplicação de Tabelas Hash: Sistema de Autenticação de Contas

Para cenários que exigem buscas rápidas e gerenciamento de pares chave-valor, como um sistema de registro e login de contas, as tabelas hash são ideais. Em C++, a estrutura std::unordered_map fornece essa funcionalidade com complexidade de tempo média O(1) para inserções e consultas.

#include <iostream>
#include <unordered_map>
#include <string>

void processAuthentication() {
    int operations;
    std::cin >> operations;
    
    std::unordered_map<std::string, std::string> userDatabase;
    
    for (int i = 0; i < operations; ++i) {
        char action;
        std::string userId, pwd;
        std::cin >> action >> userId >> pwd;
        
        if (action == 'R') { // Registro
            if (userDatabase.find(userId) != userDatabase.end()) {
                std::cout << "ERROR: Account already exists\n";
            } else {
                userDatabase[userId] = pwd;
                std::cout << "SUCCESS: Account created\n";
            }
        } else if (action == 'L') { // Login
            auto it = userDatabase.find(userId);
            if (it == userDatabase.end()) {
                std::cout << "ERROR: Account not found\n";
            } else if (it->second == pwd) {
                std::cout << "SUCCESS: Login accepted\n";
            } else {
                std::cout << "ERROR: Invalid credentials\n";
            }
        }
    }
}