Na Aula 11 vimos o conceito de árvore binária e os quatro caminhamentos clássicos. Nesta aula estudamos a Árvore Binária de Pesquisa (Abp): uma árvore binária com uma propriedade de ordenação que permite buscar, inserir e remover elementos de forma eficiente. Veremos a definição da propriedade, a representação em C, todas as operações e sua complexidade — incluindo o caso degenerado que motiva o estudo de árvores balanceadas (Aula 14).

1. A propriedade da Abp

Uma Árvore Binária de Pesquisa (Abp) é uma árvore binária que satisfaz a propriedade de ordenação: para todo nó x,

• todos os valores na subárvore esquerda de x são menores que o valor de x;
• todos os valores na subárvore direita de x são maiores que o valor de x.

Essa propriedade vale recursivamente para toda subárvore, não só para a raiz. É o que permite, a cada passo de uma busca, descartar metade (ou mais) da árvore restante — do mesmo jeito que a busca binária em vetores ordenados descarta metade do vetor.

        50              <- tudo à esquerda < 50; tudo à direita > 50
       /  \
     30    70           <- subárvore esq.: tudo < 30 à esq de 30; tudo > 30 à dir de 30
    /  \   /  \              (e todos < 50 pela propriedade da raiz)
  20   40 60   80

Uma consequência direta: o caminhamento em-ordem de uma Abp sempre produz os valores em ordem crescente — decorrência direta da propriedade de ordenação aplicada recursivamente.

2. Representação em C e interface do TAD

Cada nó guarda o dado e dois ponteiros, esq e dir. A árvore inteira é representada pelo ponteiro para o nó raiz; uma árvore vazia é simplesmente NULL:

typedef struct {
    int  cod;
    char nome[50];
    float preco;
} Produto;

typedef struct str_NodoArv NodoArv;

struct str_NodoArv {
    Produto  dado;
    NodoArv *esq;
    NodoArv *dir;
};

/* Inicializar = declarar NULL:  NodoArv *raiz = NULL; */

As operações que modificam a árvore (inserir, remover) recebem o ponteiro raiz como parâmetro e o devolvem atualizado. O chamador precisa reatribuir:

NodoArv* abpBuscar   (NodoArv *raiz, int cod);      /* ponteiro p/ nó com dado.cod==cod, ou NULL */
NodoArv* abpInserir  (NodoArv *raiz, Produto p);   /* insere p preservando propriedade          */
NodoArv* abpRemover  (NodoArv *raiz, int cod);      /* remove cod preservando propriedade        */
void     abpDestruir (NodoArv *raiz);               /* libera toda a memória                     */
void     abpEmOrdem  (const NodoArv *raiz);         /* imprime em ordem crescente de cod         */

/* Uso: */
raiz = abpInserir(raiz, produto);
raiz = abpRemover(raiz, cod);

3. Operações

Todas as operações principais seguem o mesmo padrão recursivo da Aula 11: caso base para NULL, e duas chamadas recursivas que descem pela subárvore esquerda ou direita. A propriedade da Abp decide qual subárvore percorrer.

3.1 Buscar

Ideia: começa na raiz. Se o valor buscado é igual ao nó atual, encontrou. Se é menor, vai à esquerda; se é maior, vai à direita. Repete até encontrar ou chegar a NULL (não existe). A cada passo, descarta-se uma subárvore inteira — exatamente como a busca binária.

Exemplo: buscar 40 na árvore abaixo.

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

abpBuscar([50], 40):    40 < 50  →  desce à esquerda
  abpBuscar([30], 40):  40 > 30  →  desce à direita
    abpBuscar([40], 40): 40 == 40 →  encontrou!  retorna [40]
  retorna [40]
retorna [40]

Exemplo: buscar 45 (não existe).

abpBuscar([50], 45):    45 < 50  →  desce à esquerda
  abpBuscar([30], 45):  45 > 30  →  desce à direita
    abpBuscar([40], 45): 45 > 40  →  desce à direita
      abpBuscar(NULL, 45):  NULL  →  não encontrado, retorna NULL
    retorna NULL
  retorna NULL
retorna NULL

