Questões 5 e 6.

         5) A árvore de pesquisa TRIE, também conhecida como árvore digital ou árvore de prefixos, é uma estrutura de dados construída a partir dos caracteres da string que define uma chave, o que permite usá-los no processo de busca do valor desejado, seja um valor que a chave guarda, que é armazenado no nó referente ao último caractere da chave, ou uma palavra.

            É possível implementar a árvore por meio de duas estruturas básicas: array e variáveis dinâmicas.

            Trie estática

Implementada por meio de array. Contém uma matriz entre números (colunas) e letras (linhas). Ex.:

	1	2	3	4	5	6	...	...
a	2
b		3
c			abc
d
e		aedo	abert
....

Exemplo do funcionamento dessa implementação:

Adicionando a palavra aedo, colocamos ela na posição 1-a a princípio, pois ela começa com a letra a. Posteriormente, adicionando abert, observamos que ocorreu um conflito entre aedo e abert, pois ambas começam com a mesma letra. Para contornar essa situação, adicionamos uma nova coluna, e movemos ambas as palavras para ele, onde a posição de cada string será definida pela SEGUNDA letra da palavra, portanto essa segunda coluna irá conter todas as palavras que começam com a e não colidem com a posição de nenhuma outra. A antiga posição irá receber um apontador para a coluna que recebeu as palavras.

Para reforçar, ao adicionarmos abc observamos uma colisão com abert, portanto criamos uma nova coluna, colocamos um ponteiro na antiga posição de abert para a nova coluna, e transferimos ambas as palavras, que serão posicionadas conforme o seu TERCEIRO caractere, portanto a coluna 3 irá conter todas as palavras que começam com ab e que não colidem com nenhuma outra.

Podemos observar que não é uma boa forma de implementação, pois o número de colunas criados seria tão grande quanto as combinações possíveis de todos os caracteres considerados.

            Trie dinâmica

                                                                                   

Nessa implementação, o primeiro caractere da primeira palavra será a raiz da árvore e sua implementação responderá as seguintes regras: Cada nó “vertical/ esquerdo” representará os filhos/próximos caracteres da palavra inserida, ou seja, ao inserir BABY, teremos a estrutura B-A-B-Y, onde cada letra é conectada pelo nó esquerdo do nó pai. O nó direito corresponde a um próximo valor, o que leva a outra palavra que começa com um caractere diferente não. Sendo uma árvore binária ela segue as demais regras referentes a sua própria natureza.

Observe que, ao inserir uma palavra com prefixos semelhantes, como por exemplo BOX, é necessário fazer um ajuste na inserção, para manter a composição da estrutura. A inserção funciona da seguinte maneira:

I - Compara o primeiro caractere com a raiz, se não for igual segue a direita até encontrar um igual (1) ou até encontrar um apontador NULL (2), caso (1) siga para o passo II, caso (2) insira o caractere a direita do último nó verificado e prossiga com a inserção dos demais caracteres, com respectivos nós para cada um, verticalmente usando o filho esquerdo de cada nó inserido.

II – Ao encontrar um valor igual, comparamos o segundo caractere da string a ser inserida com o caractere do nó esquerdo, se for igual, prosseguimos a busca comparando o terceiro caractere com o filho esquerdo do nó anterior usado na comparação, e assim sucessivamente. Caso todo os caracteres forem iguais, não há necessidade de inserir a palavra, porém se a busca chegou num nó “vertical” igual ao valor do respectivo caractere na string e sem filho a esquerda, adicionamos “verticalmente” o restante da string, ou seja, inserimos os caracteres restantes da palavra a esquerda de cada nó inserido.

III – Caso no meio da busca dos caracteres semelhantes, após n caracteres iguais um não for semelhante, inserimos o próximo caractere da palavra a direita de do nó não semelhante, caso a direita esteja ocupada, percorremos todos os nós direitos dos filhos direitos até encontrar um ponteiro nulo e adicionamos a respectiva letra, por fim, adicionamos o restante da palavra verticalmente.

Exemplo: Adicionar BAD na figura acima. Separamos BAD em B-A-D, comparamos B com a raiz da árvore, que por coincidência é B, avançamos para o nó esquerdo da raiz ne1. Comparamos A com o valor em ne1, que é igual, então avançamos para o nó esquerdo de ne1, ne2, e comparamos D com o valor desse nó. Como o valor é diferente percorremos para direita de ne2, nd2, que é vazio, portanto adicionamos as letras restantes, que no caso é somente D.

Árvore de N Nós filhos para cada nó

                                 

        

           Uma das implementações possíveis é usando uma árvore em que cada nó tem N filhos, sendo N o número de caracteres do alfabeto utilizado.

            Listas de Palavras Separadas por tamanho

            Para otimizar o processo de busca de uma trie bem construída podemos criar um array ou uma lista encadeada em que cada índice da estrutura indica o tamanho de todas as palavras contidas na posição. Basicamente, na implementação cada posição irá conter uma trie, seja implementada por meio de variáveis dinâmicas ou não, em que cada palavra tem no total i caracteres, sendo i o índice da posição da raiz no array ou lista encadeada.

             6)  Em um arquivo, sendo um campo para o nó e outro para o endereço no arquivo, podendo ter acesso direto ao arquivo que mantém as informações. São mantidas em arquivos devido à grande quantidade de informações que precisam ser guardadas.