Re:_Dúvida_de_Patricia_Tries

[Alexandre Murakami <ale_murakami@yahoo.com.br>]

Oi gente

Eu acho (Deus é pai!) que o Patricia-trie funciona com
essa função aqui:


void STinsert(Item item)
  { int i;
    Key v = key(item);

    /* se a árvore estiver vazia */
    if (head->l == head)
      {
        link x = NEW(item, 0, 0, nbits(v));
        x->l = x->r = x;
        head->l = x;
        return;
      }

    Key t = key(searchR(head->l, v, -1));
    if (v == t) return;
    for (i = 0; digit(v, i) == digit(t, i); i++);
    head->l = insertR(head->l, item, i, head);
  }

Aqui, o head continua sendo um nó vazio, com o valor
do bit -1, head->l apontando para a árvore e head->r
sem função. Mas o primeiro nó inserido tem bit =
número de bits do item (4 bits no exemplo do livro) e
os dois links apontando pra ele mesmo (é o que faz a
parte nova). Acho que assim faz sentido.

Abraços
Alexandre Murakami


--- Rubens Altimari <rubens@bcc2000.net> escreveu: >
Acesso pelo menor preço do mercado! R$ 14,90 nos 3
> primeiros meses!
> ASSINE AGORA! http://www.bol.com.br/acessobol/
> 
> 
> >Não não, Rubens, não é erro de código não.
> 
>     Você tem toda a razão. Parando para fazer
> direitinho, realmente está certo. Acho que a maior
> diferença, comparando com a maioria das outras
> estruturas, é que neste caso o head não é um link, é
> um nodo! E, comparando com a trie comum, é o único
> nodo extra, sem dados (na trie e nas multiway-tries
> tem mais de um).
> 
>     Curioso, porém, aquilo que eu havia comentado: a
> versão C++ de STsearch chama searchR com head, não
> head->l. Mas, depois desta, eu não digo mais nada:
> estas Patricias dão muito trabalho, precisa olhar
> nos mínimos detalhes... ;-]
> 
>     Obrigado pelo toque,
> 
> Rubens
> 
> 
> 
> 
>  


_______________________________________________________________________________________________
Yahoo! GeoCities
Tenha seu lugar na Web. Construa hoje mesmo sua home page no Yahoo! GeoCites. É fácil e grátis!
http://br.geocities.yahoo.com/