Artigo original: Binary Search Trees: BST Explained with Examples
O que é uma árvore binária de busca?
Uma árvore é uma estrutura de dados composta de nós, com as seguintes características:
- Cada árvore tem um nó raiz em seu ponto superior (também conhecido como Nó Pai) contendo algum valor (com qualquer tipo de dados).
- O nó raiz tem zero ou mais "nós filhos".
- Cada nó filho tem zero ou mais "nós filhos" e assim por diante. Isso cria uma subárvore interna à árvore. Cada nó tem sua própria subárvore feita dos filhos e dos filhos dos filhos e assim por diante. Isso quer dizer que cada nó pode ser uma árvore por si só.
Uma árvore binária de busca (ou BST, do inglês binary search tree) tem, além disso, as duas características abaixo:
- Cada nó pode ter, no máximo, dois filhos.
- Para cada nó, os valores de seus descendentes da esquerda são inferiores ao valor do nó atual, que, por sua vez, é inferior aos nós descendentes da direita (se existirem).
As BST tem como base a ideia do algoritmo de busca binária, que permite uma procura, inserção e remoção rápidas dos nós. A maneira como estão configurados representa, em média, que cada comparação permite que as operações evitem passar por cerca de metade da árvore. Assim, cada procura, inserção ou remoção leva um tempo proporcional ao logaritmo do número de itens armazenados na árvore, O(log n). Entretanto, em algumas situações, podemos ter o pior dos casos, em que a árvore não está balanceada e a complexidade de tempo passa a ser O(n) para essas três funções. É por isso que árvores autobalanceadas (AVL, rubro-negra etc.) são muito mais eficazes que a BST básica.
Exemplo de cenário com o pior caso: isso pode acontecer quando você segue adicionando nós que são sempre maiores do que o nó anterior (seu pai). A mesma situação pode acontecer quando você sempre adiciona nós com valores inferiores aos de seus nós pai.
Operações básicas em uma BST
- Criar: cria uma árvore vazia.
- Inserir: insere um nó na árvore.
- Pesquisar: pesquisa por um nós na árvore.
- Excluir: exclui um nó da árvore.
- Travessia em ordem: faz a travessia da árvore na ordem.
- Travessia pré-ordem: faz a travessia da árvore pré-ordem.
- Travessia pós-ordem: faz a travessia da árvore pós-ordem.
Criar
Inicialmente, uma árvore vazia e sem nós é criada. A variável/identificador que deve apontar para o nó raiz é inicializado com o valor NULL.
Pesquisar
Sempre começamos a pesquisa em uma árvore pelo nó raiz e descemos a partir dele. Você compara os dados em cada nó com o valor que você está buscando. Se o nó comparado não corresponder, seguimos para o nó filho da direita ou da esquerda, dependendo do resultado da comparação seguinte: se o nó que buscamos for inferior àquele com o qual estamos comparando, seguimos para o filho da esquerda. Do contrário (se for maior) vamos para o filho da direita. Por quê? Porque a BST é estruturada (por definição) de modo que o filho da direita sempre seja maior que o pai e que o filho da esquerda sempre seja menor.
Busca em largura (BFS, do inglês breadth-first search)
A busca em largura é um algoritmo usado para fazer a travessia de uma BST. Ela começa no nó raiz e viaja de modo lateral (de um lado para outro), buscando pelo nó desejado. Este tipo de busca pode ser descrito como O(n), dado que cada nó é visitado uma vez e que o tamanho da árvore está correlacionado diretamente com o tamanho da busca.
Busca em profundidade (DFS, do inglês depth-first search)
Com a abordagem da busca em profundidade, começamos com o nó raiz e viajamos para baixo em uma única ramificação. Se o nó desejado for encontrado naquela ramificação, ótimo. Do contrário, continuamos subindo e pesquisando por nós não visitados. Esse tipo de busca também tem uma notação big O de O(n).
Inserir
É muito semelhante à função de pesquisar. Novamente, começamos do nó raiz da árvore e descemos de modo recursivo, procurando pelo local certo para inserir o novo nó, do mesmo modo que explicamos na função de pesquisar. Se um nó com o mesmo valor já existir na árvore, é possível escolher inserir a duplicata ou não. Algumas árvores permitem duplicatas, outras não. Isso depende da implementação.
Excluir
Há 3 casos que podem acontecer quando você tenta excluir um nós. Ele pode,
- não ter uma subárvore (não ter filhos): esse é o caso mais fácil. Você pode simplesmente excluir o nó, sem precisar realizar outras ações.
- Uma subárvore (um filho): você precisa se certificar de que, após o nó ser excluído, seu filho é, então, conectado ao pai do nó excluído.
- Duas subárvores (dois filhos): você precisa encontrar e substituir o nó que você quer excluir pelo seu sucessor em ordem (o nó mais à esquerda na subárvore à direita).
A complexidade de tempo para a criação de uma árvore é O(1). A complexidade de tempo para a pesquisa, inserção ou exclusão de um nó depende da altura h da árvore, portanto o pior caso é O(h) no caso de árvores que vão apenas em uma direção (esquerda ou direita).
Tipos especiais de árvore binária
- Heap
- Árvore rubro-negra
- Árvore B (B-Tree)
- Árvore play
- Árvore n-ária
- Trie (árvore de prefixos)
Tempo de execução
Estrutura de dados: BST (binary search tree)
- Desempenho no pior caso:
O(n) - Desempenho no melhor caso:
O(1) - Desempenho médio:
O(log n) - Complexidade de espaço no pior caso:
O(1)
Onde n é o número de nós da BST. O pior caso é O(n), já que a BST pode não estar balanceada.
Implementação da BST
Aqui temos uma definição para um nó da BST com alguns dados, referenciando seus nós filhos da esquerda e da direita.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
Operação de pesquisa
Sempre que um elemento precisa ser pesquisado, comece a pesquisa a partir do nó raiz. Depois, se os dados forem menores do que o valor-chave, pesquise o elemento na subárvore da esquerda. Do contrário, pesquise o elemento na subárvore da direita. Siga o mesmo algoritmo para cada nó.
struct node* search(int data){
struct node *current = root;
printf("Elementos visitados: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//vá para a subárvore da esquerda
if(current->data > data){
current = current->leftChild;
}//senão, vá para a subárvore da direita
else {
current = current->rightChild;
}
//não encontrado
if(current == NULL){
return NULL;
}
}
}
return current;
}
Operação de inserção
Sempre que um elemento precisar ser inserido, primeiro encontre seu local adequado. Comece pesquisando a partir do nó raiz. Então, se os dados forem menores que o valor-chave, pesquise o local vazio na subárvore da esquerda e insira o dado. Do contrário, pesquise o local vazio na subárvore da direita e insira o dado.
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//se a árvore estiver vazia
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//vá para a esquerda da árvore
if(data < parent->data) {
current = current->leftChild;
//insira à esquerda
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//vá para a direita da árvore
else {
current = current->rightChild;
//insira à direita
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Operação de exclusão
void deleteNode(struct node* root, int data){
if (root == NULL) root=tempnode;
if (data < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
As árvores binárias de busca (BSTs) também nos dão acesso rápido aos predecessores e sucessores.
Predecessor de um nó
Predecessores podem ser descritos como os nós que vêm logo antes do nó em que você se encontra no momento. Para encontrar o predecessor do nó atual, olhe para o maior nó folha/mais à direita na subárvore esquerda.
Sucessor de um nó
Sucessores podem ser descritos como os nós que vêm logo após o nó atual. Para encontrar o sucessor do nó atual, olhe para o menor nó folha/mais à esquerda na subárvore da direita.
Vamos examinar alguns procedimentos de operação em árvores
Como as árvores são definidas recursivamente, é muito comum escrevermos rotinas que operam nas árvores que sejam recursivas.
Por exemplo, se quisermos calcular a altura de uma árvore, ou seja, a altura de um nó raiz, podemos fazer isso recursivamente, percorrendo a árvore. Podemos dizer assim:
- Se tivermos uma árvore vazia, sua altura é 0.
- Do contrário, estamos a 1 mais a maior altura entre a da árvore filha à esquerda e a da árvore filha à direita.
- Se olharmos para uma folha, por exemplo, essa altura seria 1, pois a altura do filho à esquerda é 0, e a altura do filho da direita também é 0. Assim, como o máximo dentre os dois é 0, então 1 mais 0 = 1.
Algoritmo da altura - Height(tree)
if tree = nil:
return 0
return 1 + Max(Height(tree.left),Height(tree.right))
Este é o código em C++
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
int rDepth = maxDepth(node->right);
int lDepth = maxDepth(node->left);
if (lDepth > rDepth)
{
return(lDepth+1);
}
else
{
return(rDepth+1);
}
}
}
Também podemos calcular o tamanho de uma árvore, que é o seu número de nós.
- Mais uma vez, se tivermos uma árvore vazia, temos 0 nós.
- Do contrário, temos o número de nós no filho à esquerda mais 1 mais o número de nós no filho à direita. Assim 1 mais o tamanho da árvore da esquerda mais o tamanho da árvore da direita.
Algoritmo do tamanho - Size(tree)
if tree = nil
return 0
return 1 + Size(tree.left) + Size(tree.right)
Este é o código em C++
int treeSize(struct node* node)
{
if (node==NULL)
return 0;
else
return 1+(treeSize(node->left) + treeSize(node->right));
}
Travessias
Há 3 tipos de travessias que são feitas tipicamente em uma árvore binária de busca. Todas elas têm um modo bastante comum de percorrer os nós de uma árvore.
Em ordem (in-order traversal)
Essa travessia primeiro percorre a subárvore da esquerda do nó raiz, acessa o nó atual, seguido da subárvore da direita do nó atual. O código abaixo representa o caso de base, também, que diz que uma árvore vazia também é uma árvore binária de busca.
void inOrder(struct node* root) {
// Caso de base
if (root == null) {
return;
}
// Percorre primeiro a subárvore da esquerda.
inOrder(root.left);
// Imprime o valor do nó atual.
printf("%d ", root.data);
// Percorre em seguida a subárvore da direita.
inOrder(root.right);
}
Pré-ordem (pre-order traversal)
Essa travessia primeiro acessa o valor do nó atual, faz a travessia pela subárvore da esquerda e, depois, pela subárvore da direita, respectivamente.
void preOrder(struct node* root) {
if (root == null) {
return;
}
// Imprime o valor do nó atual.
printf("%d ", root.data);
// Percorre a subárvore da esquerda.
preOrder(root.left);
// Percorre a subárvore da direita.
preOrder(root.right);
}
Pós-ordem (post-order traversal)
Essa travessia coloca o valor do nó raiz no fim, percorrendo primeiro a subárvore da esquerda e depois a da direita. A ordem relativa das subárvores da esquerda e da direita permanece a mesma. Somente a posição do nó raiz muda em relação às travessias anteriores.
void postOrder(struct node* root) {
if (root == null) {
return;
}
// Percorre primeiro a subárvore da esquerda.
postOrder(root.left);
// Percorre em seguida a subárvore da direita.
postOrder(root.right);
// Imprime o valor do nó atual.
printf("%d ", root.data);
}
Vídeos do freeCodeCamp relevantes no canal do YouTube
Binary Search Tree: Traversal and Height (Árvore binária de busca: travessia e altura)
A seguir, temos tipos comuns de árvores binárias:
Árvore totalmente binária/árvore binária estrita: uma árvore é totalmente binária ou estrita se todo nó tiver exatamente 0 ou 2 nós filhos.
18
/ \
/ \
15 30
/ \ / \
40 50 100 40
Na árvore totalmente binária, o número de nós folha é igual ao número de nós internos mais um.
Árvore binária completa: uma árvore binária é completa se todos os níveis estiverem completamente preenchidos, exceto, possivelmente, o último nível e se o último nível tiver todas as chaves o mais à esquerda possível.
18
/ \
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Árvore binária perfeita: uma árvore binária é perfeita se todos os nós internos tiverem dois nós filhos e se todas as folhas estiverem no mesmo nível.
18
/ \
/ \
15 30
/ \ / \
40 50 100 40
Aumentando uma BST
Às vezes, precisamos armazenar algumas informações adicionais com as estruturas de dados tradicionais para tornar nossas tarefas mais fáceis. Por exemplo, considere um cenário onde você deve encontrar o i-ésimo menor número de um conjunto. É possível usar a força bruta aqui, mas queremos reduzir a complexidade do problema para O(lg n) aumentando uma árvore rubro-negra ou qualquer árvore autobalanceada (onde n é o número de elementos do conjunto). Também podemos calcular a classificação de qualquer elemento no tempo O(lg n). Vamos considerar um caso onde aumentamos uma árvore rubro-negra para que armazene as informações necessárias. Além dos atributos normais, podemos armazenar um certo número de nós internos na subárvore com a raiz x (tamanho da subárvore com raiz em x incluindo o próprio nó). Considere x como sendo qualquer nó arbitrário de uma árvore.
x.size = x.left.size + x.right.size + 1
Quando aumentamos a árvore, levamos em consideração que devemos ser capazes de manter as informações adicionadas, bem como fazer outras operações, como inserção, exclusão e atualização em um tempo O(lg n).
Assim, sabemos que o valor de x.left.size (subárvore do lado esquerdo de x) nos dará o número de nós que vêm após x na travessia em ordem da árvore. Portanto, x.left.size + 1 é a classificação de x dentro da subárvore com raiz em x.