Overview
As estruturas de dados representam uma vantagem crucial na programação de computadores, e saber quando e porque usá-los é muito importante.
Este artigo é uma breve introdução à estrutura de dados trie (pronuncia-se “tentar”), sua implementação e análise de complexidade.
Trie
Uma trie é uma estrutura de dados discreta que não é bem conhecida ou amplamente mencionada em cursos típicos de algoritmos, mas, no entanto, uma importante.
Uma trie (também conhecida como árvore digital) e às vezes até mesmo uma árvore de radix ou prefixos (pois eles podem ser pesquisados por prefixos), é uma estrutura de árvore ordenada, que tira vantagem das chaves que armazena – geralmente strings.
A posição de um nó na árvore define a chave com a qual esse nó está associado, o que torna as tentativas diferentes em comparação com as árvores de busca binária, nas quais um nó armazena uma chave que corresponde apenas a esse nó.
Todos os descendentes de um nó têm um prefixo comum de uma String associada a esse nó, enquanto a raiz está associada a uma String vazia.
Aqui temos uma pré-visualização do TrieNode que estaremos usando em nossa implementação do Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Pode haver casos em que uma trie é uma árvore de busca binária, mas em geral, estes são diferentes. Tanto as árvores de busca binária quanto as tentativas são árvores, mas cada nó nas árvores de busca binária sempre tem dois filhos, enquanto os nós das tentativas, por outro lado, podem ter mais.
Em um trie, cada nó (exceto o nó raiz) armazena um caracter ou um dígito. Ao atravessar o trie do nó raiz para um determinado nó, um prefixo comum de caracteres ou dígitos pode ser formado, que é compartilhado por outros ramos do trie também.
Ao atravessar o trie de um nó folha para o nó raiz, uma String ou uma seqüência de dígitos pode ser formada.
Aqui está a classe Trie, que representa uma implementação da estrutura de dados da trie:
public class Trie { private TrieNode root; //...}Operações Comuns
Agora, vamos ver como implementar operações básicas.
3.1. Inserindo Elementos
A primeira operação que vamos descrever é a inserção de novos nós.
Antes de iniciarmos a implementação, é importante entender o algoritmo:
- Definir um nó atual como nó raiz
- Definir a letra atual como primeira letra da palavra
- Se o nó atual já tem uma referência existente à letra atual (através de um dos elementos no campo “filhos”), então defina o nó atual para aquele nó referenciado. Caso contrário, crie um novo nó, defina a letra igual à letra atual e também inicialize o nó atual para esse novo nó
- Repetir o passo 3 até que a chave seja atravessada
A complexidade dessa operação é O(n), onde n representa o tamanho da chave.
Aqui está a implementação deste algoritmo:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Agora vamos ver como podemos usar este método para inserir novos elementos numa trie:
private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}Podemos testar essa trie já foi preenchida com novos nós do seguinte teste:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Finding Elements
>
Vamos agora adicionar um método para verificar se um determinado elemento já está presente em uma trie:
- Criar filhos da raiz
- Iterar através de cada caractere da String
- Verifica se esse caractere já faz parte de uma sub-trie. Se ele não estiver presente em nenhuma parte da triagem, então pare a busca e retorne falso
- Repita o segundo e o terceiro passo até que não haja mais nenhum caractere na String. Se o fim da String for atingido, retorne true
A complexidade deste algoritmo é O(n), onde n representa o comprimento da chave.
A implementação Java pode parecer:
public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}E em acção:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Eliminando um elemento
Para além de inserir e encontrar um elemento, é óbvio que também precisamos de ser capazes de eliminar elementos.
Para o processo de apagar, precisamos seguir os passos:
- Verifica se este elemento já faz parte do trie
- Se o elemento for encontrado, então remove-o do trie
A complexidade deste algoritmo é O(n), onde n representa o comprimento da chave.
Vejamos rapidamente a implementação:
public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}E em acção:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Conclusão
Neste artigo, vimos uma breve introdução à estrutura de dados da trie e suas operações mais comuns e sua implementação.