Re: Dúvida de Patricia Tries

[Giuliano Mega <megag@terra.com.br>]

Não não, Rubens, não é erro de código não. O que ocorre é o seguinte: o Patricia trie termina uma search quando detecta um link para cima; ou seja, quando o contador de bits da chave de cima for maior que o contador de bits da chave atual. Veja o que ele faz:

NULLItem = 00000
b = -1

Quando ele associa isso ao nó da cabeça, o que ele faz é criar um nó que invariavelmente será detectado como um link para cima. Como você sempre insere à esquerda todo e qualquer nó inserido irá ficar à esquerda da cabeça e o link para cima do nó extremo esquerdo irá apontar para alguma coisa (a cabeça).
Dessa forma, se vc der uma busca em 00000 vc encontra a cabeça e não "o nada".

                               NULL(-1)
                              /   /
                             /   /
                            /  A(4)
                           /___/\__\

Entenderam?
Realmente é um tanto bizarro, mas é uma maneira interessante de eliminar um caso especial onde a Patricia teria um null link (Patricias não têm null links).

Rubens Altimari wrote:

> Oi, Alexandre:
>
> >Eu não entendi bem algumas coisas da implementação do
> Sedgewick de Patricia Tries. Na função STinsert()
> (Program 15.5), está a seguinte linha:
>
> head->l = insertR( head->l, ...);
>
> >Por que a inserção é feita em uma das ramificações da
> raiz? Pelo que eu entendi, o head é um elemento vazio,
> com bit = -1, o ponteiro r não é usado e o ponteiro l
> aponta para a árvore. É isso?
>
>     Não sei se alguém mais já respondeu, ou se isto é "notícia velha". Mas acho que é um erro do código. Se, em vez de usar head->l, você usar head, fica tudo certo, a meu ver. No caso de uma árvore vazia "tanto faz", porque o ->l aponta para o próprio head, mas em uma árvore cheia não daria certo.
>
>     Acho que o próximo programa, 15.5, também está errado, mas não tive paciência para testar direitinho. Procurei na errata do Sedgewick, e não encontrei menção a isto, mas notei que o código em C++, do Algorithms em C++, usa head em vez de head->l, como eu comentei acima. Já o programa 15.5 está igual.
>
> Rubens