Árvores binárias de pesquisa

Árvores de pesquisa

Ah! este parágrafo é necessário para que a seção tenha algo a dizer. Vejam! e a fonte é diferente!

Suponha que você tenha um conjunto de elementos a armazenar no seu computador, de forma que possa realizar inúmeras buscas sobre esses elementos. Suponha agora que você utilize, como estrutura de dados para armazenar esses elementos, uma lista encadeada. Como vocês devem lembrar, a complexidade de busca em uma lista encadeada é (no pior caso) O(n), onde n é o número de elementos da lista. Isso ocorre porque precisamos percorrer a lista, no pior caso (caso onde o elemento a ser procurado se encontra no final da lista), do início (cabeça da lista) até o final. E se pudéssemos dar “saltos” nessa procura?

Claro que podemos dar “saltos” em uma procura. Alias, essa é a forma natural de otimizar processos. Para melhor visualizar esse processo, imagine uma busca de um número no intervalo de 0 a 100. Ao invés de iniciar sua busca no 0 e se estender até o 100, você pode testar o médio, 50, e verificar se o número a ser encontrado é maior ou menor. Se for menor, podemos então desprezar todos os números acima de 50 e recomeçar a busca no intervalo de 0 a 50. Esse procedimento deverá se repetir até que o número correspondente seja encontrado. Esse procedimento gerou implicitamente uma árvore de busca, conforme ilustrado na figura .

Responda a pergunta do exercício para melhor fixar seu conteúdo.