Re: Dúvida de Patricia Tries

["Alexandre Murakami" <ale_murakami@bol.com.br>]

Oi Rubens

Eu não sei se é erro de código. Eu pensei nisso, mas a função insertR()
recebe dois links como parâmetro, h e p. Pelo que eu entendi, p aponta
sempre para o pai de h. Os valores que são inicialmente passados são h =
head -> l e p = head. Aí, se head apontar para o primeiro item, não sei que
valores devem ser passados. Se passar h = head e p = head, ele não funciona.
Além disso, na função STinit(), ele aloca em head um item vazio. Essa parte
de Patricia-trie está realmente estranha... AAAAAAAAARRRRRRRRRGH!!! :-)

Aliás, tem outra coisa que não entendi. A função STinsert() faz uma busca
antes de inserir um elemento na árvore. Depois, ele procura o primeiro bit
diferente entre o item encontrado e o item a ser inserido. Mas se a árvore
estiver vazia, nenhum item é encontrado. O que acontece então? A função
digit() retorna o que para um item vazio?

Abraços
Alexandre Murakami

----- Original Message -----
From: Rubens Altimari <rubens@bcc2000.net>
To: <yoshi-mac323@ime.usp.br>
Sent: Wednesday, June 20, 2001 8:05 PM
Subject: Re: Dúvida de Patricia Tries


Acesso pelo menor preço do mercado! R$ 14,90 nos 3 primeiros meses!
ASSINE AGORA! http://www.bol.com.br/acessobol/


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