Implementar, em linguagem C, o algoritmo de busca em uma árvore digital binária.
Passo 1
Beleza! O enunciado pede para a gente “Implementar, em linguagem C, o algoritmo de busca em uma árvore digital binária.” Isso cai na matéria de estruturas de dados (mais especificamente em tries binárias ou árvores digitais), e a gente vai usar:
- Conceito de árvore (ponteiros para filhos esquerdo e direito)
- Operações bit a bit em C para separar cada bit da chave
- Laços para percorrer do bit mais significativo (MSB) até o menos significativo (LSB)
Passo 2
Vamos começar definindo a estrutura do nó. Aqui cada nó tem dois ponteiros (filho 0 e filho 1) e uma flag que indica se ali terminou uma chave inserida.
#define BITS_KEY 32 // assumindo chave de 32 bits
typedef struct TrieNode {
int isEnd; // 1 se esse nó marca fim de uma chave válida
struct TrieNode* child[2]; // child[0] = ramo para bit 0, child[1] = ramo para bit 1
} TrieNode;
Passo 3
Agora a função de busca. A ideia é: dado um ponteiro
root
e uma chave key
, a gente percorre bit a bit, do MSB (bit 31) até o LSB (bit 0). Em cada nível, escolhe child[bit]
. Se em algum momento não existir nó, concluímos que a chave não está na árvore.TrieNode* search(TrieNode* root, unsigned int key) {
TrieNode* curr = root;
// percorre do bit 31 até o bit 0
for (int i = BITS_KEY-1; i >= 0; i--) {
if (!curr) return NULL; // ramo não existe → não achou
int bit = (key >> i) & 1; // extrai o i-ésimo bit: (key >> i) & 1
curr = curr->child[bit];
}
// se terminou os bits e curr não é NULL, checa se é fim de chave
if (curr && curr->isEnd)
return curr; // achou a chave
return NULL; // percorreu tudo mas não era fim de chave
}
Passo 4
Teoria em jogo:
- Em uma árvore digital binária (ou trie binária), cada nível corresponde a um bit da chave.
- Você decide ramificar para a esquerda (bit 0) ou direita (bit 1).
- A operação
desloca os bits de key
para a direita emi
posições, depois faz AND com 1 para isolar só aquele bit. - A busca leva tempo
, com sendo número de bits da chave (aqui 32).
Passo 5
Se quiser usar na prática, basta chamar
search(root, minhaChave)
. Se o retorno for NULL
, não existe; senão, você recebe o ponteiro do nó onde isEnd == 1
.Resposta
#include <stdio.h>
#include <stdlib.h>
#define BITS_KEY 32
typedef struct TrieNode {
int isEnd;
struct TrieNode* child[2];
} TrieNode;
// cria nó novo
TrieNode* newNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEnd = 0;
node->child[0] = node->child[1] = NULL;
return node;
}
// busca na trie binária
TrieNode* search(TrieNode* root, unsigned int key) {
TrieNode* curr = root;
for (int i = BITS_KEY - 1; i >= 0; i--) {
if (!curr) return NULL;
int bit = (key >> i) & 1;
curr = curr->child[bit];
}
if (curr && curr->isEnd)
return curr;
return NULL;
}
// exemplo de inserção só pra testar busca
void insert(TrieNode* root, unsigned int key) {
TrieNode* curr = root;
for (int i = BITS_KEY - 1; i >= 0; i--) {
int bit = (key >> i) & 1;
if (!curr->child[bit])
curr->child[bit] = newNode();
curr = curr->child[bit];
}
curr->isEnd = 1;
}
int main() {
TrieNode* root = newNode();
insert(root, 42);
insert(root, 100);
unsigned int x = 42;
if (search(root, x))
printf("Chave %u encontrada!\n", x);
else
printf("Chave %u nao existe.\n", x);
return 0;
}