Lesson19

Nesta aula vamos estudar árvores binárias enquanto estrutura de dados, métodos de travessia de árvores, e procura em árvores binárias de pesquisa.

Uma árvore binária (de pesquisa) tem a seguinte estrutura:

No caso das árvores de pesquisa binária, como no exemplo acima, os nós na sub-árvore esquerda tem chaves menores ou iguais que a raiz, e os nós na sub-árvore direita tem chaves maiores ou iguais que a raiz.

Implementação: estrutura de dados

#include <stdlib.h>
#include "Item.h"

typedef struct node* link;
struct node { Item item; link l, r;};
static link head;

void init() {
  head = NULL;
}

link NEW(Item item, link l, link r) {
  link x = malloc(sizeof(struct node));
  x->item = item;
  x->l = l; 
  x->r = r;
  return x;
}

Pesquisa

Dado um elemento, a pesquisa começa na raiz (ou head ou root) e verificamos se o mesmo é igual ao item guardado na raiz. Se for igual, então retornamos o nó (link) onde estamos, caso contrário continuamos a pesquisa com o filho da esquerda ou com o filho da direita dependendo se o elemento que procuramos é menor ou maior que o item na raiz, respectivamente.

link search(link h, Item v) {
  if (h == NULL) 
    return NULL;
  if eq(v, h->item)
    return h;
  if less(v, h->item)
    return search(h->l, v);
  else
    return search(h->r, v);
}

Inserção

Começamos na rais e vamos percorrendo a árvore de cima para baixo até encontrar o lugar onde introduzir o novo elemento. Quando encontrarmos o lugar vazio (NULL) para o novo elemento (respeitando as regras da binary search tree), criamos um novo elemento. Tal como no caso anterior, podemos fazer esta operação de forma recursiva.

link insert(link h, Item item) {
  if (h == NULL) 
      return NEW(item, NULL, NULL);
  if (less(v, item))
    h->l = insert(h->l, item);
  else
    h->r = insert(h->r, item);
  return h;
}

Exemplo de utilização por parte do cliente:

head = insert(head,10);

Menor e maior elementos

Como encontrar o menor elemento abaixo de um determinado nó? Descemos na árvore sempre pelo filho da esquerda até encontrarmos um nó sem filho esquerdo.

Como encontrar o maior elemento abaixo de um determinado nó? Descemos na árvore sempre pelo filho da direita até encontrarmos um nó sem filho direito.

link max(link h) {
  if (h==NULL || h->r==NULL) return h;
  else return max(h->r);
}

link min(link h) {
  if (h==NULL || h->l==NULL) return h;
  else return min(h->l);
}

Ou em alternativa:

link max(link h) {
  while(h!=NULL && h->r!=NULL)
		h=h->r;
  return h;
}

link min(link h) {
  while(h!=NULL && h->l!=NULL)
		h=h->l;
  return h;
}

Remoção

Operação mais complexa, três casos:

1. Se o nó não tiver filhos é fácil, basta apagar.
2. Se o nó tiver um só filho, também é fácil, por exemplo, para apagar o 18 no exemplo acima, redirecionamos o filho direito do 12 para o 19 e apagamos o 18.
3. Remoção de um nodo interno: i) substituímos o elemento a remover pelo maior dos elementos à esquerda do elemento a ser removido; ii) removemos esse elemento (que está numa nas condições 1 ou 2).

link delete(link h, Item item) {
  link aux ;
  if (h==NULL) return h;
  else if (less(item, h->item)) h->l=delete(h->l,item);
  else if (less(h->item, item)) h->r=delete(h->r,item) ;
  else{
    if (h->l !=NULL && h->r !=NULL ) { /*caso 3*/
      aux=max(h->l);
      h->item = aux->item;
      h->l=delete(h->l, aux->item);
    } else {                           /*casos 1 e 2*/
      aux=h;
      if ( h->l == NULL && h->r == NULL ) h=NULL;
      else if (h->l==NULL) h=h->r; 
      else h=h->l;
      deleteItem(aux->item);
      free(aux); 
    }
  }
  return h;
}

Exemplo relativo ao caso 3:

Número de elementos e profundidade

int count(link h) {
  if (h==NULL) return 0;
  else return count(h->r)+count(h->l)+1;
}

int height(link h) 
{
  int u, v; 
  if (h == NULL) return 0; 
  u = height(h->l); 
  v = height(h->r); 
  if (u > v) return u+1; 
  else       return v+1;
}

Travessia

Função visit:

/* exemplo para inteiros */
void visit (Item i)
{
  printf("%d\n", i);
} 

Travessia em Pre-Order: visita raíz antes dos filhos. Sequência para o exemplo acima:

20
12
8
2
9
18
19
32
23
45

Implementação:

void traverse(link h)
{
  if (h == NULL)
    return;
  visit(h->item);
  traverse(h->l);
  traverse(h->r);
}

Travessia em In-Order: visita a raíz depois do filho esquerdo e antes do direito. Sequência para o exemplo acima:

2
8
9
12
18
19
20
23
32
45

