Árvore ternária de busca

Árvore ternária de busca
Tipo	Árvore
Complexidade de Tempo em Notação big O
Algoritimo Caso Médio Pior Caso Busca O(log n) O(n) Inserção O(log n) O(n) Remoção O(log n) O(n)

Em ciência da computação, um árvore ternária de busca é um tipo de trie (às vezes chamado de árvore de prefixos), onde os nós são organizados em uma forma semelhante a uma árvore de busca binária, mas com até três filhos, em vez de apenas dois como em uma árvore binária. Assim como outras tries, uma árvore ternária de busca pode ser usada como um mapa associativo com melhores capacidades para a busca em strings. No entanto, árvore ternária de busca são mais eficientes em relação às outras tries, quando se fala em custo de velocidade. Suas aplicações mais comuns incluem a verificação ortográfica e auto-complemento.

Descrição

Cada nó da árvore ternária de busca armazena um único caractere, um objeto (ou um ponteiro para um objeto, dependendo da implementação), e referências para os seus três filhos convencionalmente chamados filho menor, filho igual, e filho maior, que também podem ser chamadas, respectivamente, como meio, menor e maior.^[1] Um nó também pode ter um ponteiro para o nó seu nó pai, bem como um indicador para saber se o nó marca o fim de uma palavra.^[2] O ponteiro filhoMenor deve apontar para um nó cujo caractere é menor que o nó atual. A ponteiro filhoMaior deve apontar para um nó cujo caractere é maior do que o nó atual.^[1] O filhoIgual aponta para o próximo caractere da palavra.

A figura abaixo mostra um exemplo dessa árvore com as sequências de caracteres em inglês "as", "at", "cup", "cute", "he", "i" e "us":

          c
        / | \
       a  u  h
       |  |  | \
       t  t  e  u
      /  /|    /|
     s  p e   i s

Como em outros tries, cada nó em uma árvore ternária de busca representa um prefixo de cadeias de caracteres armazenadas. Todas as cadeias na subárvore do meio de um nó começam com esse prefixo.

Usos

Árvores ternárias de busca podem ser utilizados para resolver muitos problemas em que um grande número de sequências de caracteres devem ser armazenados e recuperados em uma ordem arbitrária. Alguns dos mais comuns são:

• A qualquer momento uma trie pode ser usada, mas uma estrutura que consome menos memória é o preferível.^[1]
• Uma estrutura de dados rápida e que exige pouco espaço, para mapeamento strings para outros dados.^[3]
• Para implementar auto-complemento.^[2]
• Para verificação ortográfica.^[4]
• Para a procura do vizinho mais próximo (dos quais a verificação ortográfica é um caso).^[1]
• No lugar de uma tabela de hash.^[4]

Ver também

• Trie
• Árvore binária de busca
• Tabela Hash

Referências

1. «Ternary Search Trees». Dr. Dobbs 
2. «Efficient auto-complete with a ternary search tree» 
3. Wrobel, Lukasz. «Ternary Search Tree» 
4. «Plant your data in a ternary search tree» 

Ligações externas

• Ternary Search Trees página com documentos (por Jon Bentley e Robert Sedgewick) sobre árvores ternárias de pesquisa e algoritmos para "ordenar e procurar strings"
• Ternary Search Trees – um vídeo de Robert Sedgewick
• TST.java.html Implementação em Java de uma TST por Robert Sedgewick e Kevin Wayne