Uma estrutura de dados fundamental para organizar informações de forma hierárquica é a árvore. Cada elemento em uma árvore é denominado nó, e cada nó pode apontar para múltiplos nós filhos. Uma árvore é essencialmente um conjunto de nós originado de um único nó inicial, conhecido como raiz.
A complexidade de algoritmos e estruturas de dados em árvores é frequentemente explorada em entrevistas técnicas, com ênfase particular em árvores binárias e árvores de busca binária.
Árvores Binárias
Uma árvore binária é uma árvore em que cada nó possui no máximo dois filhos, um esquerdo e um direito. A quantidade máxima de nós em um nível i de uma árvore binária é 2i-1. Uma árvore binária com profundidade k pode conter no máximo 2k - 1 nós.
Existem definições específicas para tipos de árvores binárias:
- Árvore Binária Cheia (Full Binary Tree): Cada nó nesta árvore tem exatamente 0 ou 2 filhos.
- Árvore Binária Completa (Complete Binary Tree): Todos os níveis, exceto possivelmente o último, estão completamente preenchidos. Na última camada, os nós são preenchidos da esquerda para a direita o mais próximo possível.
A camada (level) de um nó é deefinida pela distância do nó raiz, com a raiz na camada 0. A altura (height) de uma árvore é a camada do nó folha mais profundo, mais um. Alternativamente, é o comprimetno do caminho mais longo da raiz até uma folha, mais um.
Travessia de Árvores Binárias
A travessia de árvores envolve visitar todos os nós de uma árvore seguindo uma ordem específica. As abordagens comuns incluem:
- Pré-ordem (Pre-order Traversal): Visita a raiz, depois percorre a subárvore esquerda, e por fim percorre a subárvore direita.
- Em-ordem (In-order Traversal): Percorre a subárvore esquerda, visita a raiz, e então percorre a subárvore direita. Para árvores de busca binária, esta travessia resulta em uma sequência ordenada de elementos.
- Pós-ordem (Post-order Traversal): Percorre a subárvore esquerda, depois a subárvore direita, e por fim visita a raiz.
Busca em Profundidade (DFS)
As três travessias mencionadas (pré-ordem, em-ordem, pós-ordem) são implementações do algoritmo de Busca em Profundidade (Depth-First Search - DFS). A forma mais intuitiva de implementar DFS é através de recursão, que é uma abordagem frequentemente útil para resolver problemas em árvores. É possível converter implementações recursivas de DFS em iterativas utilizando uma estrutura de pilha.
Busca em Largura (BFS)
A Busca em Largura (Breadth-First Search - BFS), também conhecida como travessia por níveis, visita os nós camada por camada, começando pela raiz (camada 0), e depois percorrendo os nós de cada camada subsequente da esquerda para a direita.
Exemplo de Construção e Travessia
Vamos considerar a construção de uma árvore binária a partir de uma representação serializada e suas travessias.
Travessia Pré-ordem com Serialização
A serialização em pré-ordem, usando um caractere especial (#) para representar nós nulos, permite reconstruir a árvore. Uma travessia pré-ordem pode produzir uma saída como: 3 1 # # 2 # # 5 6 # # 8 # # 7 # #.
#include <iostream>
#include <string>
#include <queue>
#include <vector>
// Caractere para representar nós nulos
const char NULL_NODE = '#';
struct TreeNode {
char value;
TreeNode* left;
TreeNode* right;
TreeNode() : left(nullptr), right(nullptr) {}
};
class BinaryTreeSerializer {
private:
TreeNode* root;
std::queue<char> dataQueue;
std::vector<TreeNode*> nodePool; // Gerencia a memória alocada para os nós
// Função recursiva para construir a árvore
void buildTreeRecursive(TreeNode*& node) {
if (dataQueue.empty()) return;
char currentChar = dataQueue.front();
dataQueue.pop();
if (currentChar == NULL_NODE) {
node = nullptr;
return;
}
node = allocateNode(); // Aloca um novo nó
node->value = currentChar;
buildTreeRecursive(node->left);
buildTreeRecursive(node->right);
}
// Função recursiva para travessia pré-ordem
void traversePreOrderRecursive(const TreeNode* node) {
if (node == nullptr) {
std::cout << NULL_NODE << " ";
return;
}
std::cout << node->value << " ";
traversePreOrderRecursive(node->left);
traversePreOrderRecursive(node->right);
}
// Aloca um nó e o adiciona à pool de memória
TreeNode* allocateNode() {
TreeNode* newNode = new TreeNode();
nodePool.push_back(newNode);
return newNode;
}
public:
// Construtor que inicializa a árvore com dados serializados
BinaryTreeSerializer(const std::string& serializedData) : root(nullptr) {
for (char c : serializedData) {
dataQueue.push(c);
}
}
// Método público para iniciar a construção da árvore
void constructTree() {
buildTreeRecursive(root);
}
// Método público para iniciar a travessia pré-ordem
void printPreOrder() {
traversePreOrderRecursive(root);
std::cout << std::endl;
}
// Destrutor para liberar a memória alocada
~BinaryTreeSerializer() {
for (TreeNode* node : nodePool) {
delete node;
}
}
};
int main() {
std::string serialized = "3 1 # # 2 # # 5 6 # # 8 # # 7 # #";
BinaryTreeSerializer tree(serialized);
tree.constructTree();
tree.printPreOrder(); // Saída esperada: 3 1 # # 2 # # 5 6 # # 8 # # 7 # #
return 0;
}
Outra forma de travessia é imprimir os caminhos que levam a cada nó folha. Para a mesma árvore, isso poderia resultar em algo como: [3 1] [3 2] [3 5 6 8] [3 5 7].
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <utility> // Para std::pair
// Caractere para representar nós nulos
const char NULL_NODE = '#';
struct TreeNode {
char value;
TreeNode* left;
TreeNode* right;
TreeNode() : left(nullptr), right(nullptr) {}
};
class PathTraversalTree {
private:
TreeNode* root;
std::queue<char> dataQueue;
std::vector<TreeNode*> nodePool; // Gerencia a memória alocada
std::vector<std::pair<char, int>> currentPath; // Armazena o caminho atual
// Função recursiva para construir a árvore
void buildTreeRecursive(TreeNode*& node) {
if (dataQueue.empty()) return;
char currentChar = dataQueue.front();
dataQueue.pop();
if (currentChar == NULL_NODE) {
node = nullptr;
return;
}
node = allocateNode();
node->value = currentChar;
buildTreeRecursive(node->left);
buildTreeRecursive(node->right);
}
// Função recursiva para travessia por caminho
void traversePathRecursive(const TreeNode* node) {
if (node == nullptr) {
return;
}
// Adiciona o nó atual ao caminho
currentPath.push_back({node->value, 1});
// Se for um nó folha, imprime o caminho
if (node->left == nullptr && node->right == nullptr) {
printCurrentPath();
} else {
// Se não for folha, incrementa a "referência" para os nós pais no caminho
incrementPathReferences();
}
// Continua a travessia recursiva
if (node->left != nullptr || node->right != nullptr) {
traversePathRecursive(node->left);
traversePathRecursive(node->right);
}
}
// Incrementa a contagem de referência para os nós no caminho atual
void incrementPathReferences() {
for (auto& pathNode : currentPath) {
pathNode.second++;
}
}
// Imprime o caminho atual formatado
void printCurrentPath() {
std::cout << "[";
auto it = currentPath.begin();
while (it != currentPath.end()) {
std::cout << it->first;
it->second--;
if (it->second == 0) {
it = currentPath.erase(it); // Remove o nó se a referência chegar a zero
continue;
}
std::cout << " "; // Espaço entre os elementos do caminho
++it;
}
std::cout << "] ";
}
// Aloca um nó e o adiciona à pool de memória
TreeNode* allocateNode() {
TreeNode* newNode = new TreeNode();
nodePool.push_back(newNode);
return newNode;
}
public:
// Construtor
PathTraversalTree(const std::string& serializedData) : root(nullptr) {
for (char c : serializedData) {
dataQueue.push(c);
}
}
// Método público para construir a árvore
void constructTree() {
buildTreeRecursive(root);
}
// Método público para iniciar a travessia por caminho
void printPaths() {
traversePathRecursive(root);
std::cout << std::endl;
}
// Destrutor
~PathTraversalTree() {
for (TreeNode* node : nodePool) {
delete node;
}
}
};
int main() {
std::string serialized = "31#2##568###7##"; // Sem espaços para corresponder ao exemplo de saída
PathTraversalTree tree(serialized);
tree.constructTree();
tree.printPaths(); // Saída esperada: [3 1 ] [3 2 ] [3 5 6 8 ] [3 5 7 ]
return 0;
}
O paradigma de Divisão e Conquista (Divide and Conquer) decompõe um problema em subproblemas menores, resolve-os recursivamente e, em seguida, combina suas soluções para resolver o problema original.
- Divisão: Quebrar o problema em subproblemas independentes de mesmo tipo.
- Conquista: Resolver os subproblemas recursivamente. Se os subproblemas forem pequenos o suficiente, resolvê-los diretamente.
- Combinação: Combinar as soluções dos subproblemas para obter a solução do problema original.
Exemplos clássicos incluem busca binária, multiplicação de matrizes grandes e algoritmos de ordenação como Merge Sort e Quick Sort.
Árvore de Busca Binária (BST)
Uma Árvore de Busca Binária (Binary Search Tree - BST) é um tipo especializado de árvore binária onde, para qualquer nó, todos os valores na sua subárvore esquerda são menores que o valer do nó, e todos os valores na sua subárvore direita são maiores.
Características e Desempenho da BST
Em uma BST balanceada, a altura é logarítmica em relação ao número de nós (O(log N)), o que resulta em operações de busca, inserção e remoção com complexidade O(log N). No entanto, se a BST degenerar em uma lista ligada (por exemplo, ao inserir elementos em ordem crescente), a complexidade das operações pode degradar para O(N).
Árvore Binária Balanceada
Uma árvore binária é considerada balanceada se, para cada nó, a diferença de altura entre suas subárvores esquerda e direita não exceder 1, e ambas as subárvores também forem balanceadas.
Uma abordagem eficiente para verificar o balanceamento de uma árvore é usar um algoritmo que retorna a altura de cada subárvore e, simultaneamente, verifica o balanceamento. Se uma subárvore não estiver balanceada, um valor especial (como -1) pode ser retornado para indicar essa condição. Essa técnica, aplicando um conceito similar à programação dinâmica, garante que cada nó seja visitado apenas uma vez, resultando em uma complexidade de tempo O(N).