Busca Digital

Motivação

Chaves possuem tamanhos diferentes. (E.g.: sentenças em um texto na Língua Portuguesa).
Custo da busca não depende do total de chaves armazenadas.

Árvore m-ária, onde m indica o tamanho do alfabeto das chaves.
 

chaves foi fora fui vai ver vi viu vimos veremos

Busca em Árvores Digitais

struct SNoDig
{
     SNoDig * Filhos[m];
}

bool BuscaDig(char * chave)
{
     int i = 0;
     bool achou = false;
     SNoDig * no;
     no = raiz;

     while(i < strlen(chave) && no != NULL)
     {
           no = no->Filhos[ PosicaoDoSimboloNoVetor(chave[i]) ];
           ++i;
     }
     if( no != NULL ) return(true);
     else return(false);
}

int PosicaoDoSimboloNoVetor( char chave); /* Retorno posicao do ponteiro no vetor */
{
       return(chave-'a'); /* Caso o alfabeto seja a,b,c...,z */
}

Problema do Prefixo: Todos os prefixos de uma chave contida em uma árvore digital também estão contidos (ver algoritmo de busca (acima)) . Uma solução: marcar explicitamente os nós que contém uma chave (na figura 1 usamos asteriscos). As folhas não precisam ser marcadas.

Exercício: Modificar algoritmo BuscaDig para resolver problema do prefixo.

Inserção em Árvores Digitais

/* Busca deve ser alterada para retornar a seguinte estrutura: */
struct ResBusca
{
    SNo * No;  /* Ponteiro para o nó correspondente ao último caracter representado na árvore */
    int Pos; /* Posição, na chave, do último caracter representado na árvore */
}

void Insere(char * chave)
{
    int i;
    ResBusca Res;
    SNoDig * No;
    SNoDig * PontoIns;

    Res = Busca(chave);
    i = Res.Pos;
    PontoIns = Res.No;
    while(chave[i] != '\0')
    {
        No = new SNoDig;
        InicializaComNullOsPonteiros(No);
        PontoIns->Filhos[  PosicaoDoSimboloNoVetor( chave[i] ) ] = No;
        PontoIns = No;
    }
}
 

Árvore Digital Binária (Digital Tree)

Quando o alfabeto possui apenas 2 símbolos (m=2). Geralmente, 0 e 1.
 

Chaves 000 0101 110 111 1 01

Árvore Binária de Prefixo

Apenas as folhas são associadas a chaves.

Árvore PATRICIA