Re: Dúvida de Patricia Tries

["Rubens Altimari" <rubens@bcc2000.net>]

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