Inserindo em uma BST
Construa uma árvore binária de busca.
Inserindo em uma BST é uma aula grátis de C Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
A regra de ordenação da BST
Uma árvore de busca binária (BST) é uma árvore binária com uma regra adicional: para cada nó, todos os valores da subárvore esquerda são menores, e todos os valores da subárvore direita são maiores.
É essa ordenação que permite pesquisar, inserir e excluir em um tempo proporcional à altura da árvore.
Onde um valor pertence
Para inserir, começamos pela raiz e fazemos uma comparação. Se o novo valor for menor, vamos para a esquerda; se for maior, vamos para a direita.
Repetimos o processo até alcançar um espaço vazio (NULL), que é exatamente onde o novo nó deve ficar.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/O auxiliar create_node
A inserção cria novos nós folha, portanto reutilizamos um construtor que aloca e inicializa um nó.
Ambos os filhos começam como NULL, pois um nó recém-inserido é sempre uma folha.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}Inserção recursiva
A forma mais simples de inserir é recursiva e retorna a raiz da subárvore, que pode ser nova.
Se a subárvore estiver vazia, retornamos um nó novo. Caso contrário, fazemos a recursão para a esquerda ou para a direita, reconectamos o resultado e então retornamos a raiz inalterada.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}Por que retornar a raiz
Retornar a raiz da subárvore permite que o pai reconecte o link em uma única linha: root->left = insert(root->left, v).
Quando a subárvore estava vazia, o novo nó retornado se torna o filho. Quando não estava, a mesma raiz é retornada e o link permanece inalterado.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);Tratando valores duplicados
As BSTs reais precisam decidir o que fazer com valores iguais. Uma escolha comum é ignorar duplicatas, como nossa insert faz ao não ter um ramo para o caso de igualdade.
As alternativas incluem manter uma contagem por nó ou sempre enviar as duplicatas para um dos lados.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */Construindo uma BST
Inserir uma sequência de valores produz uma árvore cujo formato depende da ordem de inserção.
Aqui inserimos vários números e imprimimos os filhos imediatos da raiz para confirmar que a regra de ordenação é respeitada.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return create_node(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}Uma inserção iterativa
Também é possível inserir sem recursão. Percorremos a árvore com um ponteiro, mantendo o pai em uma variável, até encontrar um espaço vazio.
Então conectamos o novo nó ao lado correto desse pai.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}A ordem de inserção define o formato da árvore
Inserir 1,2,3,4,5 em ordem crescente produz uma árvore degenerada que se parece com uma lista encadeada, com altura igual à quantidade de nós.
Inserir em uma ordem equilibrada mantém a altura próxima de log(n). O equilíbrio afeta diretamente a velocidade da pesquisa.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/Custo da inserção
Cada inserção percorre um caminho da raiz até uma folha, portanto realiza um trabalho proporcional à altura da árvore.
Em uma árvore equilibrada, isso corresponde a aproximadamente log(n) comparações; em uma árvore degenerada, pode chegar a n. É por isso que existem árvores autobalanceadas.
Demonstração completa de inserção
Este programa insere valores e depois conta os nós para confirmar que cinco valores distintos foram armazenados e que um duplicado foi ignorado.
O duplicado 10 não aumenta a contagem porque insert descarta valores iguais.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}Verificação rápida
Raciocine sobre o comportamento da inserção.
Recapitulação
A inserção em uma BST compara o novo valor com cada nó, seguindo para a esquerda quando ele é menor e para a direita quando é maior, até encontrar uma posição vazia.
A forma recursiva retorna a raiz da subárvore para que o nó pai possa religar os ponteiros corretamente. O custo da inserção cresce com a altura da árvore, portanto a ordem de inserção é importante.
Perguntas Frequentes
A aula “Inserindo em uma BST” é grátis?
Sim — o texto completo de “Inserindo em uma BST” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Inserindo em uma BST”?
Construa uma árvore binária de busca. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Inserindo em uma BST”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Nós e estrutura de árvores
- Inserindo em uma BST
- Percursos
- Pesquisando e liberando