NodoArv* abpBuscar(NodoArv *raiz, int cod) {
    if (raiz == NULL)              return NULL;    // não encontrado
    if (cod == raiz->dado.cod)     return raiz;    // encontrado
    if (cod < raiz->dado.cod)
        return abpBuscar(raiz->esq, cod);           // só olha a esquerda
    return abpBuscar(raiz->dir, cod);               // só olha a direita
}

Versão iterativa. A busca é a operação mais simples de tornar iterativa: basta substituir as chamadas recursivas por um while que avança atual pelo caminho correto até encontrar o elemento ou chegar em NULL.

NodoArv* abpBuscarIter(NodoArv *raiz, int cod) {
    NodoArv *atual = raiz;
    while (atual != NULL) {
        if (cod == atual->dado.cod)
            return atual;          /* encontrado */
        if (cod < atual->dado.cod)
            atual = atual->esq;
        else
            atual = atual->dir;
    }
    return NULL;               /* não encontrado */
}

3.2 Inserir

Ideia: desce a árvore como se estivesse buscando o valor. Quando chega a NULL, esse é o lugar certo para o novo nó (qualquer outro lugar violaria a propriedade). O truque do retorno: cada chamada devolve o ponteiro que o nível acima deve usar para esq ou dir — assim o novo nó é "pendurado" automaticamente na subida da recursão, sem precisar de um ponteiro "pai" extra.

Exemplo: inserir 35 na árvore.

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

abpInserir([50], 35):   35 < 50  →  desce à esquerda
  abpInserir([30], 35): 35 > 30  →  desce à direita
    abpInserir([40], 35): 35 < 40  →  desce à esquerda
      abpInserir(NULL, 35):  NULL  →  cria [35], retorna [35]
    [40].esq = [35];  retorna [40]
  [30].dir = [40];    retorna [30]
[50].esq = [30];      retorna [50]

Resultado:
        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80
     /
    35

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80
     /
    35          <-- novo nó

NodoArv* abpInserir(NodoArv *raiz, Produto valor) {
    if (raiz == NULL) {
        NodoArv *novo = (NodoArv*) malloc(sizeof(NodoArv));
        novo->dado = valor;
        novo->esq  = NULL;
        novo->dir  = NULL;
        return novo;                         // pai vai "pendurar" este nó
    }
    if (valor.cod < raiz->dado.cod)
        raiz->esq = abpInserir(raiz->esq, valor);
    else if (valor.cod > raiz->dado.cod)
        raiz->dir = abpInserir(raiz->dir, valor);
    // se igual: código já existe, não insere duplicado
    return raiz;                             // devolve raiz (inalterada) ao pai
}

3.3 Remover

Ideia: primeiro desce pela árvore como na busca, até encontrar o nó. Ao encontrá-lo, há três casos dependendo do número de filhos. O mesmo idioma de retorno da inserção faz o pai "religar" o ponteiro correto automaticamente na subida.

Os três casos:

• Caso 1 — nó é folha (0 filhos): libera o nó e retorna NULL. O pai, ao receber NULL, passa a apontar para o vazio — correto.
• Caso 2 — nó tem 1 filho: libera o nó e retorna o único filho. O filho "sobe" para o lugar do nó removido, e a propriedade da Abp é preservada pois o filho já estava do lado correto.
• Caso 3 — nó tem 2 filhos: não dá para remover diretamente, pois dois filhos competem pelo mesmo lugar. A solução é não remover o nó: em vez disso, encontra-se o sucessor em-ordem (o menor valor da subárvore direita — o nó mais à esquerda possível a partir da direita), copia-se o seu valor para o nó atual, e remove-se o sucessor de onde ele estava. O sucessor nunca tem filho esquerdo (caso contrário não seria o mínimo), então sua remoção é sempre caso 1 ou 2.

Por que o sucessor preserva a propriedade? O sucessor é o menor valor da subárvore direita: logo, é maior que tudo na subárvore esquerda e menor que todo o restante da subárvore direita. Colocá-lo no lugar do nó removido mantém a propriedade intacta.

Caso 1 — folha (0 filhos): remover 20

        50
       /  \
     30    70
    /  \    \
  20  40    80

        50
       /  \
     30    70
       \    \
       40   80

Caso 2 — um filho: remover 70 (filho único: 80)

        50
       /  \
     30    70
    /  \    \
  20  40    80

        50
       /  \
     30   80    <-- 80 subiu para o lugar de 70
    /  \
  20  40

