Trabalho sobre semicondutores

8.2.1. Árvores (binárias) de Busca
Árvores (binárias) são muito utilizadas para se representar uma grande conjunto de dados onde se deseja encontrar um elemento de acordo com a sua chave.
Definição: Árvore Binária de Busca (Niklaus Wirth):

Uma que árvore se encontra organizada de tal forma que, para cada nodo ti, todas as chaves (info) da subárvore à esquerda de ti são menores que (ou iguais a) ti e à direita são maiores que ti.
Termo em Inglês: Search Tree
Características de Árvores de Busca
Em uma árvore de busca é possível encontrar-se qualquer chave existente descendo-se a árvore sempre à esquerda toda vez que a chave procurada for menor do que a chave do nodo visitado e sempre à direita toda vez que for maior.
A escolha da direção de busca só depende da chave que se procura e da chave que o nodo atual possui.
A busca de um elemento em uma árvore balanceada com n elementos toma tempo médio < log(n), tendo a busca então O(log n).
Graças à estrutura de árvore a busca poderá ser feita com apenas log(n) comparações de elementos.
Exemplo de Árvore de Busca Binária
Busca em
Árvores
Considerando-se a estrutura de ados da aula passada, temos como algoritmo de busca: nodo *localize ( chave : info, ptr : *nodo) início enquanto (ptr ~= nulo) e (ptr->info ~= chave) faça se (ptr->info < chave) então ptr dir; senão ptr esq; fim se fim enquanto retorne ptr; fim localize
Exercício
Construção: Inserção simples em árvore binária inserção ( chave : info, ptr : *nodo) oNovo : *nodo; início se (chave < ptr->info) então se (ptr->esq = nulo) então oNovo info esq dir esq dir = nulo) então oNovo info esq dir dir dir ); fim se fim se fim se fim inserção
Exercício
Exemplo: Inserção de um elemento com chave 14

Eliminação em uma árvore de busca binária
A eliminação é mais complexa do que a inserção
A razão básica é que a característica organizacional da árvore não deve ser quebrada:
A subárvore da direita de um nodo não deve possuir chaves