Árvore Binária

Uma árvore binária é uma estrutura de dados baseada em nós, semelhante às listas ligadas no sentido de que os elementos não são armazenados em posições contíguas de memória, mas conectados por referências.

Cada nó da árvore pode se conectar a outros dois nós, formando uma estrutura hierárquica.

Essa organização permite representar dados de forma eficiente quando precisamos manter ordem e realizar operações frequentes de busca, inserção e remoção.

Árvores binárias surgem como uma solução interessante para um problema comum:

• arrays ordenados permitem busca rápida, mas inserções e deleções são custosas
• hash tables possuem operações muito rápidas, mas não mantêm ordem

As árvores binárias oferecem um equilíbrio: mantêm os dados ordenados e ainda permitem operações eficientes.

Uma árvore binária é composta por nós conectados entre si.

Cada nó possui três componentes principais:

• valor → dado armazenado no nó
• left child → referência para o nó à esquerda
• right child → referência para o nó à direita

Alguns termos importantes:

Exemplo:

Nesse exemplo:

• 50 é a raiz
• 25 e 75 são filhos de 50
• 10, 33 e 90 são folhas

Em uma Binary Search Tree (BST) existe uma regra fundamental:

Essa regra é o que permite que operações de busca sejam realizadas de forma eficiente.

A busca em uma árvore binária começa sempre pela raiz.

O algoritmo segue os seguintes passos:

1. Observe o valor do nó atual.
2. Se ele for o valor procurado, a busca termina.
3. Se o valor procurado for menor, vá para o filho esquerdo.
4. Se for maior, vá para o filho direito.

Exemplo:

A cada passo descartamos metade das possibilidades.

Complexidade média: O(log N)

Isso é semelhante à eficiência da busca binária em arrays ordenados.

Inserir um elemento em uma árvore binária segue a mesma lógica da busca.

Primeiro encontramos o local correto onde o novo valor deve ficar.

Exemplo: inserir 30

Como a inserção é fundamentalmente uma busca seguida de um único ajuste, a complexidade é:

Complexidade: O(log N)

Isso é significativamente melhor do que arrays ordenados, onde inserções custam O(N) devido ao deslocamento de elementos.

Remover um nó de uma árvore binária pode ocorrer em três cenários.

Se o nó não possui filhos, basta removê-lo.

Se o nó possui apenas um filho, removemos o nó e conectamos o filho diretamente ao seu pai.

Esse é o caso mais complexo.

O procedimento é:

1. Encontrar o sucessor do nó.
2. Substituir o valor do nó removido por esse sucessor.
3. Remover o sucessor da posição original.

O sucessor é o menor valor da subárvore direita.

A eficiência das árvores binárias depende da sua forma.

Uma árvore balanceada distribui os nós de maneira uniforme.

Altura da árvore ≈ log N

Operações:

• busca → O(log N)
• inserção → O(log N)
• deleção → O(log N)

Se os valores forem inseridos em ordem crescente, a árvore pode degenerar em uma lista.

Nesse cenário:

• busca → O(N)
• inserção → O(N)
• deleção → O(N)

Ou seja, a árvore perde sua eficiência.

O processo de visitar todos os nós de uma estrutura de dados é chamado de traversal.

Existem diferentes maneiras de percorrer uma árvore:

• Preorder — raiz, esquerda, direita
• Inorder — esquerda, raiz, direita
• Postorder — esquerda, direita, raiz

Esses percursos são usados em diversos algoritmos e aplicações.

Árvores binárias são apenas uma das muitas estruturas baseadas nesse conceito.

Outras variações incluem:

• Heaps
• B-Trees
• Red-Black Trees
• 2-3-4 Trees

Cada uma é otimizada para cenários específicos, especialmente quando lidamos com grandes volumes de dados ou sistemas complexos.