Caso 3 — dois filhos: remover 30 (sucessor em-ordem: 40)

        50
       /  \
     30    70
    /  \    \
  20  40    80

        50
       /  \
     40    70    <-- 40 (sucessor) copiado para o lugar de 30
    /       \         o nó original 40 foi removido (era folha)
  20        80

Exemplo com os três casos. Usaremos a árvore abaixo e faremos três remoções diferentes:

Árvore inicial:
           50
          /  \
        30    70
       /  \    \
     20   40   80

Remoção 1: remover 20 — Caso 1 (folha)

abpRemover([50], 20):   20 < 50  →  desce à esquerda
  abpRemover([30], 20): 20 < 30  →  desce à esquerda
    abpRemover([20], 20): achou! é folha (caso 1) → free([20]), retorna NULL
  [30].esq = NULL;   retorna [30]
[50].esq = [30];     retorna [50]

Resultado:
           50
          /  \
        30    70
          \    \
          40   80

Remoção 2: remover 70 — Caso 2 (um filho: só 80 à direita)

(partindo do resultado anterior, sem o 20)

abpRemover([50], 70):   70 > 50  →  desce à direita
  abpRemover([70], 70): achou! tem só filho direito (caso 2) → free([70]), retorna [80]
[50].dir = [80];     retorna [50]

Resultado:
           50
          /  \
        30   80
          \
          40

Remoção 3: remover 30 — Caso 3 (dois filhos: 20 e 40)

(voltando à árvore inicial, com todos os nós)

           50
          /  \
        30    70
       /  \    \
     20   40   80

abpRemover([50], 30):   30 < 50  →  desce à esquerda
  abpRemover([30], 30): achou! tem 2 filhos (caso 3)
    sucessor = abpMinimo([40]) = [40]   (nó mais à esquerda a partir de 30.dir)
    [30].dado ← dado de [40]            (copia o valor 40 para o lugar de 30)
    agora remove o [40] original da subárvore direita de [30]:
      abpRemover([40], 40): achou! é folha (caso 1) → free([40]), retorna NULL
    [30].dir = NULL;   retorna [30]  (mas agora [30] contém o valor 40)
  [50].esq = [30];     retorna [50]

Resultado:
           50
          /  \
        40    70
       /       \
     20         80

// encontra o nó de menor valor (mais à esquerda) de uma subárvore
NodoArv* abpMinimo(NodoArv *raiz) {
    while (raiz->esq != NULL)
        raiz = raiz->esq;
    return raiz;
}

NodoArv* abpRemover(NodoArv *raiz, int cod) {
    if (raiz == NULL) return NULL;               // não encontrado

    if (cod < raiz->dado.cod)
        raiz->esq = abpRemover(raiz->esq, cod);   // procura/remove na esquerda
    else if (cod > raiz->dado.cod)
        raiz->dir = abpRemover(raiz->dir, cod);   // procura/remove na direita
    else {
        // achou o nó a remover
        if (raiz->esq == NULL && raiz->dir == NULL) {
            free(raiz);   // caso 1: folha
            return NULL;
        }
        if (raiz->esq == NULL) {
            NodoArv *filho = raiz->dir;   // caso 2: só filho direito
            free(raiz);
            return filho;
        }
        if (raiz->dir == NULL) {
            NodoArv *filho = raiz->esq;   // caso 2: só filho esquerdo
            free(raiz);
            return filho;
        }
        // caso 3: dois filhos
        NodoArv *sucessor = abpMinimo(raiz->dir);
        raiz->dado = sucessor->dado;                              // copia valor do sucessor
        raiz->dir  = abpRemover(raiz->dir, sucessor->dado.cod);  // remove o sucessor
    }
    return raiz;
}

3.4 Destruir

abpDestruir usa pós-ordem: libera os filhos antes do próprio nó, pois o free tornaria os ponteiros esq/dir inválidos.

void abpDestruir(NodoArv *raiz) {
    if (raiz == NULL) return;
    abpDestruir(raiz->esq);
    abpDestruir(raiz->dir);
    free(raiz);
}

abpDestruir(raiz);
raiz = NULL;   // responsabilidade do chamador

3.5 Exemplo de uso completo (main)

