Precisa de uma árvore binária? Use libavl

Outra dica proceis… Eu precisei, no mesmo projeto que citei abaixo, criar uma lista associativa (onde, dado um “nome”, obtenho um valor). Eu poderia implementar isso com um array dinamicamente alocado, mas o tempo de pesquisa poderia ser proporcional a N (onde N é o número de “variáveis” na lista), sem contar que as realocações criariam muita fragmentação de memória… Solução mais prática? Usar uma árvore binária balanceada. O tempo de pesquisa numa árvore desse tipo é proporcional a lg N (quer dizer: log_2 N)… Bem menos do que a implementação de uma lista me daria…

A árvore precisa ser balanceada para que não seja degradável para uma lista. O que me deixaria com o mesmo problema. A partir dai o problema foi decidir qual “tipo” de árvore balanceada usar. Existem algumas mais populares: AVL, Red Black e Splay Trees. Eu tinha decidido pela Red Black Tree porque é uma das mais rápidas e bastante usadas (por curiosidade, o kernel do linux usa uma Red Black Tree para gerenciar memória!)…

Implementar uma árvore binária balanceada não é tão difícil assim, mas também não é a coisa mais fácil do mundo. Felizmente já existe uma library prontinha: libavl. O nome, é claro, é derivado das árvores AVL, uma das primeiras implementações do gênero. A libavl que consta do repositório do Ubuntu é uma das primeiras versões e não disponibiliza a árvore Red Black, mas a AVL está lá e é tão boa quanto. As versões mais recentes da libavl implementam outras soluções, incluindo a Red Black, e de maneira portável… O que vocẽ faz com árvores AVL, faz do mesmo jeito com Red Black.

Para usar a árvore AVL basta incluir o cabeçalho avl.h (rb.h no case da Red Black Tree), criar uma árvore vazia com a função avl_alloc_tree (ou rb_alloc_tree). Para criar a árvore vocẽ deve fornecer duas funções para manipular os items: Uma de comparação de items e outra de liberação do item. Isso porque cada nó da árvore contém um ponteiro com nome item.

Para inserir um nó na lista você chama a função avl_insert, onde o segundo parâmetro é o ponteiro para o item (não para o nó). Por esse motivo é que a árvore têm que saber como comparar e liberar itens, ao ser criada. Por exemplo, suponha que um item em um nó seja definido assim:

struct var_t
{
  char name[32];
  enum vartype_e type;
  union {
    int integer;
    char *string;
  } value;
};

Assim,  para criar e inserir um item deste tipo na árvore teríamos que fazer:

#include <avl.h>
#include <string.h>
#include <malloc.h>

int compare_items(void *, void *);
void free_item(void *);

struct avl_tree *ptree;

int compare_items(void *pvItem1, *pvItem2)
{
  struct var_t *p1, *p2;

  p1 = (struct var_t *)pItem1;
  p2 = (struct var_t *)pItem2;

  /* Ordena pelo nome da "variável" */
  return strcasecmp(p1->name, p2->name);
}

void free_item(void *pItem)
{
  struct var_t *p;

  p = (struct var_t *)pItem;

  if (p->type == STRING)
    free(p->value.string);

  free(pItem);
}

int main(void)
{
  struct var_t *pVar;
  struct var_t var;
  struct avl_node *pNode;

  /* Cria a árvore AVL */
  ptree = avl_alloc_tree(compare_items, free_item);

  /* Cria um item e o insere na árvore. */
  pVar = (struct var_t *)malloc(sizeof(struct var_t));
  strcpy(pVar->name, "xpto");
  pVar->type = INTEGER;
  pVar->value.integer = 10;
  avl_insert(ptree, pVar);

  /* Cria outro item e o insere na árvore. */
  pVar = (struct var_t *)malloc(sizeof(struct var_t));
  strcpy(pVar->name, "str");
  pVar->type = STRING;
  pVar->value.string = strdup("Uma string qualquer");
  avl_insert(ptree, pVar);

  /* Pesquisa... */
  strcpy(var.name, "xpto");

  pNode = avl_search(ptree, &var);

  if (pNode != NULL)
  {
    pVar = pNode->item;
    printf("Item '%s' found (type: %s) = ",
      pVar->name,
      pVar->type == INTEGER ? "INTEGER" : "STRING");
    switch (pVar->type)
    {
    case INTEGER:
      printf("%d\n", pVar->value.integer); break;
    case STRING:
      puts(pVar->value.string); break;
    }
  }

  /* Libera todos os nós da árvore e a própria árvore! */
  avl_free_tree(ptree);
}

Essa foi um pedaço da implementação que usei no projeto que mencionei no post passado.

Repare que depois que você obtém um ponteiro para um nó com a função avl_search, pode chamar, por exemplo, avl_delete_node para sumir com ele… A vantagem de usar esse esquema “complicado” (não é!) é que sua árvore binária sempre estará balanceada, suas pesquisas serão rápidas (uma árvore com 1 milhão de itens toma menos de 20 iterações para realizar uma pesquisa). Compare isso com o pior caso da implementação de um array e toda essa “complicação”, de repente, fica bem atraente.

E você não tem que sequer saber como uma árvore balanceada funciona! Não é bom isso?

Para baixar a versão mais recente da libavl, clique aqui.

OBS: O shared object da libavl que deve ser distribuído (e que está no repositório do Ubuntu) é chamado libavi1 (tem esse ‘1’ no final). O pacote de desenvolvimento é chamado simplesmente de libavl-dev.

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s