Algoritmos, Programação e esturturas de dados

Pequena Introdução:

As árvores binárias ordenadas são estruturas recursivas compostas por elementos do mesmo tipo.
Estas árvores são árvores binárias normais mas que têm os elementos ordenados permitindo uma busca mais rápida.
Cada nó pode ter no máximo dois filhos.
Os filhos de menor valor ficam à esquerda do nó e os filhos de maior valor ficam à direita do nó.

A estrutura básica é um elemento ligado a duas árvores que se repete ao longo de toda a estrutura.

A inserção de elementos numa árvore ordenada:

A inserção de elementos é sempre feita na cabeça da árvore.
Os casos possíveis de inserção são:

Situação encontrada	Solução a utilizar
Árvore vazia	O elemento é introduzido na cabeça da árvore
Elemento a inserir é menor	O elemento é introduzido na sub-árvore esquerda
Elemento a inserir é maior	O elemento é introduzido na sub-árvore direita

Implementação prática (função recursiva):

Function inserir(x:elemento;a:arvore):arvore;
    if evaz_arv(a) then
        inserir:=criar_arv(x,null,null)
    else
        if x<no(a) then
            inserir:=criar_arv(no(a),inserir(x,fe(a)),fd(a))
        else
            inserir:=criar_arv(no(a),fe(a),inserir(x,fd(a))
end;

As sub-funções utilizadas no algoritmo já foram explicadas em aulas anteriores:

evaz_arv(a:arvore):boolean;
(Verifica se a árvore está vazia ou não)

criar_arv(x:elemento;Fe,Fd:arvore):arvore;
(Cria uma árvore com o elemento x na cabeça e com Fe e Fd a apontar para sub-árvores)

no(a:arvore):elemento;
(Visita o nó da árvore, ou seja, devolve o elemento que se encontra no nó)

A utilização de uma função para inserir elementos numa arvore pode criar problemas, pois perdemos a árvore inicial.
A inserção deve ser feita através de procedimentos para evitar problemas.

Implementação prática (procedimento recursivo):

Procedure inserir(x:elemento;var a:arvore):arvore;
    if evaz_arv(a) then
        a<-criar_arv(x,null,null)
    else
        if x<no(a) then
            inserir (x,ponteiro para "filho esquerdo" de "a")
        senão
            inserir (x,ponteiro para "filho direito" de "a")
end

A eliminação de elementos numa árvore ordenada:

A eliminação de um elemento numa árvore ordenada é simples, a única situação a ter em conta é a de escolher qual o elemento que vai ser colocado no lugar do elemento que queremos eliminar. Este elemento deve ter o valor mais próximo possível do elemento a eliminar.
Existem duas formas de eliminar elementos:

- Eliminar o elemento e colocar no lugar do elemento eliminado, o maior elemento da sub-árvore à esquerda do elemento a eliminar (elemento mais à direita da sub-árvore);
- Eliminar o elemento e colocar no lugar do elemento eliminado, o menor elemento da sub-árvore à direita do elemento a eliminar (elemento mais à esquerda da sub-árvore);

Para concluirmos que um elemento é o mais à direita da sub-árvore esquerda, basta ver se o seu filho direito está vazio.
Para ver se um elemento é o mais à esquerda da sub-árvore direita, basta ver se o seu filho esquerdo está vazio.

Uma das soluções tem de ser escolhida para implementar no algoritmo de eliminação.

Implementação prática (função recursiva):

Function eliminar (x:elemento;a:arvore):arvore;
    if evaz_arv(a) then
        eliminar:=null
    else
        if no(a)=x then
            if evaz_arv(fd(a)) then
                eliminar:=fe(a)
            else
                if evaz(fe(a)) then
                    eliminar:=fd(a)
                else
                    eliminar:=criar_arv(min(fd(a)),fe(a),eliminar(min(fd(a))),fd(a))
        else
            if x<no(a) then
                eliminar:=criar_arv(no(a),eliminar(x,fe(a),fd(a));
            else
                eliminar:=criar_arv(no(a),fe(a),eliminar(x,fd(a));
end

Se utilizarmos funções para eliminar podem ocorrer erros pois perde-se a arvore inicial, por isso devem-se utilizar procedimentos:

O procedimento para eliminar, cria uma nova caixa, coloca nessa caixa o menor filho da direita (opção utilizada), coloca no filho esquerdo o antigo filho esquerdo e faz a eliminação no filho direito.

Implementação prática (procedimento recursivo):

Procedure eliminar(x:elemento;var a:arvore):arvore;
    if evaz_arv(a) then
        a<-null
    else
        if no(a)=x then
            if evaz_arv(fd(a)) then
                a:=fe(a)
            else
                (ponteiro para "nó" de "a"):=min(fd(a))
                    eliminar:=(min(fd(a)),(ponteiro para "filho direito" de "a")
        else
            if x<no(a) then
                eliminar(x,(ponteiro para "filho esquerdo" de "a"))
           else
                eliminar(x,(ponteiro para "filho direito" de "a"))

Exemplos:
1 - Exemplo_Eliminação (utilizando procedimentos)
2 - Exemplo_Inserção (utilizando procedimentos)
3 - Exemplo_Eliminação (utilizando procedimentos)

Implementação em (C)

Outros assuntos também referidos na aula:

Função para contar o número de folhas numa árvore:

Funtion conta_folhas (a:arvore):inteiro;
    if evaz_arv(a) then
        return 0
    else
        if fe(a)=null then
            if fd(a)=null then
                return 1;
        else
            conta_folhas(fe(a))+conta_folhas(fd(a))

Função para transformar uma lista numa árvore ordenada:

Funtion lista_arv (l:lista):arvore;
    if evaz(l) then
        return null
    else
        inserir(head(l),lista_arv(cauda(l));

Questões:
Helder Quinzico nº.12090
Joaquim Rodrigues nº.11775