int main() {
    NodoArv *raiz = NULL;   /* árvore vazia */
    NodoArv *encontrado;
    Produto p;

    /* --- inserir alguns produtos --- */
    p.cod = 50; p.preco = 99.90; raiz = abpInserir(raiz, p);
    p.cod = 30; p.preco = 49.90; raiz = abpInserir(raiz, p);
    p.cod = 70; p.preco = 79.90; raiz = abpInserir(raiz, p);
    p.cod = 20; p.preco = 19.90; raiz = abpInserir(raiz, p);
    p.cod = 40; p.preco = 39.90; raiz = abpInserir(raiz, p);

    /* em-ordem imprime: 20 30 40 50 70 */
    abpEmOrdem(raiz);

    /* --- buscar --- */
    encontrado = abpBuscar(raiz, 30);
    if (encontrado != NULL)
        printf("Encontrado: cod=%d preco=%.2f\n",
               encontrado->dado.cod, encontrado->dado.preco);
    else
        printf("Nao encontrado.\n");

    /* --- remover --- */
    raiz = abpRemover(raiz, 30);   /* caso 3: 30 tem dois filhos */
    raiz = abpRemover(raiz, 20);   /* caso 1: 20 é folha         */
    raiz = abpRemover(raiz, 70);   /* caso 1: 70 virou folha      */

    /* em-ordem agora imprime: 40 50 */
    abpEmOrdem(raiz);

    /* --- destruir e anular o ponteiro --- */
    abpDestruir(raiz);
    raiz = NULL;

    return 0;
}

4. Complexidade das operações

Todas as operações principais da Abp (buscar, inserir, remover) descem a árvore por um único caminho, da raiz até, no pior caso, uma folha — seu custo é sempre proporcional à altura h da árvore:

inserir 10, 20, 30, 40 (em ordem crescente):

10
  \
   20
     \
      30
        \
         40      // árvore "torta": h = n-1 = 3

Resumindo: no melhor caso (árvore perfeitamente balanceada), h = O(log₂ n), e buscar/inserir/remover custam O(log₂ n). No pior caso (árvore degenerada), h = O(n), e essas mesmas operações custam O(n).

Resumo

Exercícios

Questões teóricas

1. Explique a propriedade da Abp com suas próprias palavras. Por que ela precisa valer recursivamente para toda subárvore e não apenas para a raiz? Dê um exemplo de árvore binária que satisfaz a propriedade somente na raiz mas que não é uma Abp válida.
2. Dada a sequência de inserções 50, 30, 70, 20, 40, 60, 80:
   • Desenhe a Abp resultante.
   • Escreva o caminhamento em-ordem, pré-ordem e pós-ordem.
   • Qual é a altura da árvore?
3. Mostre o passo a passo da remoção do nó 30 (que tem dois filhos) na árvore do exercício anterior. Qual nó ocupa o lugar de 30 e por quê?
4. Explique os três casos de remoção de um nó numa Abp. Por que o caso de dois filhos utiliza o sucessor em-ordem? Prove que o sucessor em-ordem de um nó com dois filhos nunca tem filho esquerdo.
5. A busca, inserção e remoção numa Abp custam O(h), onde h é a altura. No melhor caso h = O(log₂ n); no pior caso h = O(n).
   • Dê um exemplo de sequência de inserções que produz o pior caso (árvore degenerada).
   • Dê um exemplo de sequência que produz o melhor caso (árvore balanceada) com os mesmos elementos.
   • Por que a ordem de inserção afeta a altura?
6. Por que abpDestruir usa pós-ordem (libera os filhos antes do próprio nó) e não pré-ordem? O que aconteceria se o free(raiz) fosse chamado antes das chamadas recursivas?

Questões de implementação

Os exercícios a seguir pedem a implementação de funções em C sobre a Abp. Use recursão. Os tipos NodoArv e Produto são os definidos nesta aula.

