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.
