# Árvore binária de busca

Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação).
O objetivo desta árvore é estruturar os dados de forma a permitir busca binária.

## Conceitos básicos
### Definição

Seja S = {s$_1$, s$_2$, ..., s$_n$} um conjunto de chaves tais que s$_1$ < s$_2$ ... s$_n$. Seja k um valor dados. Deseja-se verificar se k $\in$ S e identificar o índice i tal que k = s$_i$.
A Árvore Binária de Busca (ABB) resolve os problemas propostos. A figura ilustra uma ABB.
Uma ABB é uma árvore binária rotulada T com as seguintes propriedades:
* T possui n nós. Cada nó u armazena uma chave distinta s$_j$ $\in$ S e tem como rótulo o valor r(u) = s$_j$.
* Para cada nó v de T r(v$_1$) < r(v) e r(v$_2$) > r(v), onde v$_1$ pertence à subárvore esquerda de v e v$_2$ pertence à subárvore direita de v.
Dado o conjunto S com mais de um elemento, existem várias ABB que resolvem o problema.

### Elementos

* Nós - são todos os itens guardados na árvore
* Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
* Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
* Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
* Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)

### Complexidade

A complexidade das operações sobre ABB depende diretamente da altura da árvore.
Uma árvore binária de busca com chaves aleatórias uniformemente distribuídas tem altura O(log n).
No pior caso, uma ABB poderá ter altura O(n). Neste caso a árvore é chamada de árvore zig-zag e corresponde a uma degeneração da árvore em lista encadeada.
Em função da observação anterior, a árvore binária de busca é de pouca utilidade para ser aplicada em problemas de busca em geral. Daí o interesse em árvores balanceadas, cuja altura seja O(log n) no pior caso

## Operações
### Busca

A busca em uma árvore binária por um valor específico pode ser um processo recursivo ou iterativo. Será apresentado um método recursivo.
A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Similarmente, se o valor é maior do que a raiz, a busca segue pela subárvore direita. Esse processo é repetido até o valor ser encontrado ou a subárvore ser nula (vazia). Se o valor não for encontrado até a busca chegar na subárvore nula, então o valor não deve estar presente na árvore.
Segue abaixo o algoritmo de busca implementado na linguagem Python:
Essa operação poderá ser O(log n) em algumas situações, mas necessita O(n) de tempo no pior caso, quando a árvore assumir a forma de lista ligada (árvore ziig-zag).

### Inserção

A inserção começa com uma busca, procurando pelo valor, mas se não for encontrado, procuram-se as subárvores da esquerda ou direita, como na busca. Eventualmente, alcança-se a folha, inserindo-se então o valor nesta posição. Ou seja, a raiz é examinada e introduz-se um nó novo na subárvore da esquerda se o valor novo for menor do que a raiz, ou na subárvore da direita se o valor novo for maior do que a raiz. Abaixo, um algoritmo de inserção em Python:
Esta operação requer O (log n) vezes para o caso médio e necessita de O (n) no pior caso. A fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menor que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor.

### Remoção

A exclusão de um nó é um processo mais complexo. Para excluir um nó de uma árvore binária de busca, há de se considerar três casos distintos para a exclusão:

#### Remoção na folha

A exclusão na folha é a mais simples, basta removê-lo da árvore.

#### Remoção de nó com um filho

Excluindo-o, o filho sobe para a posição do pai.

#### Remoção de nó com dois filhos

Neste caso, pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais à esquerda da subárvore direita) ou pelo valor antecessor (o nó mais à direita da subárvore esquerda), removendo-se aí o nó sucessor (ou antecessor).
No exemplo acima, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 35 (nó mais à esquerda da sua sub-árvore direita). Assim sendo, na exclusão, o valor 35 será promovido no lugar do nó a ser excluído, enquanto a sua sub-árvore (direita) será promovida para sub-árvore esquerda do 40, como pode ser visto na figura.
Exemplo de algoritmo de exclusão em Python:
Embora esta operação não percorra sempre a árvore até uma folha, esta é sempre uma possibilidade; assim, no pior caso, requer o tempo proporcional à altura da árvore, visitando-se cada nó somente uma única vez.

## Aplicações
### Percursos em ABB

Em uma árvore binária de busca podem-se fazer os três percursos que se fazem para qualquer árvore binária (percursos em inordem, pré-ordem e pós-ordem). É interessante notar que, quando se faz um percurso em ordem em uma árvore binária de busca, os valores dos nós aparecem em ordem crescente. A operação "Percorre" tem como objetivo percorrer a árvore numa dada ordem, enumerando os seus nós. Quando um nó é enumerado, diz-se que ele foi "visitado".
Pré-ordem (ou profundidade):
* Visita a raiz
* Percorre a subárvore esquerda em pré-ordem
* Percorre a subárvore direita em pré-ordem
Ordem Simétrica:
* Percorre a subárvore esquerda em ordem simétrica
* Visita a raiz
* Percorre a subárvore direita em ordem simétrica
Pós-ordem:
* Percorre a subárvore esquerda em pós-ordem
* Percorre a subárvore direita em pós-ordem
* Visita a raiz
Usando a ABB acima, os resultados serão os seguintes:
Pré-ordem => 8, 3, 1, 6, 4, 7, 10, 14, 13
Ordem simétrica => 1, 3, 4, 6, 7, 8, 10, 13, 14 (chaves ordenadas)
Pós-ordem => 1, 4, 7, 6, 3, 13, 14, 10, 8

### Ordenação

Uma árvore binária de busca pode ser usada para ordenação de chaves. Para fazer isto, basta inserir todos os valores desejados na ABB e executar o percurso em ordem simétrica.
Criar ABB tem complexidade O(n$^2$) no pior caso. A geração de um vetor de chaves ordenadas tem complexidade O(n). O algoritmo de ordenação terá complexidade final O(n$^2$) no pior caso.
Cabe observar que há algoritmos de ordenação dedicados com complexidade O(n.log n), com desempenho superior ao proposto neste tópico.