1. Implemente int abpAltura(const NodoArv *raiz) que retorna a altura da árvore (convenção: árvore vazia tem altura −1; árvore com só a raiz tem altura 0).
2. Implemente int abpContar(const NodoArv *raiz) que retorna o número total de nós da árvore.
3. Implemente int abpContarFolhas(const NodoArv *raiz) que retorna o número de folhas (nós sem filhos).
4. Implemente void abpImprimirEntre(const NodoArv *raiz, int a, int b) que imprime, em ordem crescente, todos os elementos cujo dado.cod está no intervalo fechado [a, b]. Aproveite a propriedade da Abp para não descer por subárvores que certamente não contenham valores no intervalo.
5. Implemente int abpSomaChaves(const NodoArv *raiz) que retorna a soma de todos os valores dado.cod da árvore.
6. Implemente int abpContarMaiores(const NodoArv *raiz, int val) que retorna a quantidade de nós com dado.cod > val. Use a propriedade da Abp para podar a busca quando possível.
7. Implemente NodoArv* abpCopiar(const NodoArv *raiz) que retorna uma cópia profunda (deep copy) da árvore, alocando novos nós com malloc. A árvore copiada deve ser independente da original.
8. Implemente int abpEstahPresente(const NodoArv *raiz, int cod) usando recursão (sem while ou for). A função deve retornar 1 se o cod existir na árvore, 0 caso contrário.

Sugestões de Respostas dos Exercícios

Questões teóricas

    50
   /  \
  30   70
    \
    80    <- 80 > 50, mas está na subárvore ESQUERDA de 50 (violação!)

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

Pré-ordem:  50 30 20 40 70 60 80
Em-ordem:   20 30 40 50 60 70 80   (ordem crescente)
Pós-ordem:  20 40 30 60 80 70 50
Altura: 2

        50
       /  \
     40    70      <- 40 subiu para o lugar de 30
    /     /  \
  20    60   80

Questões de implementação

int abpAltura(const NodoArv *raiz) {
    int altEsq, altDir;
    if (raiz == NULL) return -1;   // convenção: vazia tem altura -1
    altEsq = abpAltura(raiz->esq);
    altDir = abpAltura(raiz->dir);
    if (altEsq > altDir)
        return 1 + altEsq;
    else
        return 1 + altDir;
}

int abpContar(const NodoArv *raiz) {
    if (raiz == NULL) return 0;
    return 1 + abpContar(raiz->esq) + abpContar(raiz->dir);
}

int abpContarFolhas(const NodoArv *raiz) {
    if (raiz == NULL) return 0;
    if (raiz->esq == NULL && raiz->dir == NULL) return 1;   // é folha
    return abpContarFolhas(raiz->esq) + abpContarFolhas(raiz->dir);
}

void abpImprimirEntre(const NodoArv *raiz, int a, int b) {
    if (raiz == NULL) return;

    // só desce à esquerda se puder haver valores >= a lá
    if (raiz->dado.cod > a)
        abpImprimirEntre(raiz->esq, a, b);

    if (raiz->dado.cod >= a && raiz->dado.cod <= b)
        printf("%d ", raiz->dado.cod);

    // só desce à direita se puder haver valores <= b lá
    if (raiz->dado.cod < b)
        abpImprimirEntre(raiz->dir, a, b);
}

int abpSomaChaves(const NodoArv *raiz) {
    if (raiz == NULL) return 0;
    return raiz->dado.cod
         + abpSomaChaves(raiz->esq)
         + abpSomaChaves(raiz->dir);
}

int abpContarMaiores(const NodoArv *raiz, int val) {
    if (raiz == NULL) return 0;

    if (raiz->dado.cod <= val)
        // este nó e toda a subárvore esquerda são <= val; só a direita interessa
        return abpContarMaiores(raiz->dir, val);

    // este nó é > val: conta ele + tudo na direita + possíveis na esquerda
    return 1 + abpContarMaiores(raiz->dir, val)
             + abpContarMaiores(raiz->esq, val);
}

NodoArv* abpCopiar(const NodoArv *raiz) {
    NodoArv *novo;
    if (raiz == NULL) return NULL;

    novo = (NodoArv*) malloc(sizeof(NodoArv));
    novo->dado = raiz->dado;
    novo->esq  = abpCopiar(raiz->esq);   // copia subárvore esquerda
    novo->dir  = abpCopiar(raiz->dir);   // copia subárvore direita
    return novo;
}

int abpEstahPresente(const NodoArv *raiz, int cod) {
    if (raiz == NULL)           return 0;
    if (cod == raiz->dado.cod)  return 1;
    if (cod < raiz->dado.cod)
        return abpEstahPresente(raiz->esq, cod);
    return abpEstahPresente(raiz->dir, cod);
}