Notar que a sequência vem ordenada.

Implementação:

void traverse(link h)
{
  if (h == NULL)
    return;
  traverse(h->l);
  visit(h);
  traverse(h->r);
}

Travessia em Post-Order: visita a raíz depois dos filhos. Sequência para o exemplo acima:

2
9
8
19
18
12
23
45
32
20

Exemplo de aplicação: avaliação de expressões posfixadas.

Implementação:

void traverse(link h)
{
  if (h == NULL)
    return;
  traverse(h->l);
  traverse(h->r);
  visit(h);
}

Análise e complexidade

• Geralmente eficiente: $O(\log n)$.
• No pior caso, $O(n)$ para uma árvore desequilibrada. Exemplo, ordem de inserção: 1,2,3,4,5,6,7,8
• No caso de chaves aleatórias, $O(\log n)$.
• Comparação com pesquisa binária em tabelas:
  • tempo de pesquisa comparável;
  • tempo de inserção muito mais rápido.
• Tempo de pesquisa e inserção são $O(n)$ no pior caso (árvore degenerada).

Árvores equilibradas

• Evitam o pior caso de $O(n)$.
• Algum overhead na construção.
• Alternativa:
  • reequilibrar uma árvore, depois de construída;
  • usar aleatoriedade;
  • usar técnicas especiais de construção (AVL, Red-Black, etc.).

Exemplo

Crie um programa que permita guardar, numa árvore binária, todos os alunos de IAED, onde cada aluno é caracterizado pelo seu nome, nota final e um inteiro identificativo do curso. Estruture o seu programa através de ADTs. A chave (a key) utilizada para a organização da árvore deverá ser dada pelo nome do aluno.

Cada nó da árvore binária deverá ser representado por uma estrutura do tipo:

/* O tipo Item ficara definido em Item.h */
typedef struct node {
  Item item;
  struct node *l;
  struct node *r;
} *link;

Ficheiro Item.h:

#ifndef _ITEM_
#define _ITEM_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define key(a) (a != NULL ? a->nome : "")
#define less(a,b) (strcmp(a,b)<0)
#define eq(a,b) (strcmp(a,b)==0)
#define NULLitem NULL

typedef char* Key;
typedef struct estudante { 
char* nome; int notaIAED; int curso;
} * Item;     

Item newItem(char*nome, int nota, int curso);
void deleteItem(Item a);
void visitItem(Item a);

#endif

Ficheiro Item.c:

#include "Item.h"

Item newItem(char*nome, int nota, int curso)
{
    Item x = (Item)malloc(sizeof(struct estudante));
    x->nome = strdup(nome);
    x->notaIAED = nota;
    x->curso = curso;
    return x;
}

void deleteItem(Item a)
{
    free(a->nome);
    free(a);
}

void visitItem(Item a)
{
    printf("nome: %s\n",a->nome);
    printf("notaIAED: %d\n",a->notaIAED);
    printf("curso: %d\n\n",a->curso);
}

Interface do ADT Tabela de Símbolos, ficheiro ST.h:

#ifndef _ST_
#define _ST_

#include <stdlib.h>
#include <stdio.h>
#include "Item.h"

typedef struct STnode* link;
struct STnode { Item item; link l, r;};

void STinit(link*);
int STcount(link);
Item STsearch(link,Key);
void STinsert(link*,Item);
void STdelete(link*,Key);
void STsort(link,void (*visit)(Item));
void STfree(link*);
#endif

Ficheiro ST.c:

#include "ST.h"

link NEW(Item item, link l, link r)
{
    link x = (link)malloc(sizeof(struct STnode));
    x->item = item;
    x->l = l;
    x->r = r;
    return x;
}

void STinit(link*head)
{
    *head = NULL;
}

link insertR(link h, Item item) {                                                                  
    if (h == NULL)
        return NEW(item, NULL, NULL);
    if (less(key(item), key(h->item)))
        h->l = insertR(h->l, item);
    else
        h->r = insertR(h->r, item);
    return h;
}

void STinsert(link*head, Item item)
{
    *head = insertR(*head, item);
}

Item searchR(link h, Key v)
{
    if (h == NULL)
        return NULLitem;
    if (eq(v, key(h->item)))
        return h->item;
    if (less(v, key(h->item)))
        return searchR(h->l, v);
    else
        return searchR(h->r, v);
}

Item STsearch(link head, Key v)
{
    return searchR(head, v);
}

link deleteR(link h, Key k) 
{
    if (h==NULL) return h;    
    else if (less(k, key(h->item))) h->l=deleteR(h->l,k);
    else if (less(key(h->item), k)) h->r=deleteR(h->r,k) ;
    else {
        if (h->l !=NULL && h->r !=NULL){/*caso 3*/   
            link aux=max(h->l);
            {Item x; x=h->item; h->item=aux->item; aux->item=x; }            
            h->l= deleteR(h->l, key(aux->item));
        }
        else { /*casos 1 e 2*/
		    link aux=h;
            if ( h->l == NULL && h->r == NULL ) h=NULL;
            else if (h->l==NULL) h=h->r;
            else h=h->l;
            deleteItem(aux->item); 
            free(aux);
        }   
    }
    return h;
}

