Árvores binárias de pesquisa

Considerem o seguinte problema: é dado um conjunto de $N$ números. Dão-nos agora $Q$ números e perguntam-nos quais deles estão no conjunto inicial. Fácil, não? Já sabemos ordenar e fazer uma pesquisa binária, basta-nos ordenar o conjunto inicial e para cada um dos $Q$ números efetuamos uma pesquisa binária. Mas e se agora para alguns dos $Q$ números queremos saber se estão no conjunto e para os restantes queremos introduzi-los no conjunto? Já não é tão fácil..

Para este tipo de problemas, utilizamos uma estrutura de dados para guardar, inserir e remover elementos, chamada árvore binária de pesquisa. Vamos ver um pouco mais sobre ela.

Como acabaram de ler, as árvores binárias de pesquisa têm a propriedade de que todos os nós à direita de um nó têm um valor maior que o próprio e todos os nós à esquerda têm um valor menor que o próprio. Esta propriedade é útil pois permite-nos fazer pesquisa de um elemento de um conjunto guardado numa árvore em complexidade $O(h)$, onde $h$ é a altura da árvore. Se os dados forem aleatórios, então $h$ é da ordem de $\log(N)$, que seria uma grande melhoria em relação à solução mais bruta.

* Balanceamento

Para manter a altura da árvore na ordem de $\log(N)$, é necessário que a árvore tenha uma forma semelhante a uma árvore balanceada, isto é, com altura mínima possível para aquele número de nós (cerca de $\log N)$). Para isto existem vários métodos, um deles descrito no artigo seguinte:

Outro método mais lento mas mais simples de utilizar é a reconstrução da árvore de $k$ em $k$ passos. Se tivermos um conjunto de elementos e quisermos construir uma árvore balanceada com eles, escolhemos para raiz da árvore a mediana dos elementos e construimos a sub-árvore à esquerda e à direita com a metade correspondente do conjunto de elementos, utilizando o mesmo método (de escolher sempre a mediana). Se tivermos $N$ inserções, a complexidade no pior caso é $O(Nk + N / k)$, sendo $Nk$ correspondente às $N$ inserções e o resto às $N / k$ reconstruções. Podemos observar que o melhor $k$ a escolher é $\sqrt(N)$ sendo a complexidade final $O(N\sqrt(N))$.

Na prática é raro termos que implementar uma árvore AVL num concurso. Como veremos no próximo artigo, existem várias implementações disponíveis nas linguagens mais comuns em concursos. Além disso, quando precisamos mesmo de implementar uma árvore binária balanceada para resolver um problema especial, a estrutura mais utilizada em concursos é uma treap, que iremos abordar num futuro artigo do loop.