`Conceito`

Em ciência da computação, árvores são estruturas de dados hierárquicas formadas por nós (nodes) conectados, onde cada nó pode ter vários nós filhos, mas apenas um nó pai (exceto a raiz, que não possui pai). A árvore começa por um nó raiz e se ramifica em subárvores, organizando dados de forma que facilite operações como busca, inserção, remoção e ordenação. Elas são amplamente utilizadas em algoritmos, bancos de dados, sistemas de arquivos, linguagens de programação e inteligência artificial. Existem diversos tipos de árvores, como árvores binárias, árvores balanceadas (AVL, Red-Black), árvores B, Trie, entre outras, cada uma adaptada para casos específicos de uso.

</aside>

Árvores são estruturas adequadas para representar hierarquias

Exemplos </aside>

Um caminho na árvore T é uma sequência v1, v2, ...., vn de vértices, onde n ≥ 1, tal que Vi é pai de Vi+1.

Um caminho composto de uma sequência v1, v2, ...., vnde vértices tem comprimento n-1.

Sempre existe um único caminho entre um vértice e qualquer um de seus descendentes.

Exemplos </aside>

Grau ou grau de saída de um nó: número de filhos do nó.

Nível de um nó: é a distância do nó até a raiz.

Altura ou profundidade de um nó v: é o número de nós do maior caminho de v até um descendente próprio.

`Observações`

A altura de uma árvore com apenas um nó é zero.
Altura de uma árvore vazia é -1.
O último nível da árvore é o nível h, sendo h a altura da árvore. </aside>

Dependendo do número máximo de filhos que cada nó da árvore pode ter, a árvore pode ter um nome específico:

Árvore binária: cada nó pode ter de 0, 1 ou 2 filhos.
Árvore ternária: cada nó pode ter 0, 1, 2 ou 3 filhos.
Árvore quaternária: cada nó pode ter 0, 1, 2, 3 ou 4 filhos.

De um modo geral, chamamos de árvore n-ária (n ≥ 2) aquela em que cada nó pode ter de 0 a n filhos.

</aside>

Uma árvore é completa quando os nós com alguma subárvore vazia estão no último ou penúltimo nível da árvore

Exemplo em uma árvore binária </aside>

Uma árvore é cheia quando todos os seus nós internos tem o número máximo de filhos e todas as folhas estão no mesmo nível.

Exemplo </aside>

`Árvores Binárias`

A representação de árvores binárias é simples, pois cada nó pode ter, no máximo, dois filhos (duas subárvores).

Exemplo em Linguagem C </aside>

É possível percorrer todos os nós de uma árvore binária usando três estratégias:

Em ordem: percorre recursivamente a subárvore esquerda, visita a raiz e, por fim, percorre recursivamente a subárvore direita.
Pré-ordem: visita a raiz, percorre recursivamente a subárvore esquerda e, por fim, percorre recursivamente a subárvore direita.
Pós-ordem: percorre recursivamente a subárvore esquerda, percorre recursivamente a subárvore direita e, por fim, visita a raiz.

Observação: o termo "visita a raiz" significa que o valor contido naquele nó será processado. Ele pode, por exemplo, ser simplesmente impresso.

</aside>

`Binárias de Busca (ABB)`

Todos os elementos da subárvore à esquerda são menores que o nó raiz e todos os elementos da subárvore à direita são maiores que o nó raiz.

Exemplo

No exemplo da ABB a cima, todos os elementos na subárvore à esquerda de 8 são menores que ele e todos os elementos na subárvore à direita de 8 são maiores que ele.

</aside>

`Busca`

A busca de um elemento em uma ABB segue essa lógica:

Se o nó tem o valor procurado então retorna o nó.
Se o valor procurado é menor que a raiz então busca na subárvore à esquerda.
Se o valor procurado é maior que a raiz então busca na subárvore à direita. </aside>

Outra propriedade interessante da ABB é o cálculo do menor e do maior elemento:

Menor elemento: a partir da raiz, caminhar sempre para o nó mais à esquerda. O último nó à esquerda é o que contém o menor elemento

Exemplo

Maior elemento: a partir da raiz, caminhar sempre para o nó mais à direita. O último nó à direita é o que contém o maior elemento.

Exemplo </aside>

`Inserção`

A inserção de um novo elemento em uma ABB segue a mesma lógica da busca:

Se já existe um nó com o valor a ser inserido então não insere de novo.
Se o valor a ser inserido é menor que a raiz então insere na subárvore à esquerda.
Se o valor a ser inserido é maior que a raiz então insere na subárvore à direita </aside>

`Exclusão`

A exclusão em Árvores Binárias de Busca não são tão triviais quanto a inserção ou busca, pois é preciso preservar suas propriedades.

Para removermos um nó X de uma Árvore Binária de Busca preservando suas propriedades, precisamos considerar três casos:

</aside>