Árvores binárias de pesquisa **new** 2004/09/22 09:32:10.476 GMT-5 2004/09/22 09:35:22.851 GMT-5 Andre Campos andre@dimap.ufrn.br Andre Campos andre@dimap.ufrn.br árvores binárias árvores de pesquisa Este módulo apresenta os conceitos iniciais de árvores binárias de pesquisa. Ele inclui algoritmos de busca, inserção e remoção.

Á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 .

para todo vértice além-mar faça com

Responda a pergunta do exercício para melhor fixar seu conteúdo. Árvore binária estrita Árvore binária onde cada nó não-folha possui os dois filhos André Campos Algoritmos e estruturas de dados em Java 2002