Árvore binÁria de pesquisa

a busca, a inserção ordenada e a remoção são bem mais rápida.

tipo, essa arvore binaria onde a chave é igual ao valor dos nós:

9
                    
                   5             15
              
             4         6

e o array ordenado: 4 5 6 9 15

Para inserir o elemento 16 na árvore vc faz 2 comparações uma com o 9 e outra com o 15.

Para inserir no array vc compara com todos os elementos e insere no final do array.

enquanto a lista encadeada tem alguma vantagem ou desvantagem…?

árvore binária de busca (ou pesquisa) é uma árvore ordenada cujos nós a esquerda de um nó pai são menores que ele, e cujos nós a direita de um nó pai são maiores que ele. Por exemplo:

1
       0                 2

A vantagem da árvore binária de busca é que, por ela estar ordenada, a busca consiste em percorrer apenas uma subárvore até encontrar o elemento ou até atingir um nó folha da subárvore, o que deixa sua busca em ordem logarítmica natural (log2 n). Arrays são bem mais simples de serem implementados e usados, possuem tamanho fixo, o que exige previsão de memória em seu uso… Arvores podem ser implementadas dinamicamente (mas não só) e possuem eficiencia relativamente limitada, em comparação a arrays. Desde que a arvore se mantenha balanceada, isto é, que o tamanho da subarvore esq n ultrapasse a da direita em 1, ou vice versa, atinge-se a chama perfomance otimizada ou ótima.
Tentei dar uma resumida do q eu lembro pq estudei isso ha um tempo
Desculpe-me se disse alguma besteira, mas pesquise no google ou wikipedia para procurar saber mais sobre arvores, existem otimas apostilas de universidades na net
[]'s

Boa tarde!

Sobre árvores de pesquisa, a wikipedia tem um material razoável. Procure por “Lista de estruturas de dados”, “Estrutura de dados”, “Árvore binária”, “Árvore de busca binária” ou em inglês por seus correspondentes.

Até!