link max(link h) {
    if (h==NULL || h->r==NULL) return h;
    else return max(h->r);
}

int count(link h){
    if (h==NULL) return 0;
    else return count(h->r)+count(h->l)+1;
}

int STcount(link head){
    return count(head);
}

void STdelete(link*head, Key k){   
    *head = deleteR(*head, k);
}

void sortR(link h, void (*visit)(Item)) 
{
    if (h == NULL)
        return;
    sortR(h->l, visit);
    visit(h->item);
    sortR(h->r, visit);
}

void STsort(link head, void (*visit)(Item))
{
    sortR(head, visit);
}

link freeR(link h)
{
    if (h==NULL) 
        return h;
    h->l=freeR(h->l);
    h->r=freeR(h->r);
    return deleteR(h,key(h->item));
}

void STfree(link*head)
{
    *head=freeR(*head);
}

Cliente, ficheiro main.c:

#include <stdio.h>
#include "ST.h"

int main(){
    link turma1;    
    STinit(&turma1);

    STinsert(&turma1, newItem("Mikhail Gorbachev", 10, 0));
    STinsert(&turma1, newItem("Jimmy Carter", 10, 0));
    STinsert(&turma1, newItem("Barack Obama", 12, 0));    
 
    STsort(turma1,visitItem);

    printf("numero de alunos: %d\n",STcount(turma1));
    STdelete(&turma1,"Barack Obama");
    printf("numero de alunos: %d\n",STcount(turma1));

    STfree(&turma1);

    return 0;
}

Função tsearch

Existem funções definidas em search.h que nos permitem gerir uma árvore binária de pesquisa.

#include <search.h>

void *tsearch(const void *key, void **rootp,
                int (*compar)(const void *, const void *));

void *tfind(const void *key, const void **rootp,
                int (*compar)(const void *, const void *));

void *tdelete(const void *key, void **rootp,
                int (*compar)(const void *, const void *));

void twalk(const void *root, void (*action)(const void *nodep,
                                   const VISIT which,
                                   const int depth));

#define _GNU_SOURCE
#include <search.h>

void tdestroy(void *root, void (*free_node)(void *nodep));

Nestas funções, rootp é um ponteiro para um ponteiro para a raiz e root é um ponteiro para a raiz. A árvore é vazia quando o ponteiro para a raiz for NULL. O parâmetro key é um ponteiro para o item a procurar. A função tsearch procura um elemento e, se este não existir, adiciona o mesmo. Esta função retorna um ponteiro para o elemento encontrado, ou inserido se for o caso. A função tfind é idêntica à função tsearch, mas não insere o elemento quando este não existe, retornando NULL nesse caso. A função tdelete permite eliminar um elemento da árvore. O parâmetro compar nestas três funções define a ordem total a ter em conta.

A função twalk permite efectuar travessias numa árvore binária em que o parâmetro action define o que fazer quando um nó é visitado. O parâmetro which da função action deve ser tido em conta na implementação da mesma uma vez que indica em que fase da visita estamos.

Exemplo (tsearch.c):

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <search.h>

#define STEPS 32

static void * root = NULL;

static int
compare(const void *pa, const void *pb)
{
  return (long int) pa - (long int) pb;
}

void
action (const void *nodep, const VISIT which, const int depth)
{
  long int data;

  switch (which)
    {
    case preorder:
      break;
    case postorder:
      data = *(long int *) nodep;
      printf ("%6ld\n", data);
      break;
    case endorder:
      break;
    case leaf:
      data = *(long int *) nodep;
      printf ("%6ld\n", data);
      break;
    }
}

void do_nothing(void * p) {}

int
main(int argc, char *argv[])
{
  long int value;
  size_t i;

  if (argc > 1)
    srand(atoi(argv[1]));

  for (i = 0; i < STEPS; i++) {
    value = rand()%100;
    tsearch((void *) value, &root, compare);
  }

  twalk(root, action);

  tdestroy(root, do_nothing);
  return EXIT_SUCCESS;
}

Compilar e executar:

[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic -o tsearch tsearch.c 
[aplf@darkstar ~]$ valgrind ./tsearch $RANDOM
==21060== Memcheck, a memory error detector
==21060== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==21060== Using Valgrind-3.9.0 and LibVEX; rerun with -h for copyright info
==21060== Command: ./tsearch 17208
==21060== 
     1
    14
    19
    23
    25
    26
    29
    30
    34
    35
    37
    41
    48
    51
    52
    53
    57
    59
    62
    64
    66
    71
    76
    77
    85
    86
    97
==21060== 
==21060== HEAP SUMMARY:
==21060==     in use at exit: 0 bytes in 0 blocks
==21060==   total heap usage: 27 allocs, 27 frees, 864 bytes allocated
==21060== 
==21060== All heap blocks were freed -- no leaks are possible
==21060== 
==21060== For counts of detected and suppressed errors, rerun with: -v
==21060== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
[aplf@darkstar ~]$