Estruturas de Dados

Árvores binárias de busca

Árvores Binárias onde cada nó x obedece as seguintes propriedades:
- Todas as chaves dos nós pertencentes à sub-árvore esquerda de x são "menores que" a chave de x e
- Todas as chaves dos nós pertencentes à sub-árvore direita de x são "maiores que" a chave de x.
Exemplos:
(10 (5 () (9 () ())) (15 (13 () ()) (18 () ())))
(10 (5 () (9 (7 () ()) ())) (15 (13 (12 () ()) ()) (18 (16 () ()) ())))
Não Exemplos:
(14 (5 () (9 () ())) (15 (13 () ()) (18 () ())))

Algoritmo de Inserção

SNo * BuscaPontoInsercao(SNo * x,int k)
{
    if(k>x->chave)
    {
         if(x->FD == NULL)
         {
              return(x);
         }
         else
         {
               return(BuscaPontoInsercao(x->FD,k));
         }
    }
    else
    {
         if(x->FE == NULL)
        {
              return(x);
        }
        else
        {
               return(BuscaPontoInsercao(x->FE,k));
        }
    }
}

void Insere(int k)
{
SNo * Lugar;
SNo * NovoNo;

NovoNo = new SNo;

    NovoNo->chave = k;
    NovoNo->FE = NovoNo->FD = NULL;

    if(Raiz==NULL)
    {
         Raiz = NovoNo;
    }
    else
    {
         Lugar = BuscaPontoInsercao(Raiz,k);
         if(Lugar->chave < k)
         {
               Lugar->FD = NovoNo;
         }
         else
         {
              Lugar->FE = NovoNo;
         }
    }
}

abbEmJava.tar.gz Exemplo de implementação de ABB em Java

canvas.tar.gz Exemplo simples de utilização da classe Canvas. Este código pode ser aprimorado para que seja possível a apresentação da ABB em modo gráfico.

Algoritmo de Remoção

Note que ao invés de acrescentar um ponteiro para o pai na estrutura do nó, optou-se por criar uma função que devolve o pai de um nó, fazendo uma busca na árvore (economiza-se em espaço mas perde-se em tempo de processamento).

SNo * Busca(SNo * x,int k)
{
   if(x==NULL) return(NULL); /* k nao esta na arvore */
   if(x->chave == k) return(x);
   else
   {
      if(k<x->chave) return(Busca(x->FE,k));
      else return(Busca(x->FD,k));
   }
}

SNo * BuscaPai(SNo * Pai, SNo * Filho)
{
   if(Pai==NULL) return(NULL);
   if(Pai->FD == Filho || Pai->FE == Filho) return(Pai);
   else
   {
      if(Filho->chave < Pai->chave) return(BuscaPai(Pai->FE,Filho));
      else return(BuscaPai(Pai->FD,Filho));
   }
}

void Remove(int k)
{
RemoveNo(Busca(Raiz,k));
}

SNo * Menor(SNo * x)
{
if( !(x->FE) ) return(x);
else return(Menor(x->FE));
}

SNo * Maior(SNo * x)
{
if( !(x->FD) ) return(x);
else return(Menor(x->FD));
}

void RemoveNo(SNo * x)
{
SNo * Pai;
SNo * y;

   Pai = BuscaPai(Raiz,x);

   if(x->FD == NULL && x->FE == NULL)
   {
      if(Pai)
      {
        if(Pai->FE == x) Pai->FE = NULL;
        else Pai->FD = NULL;
      }
      else
      {
        Raiz = NULL;
      }
      delete x;
   }
   else
   {
      if(x->FD != NULL)
      {
         y = Menor(x->FD);
      }
      else
      {
         y = Maior(x->FE);
      }
      x->chave = y->chave;
      RemoveNo(y);
   }
}

Mostrando a árvore em modo texto

/* As 3 funções seguintes são usadas para mostrar, usando apenas ANSI C, uma árvore na representação hierárquica. */

void MostraArvore()
{
PreOrdem(Raiz,1,80);
}

void PreOrdem(SNo * x,int i,int f)
{
   if(x!=NULL)
   {
      Espacos(i+((f-i)/2));
      printf("%d\n",x->chave);
      PreOrdem(x->FE,i,i+((f-i)/2));
      PreOrdem(x->FD,i+((f-i)/2),f);
   }
}

void Espacos(int t)
{
int i;
for(i=1;i<=t;++i) printf(" ");
}