Apresente um exemplo para mostrar que a estrutura de uma Trie não depende da ordem de entrada das chaves.
Passo 1
Beleza, o exercício tá pedindo para a gente mostrar com um exemplo que, não importa a ordem em que você insere as palavras numa Trie, a estrutura final dela vai ser a mesma. O assunto aqui é “Trie” (ou árvore de prefixos). Pra resolver, a gente vai lembrar o que é uma Trie, escolher um conjunto de chaves (palavras) e dois pedidos de inserção em ordens diferentes. Aí a gente constrói as Tries passo a passo e vê que o resultado é idêntico.
Passo 2
Primeiro, recapitular rapidinho o que é uma Trie.
- Uma Trie começa num nó raiz vazio.
- Cada aresta saiu de um nó carrega um caractere.
- Caminhando da raiz até um nó qualquer, a sequência de caracteres forma um prefixo (e, se marcarmos esse nó como final, uma palavra completa).
- O ponto chave: diferentes ramos compartilham prefixos em comum.
Passo 3
Vamos escolher um conjunto pequeno de palavras para ficar claro:
K = {“car”, “cat”, “dog”}
E duas ordens de inserção:
Ordem A: car → cat → dog
Ordem B: dog → cat → car
K = {“car”, “cat”, “dog”}
E duas ordens de inserção:
Ordem A: car → cat → dog
Ordem B: dog → cat → car
Agora vamos construir a Trie na Ordem A.
Passo 4
Construindo a Trie (Ordem A):
- Inserir “car”:
- Da raiz, cria nó para ‘c’, depois para ‘a’, depois para ‘r’ (marcamos esse nó como fim).
- Inserir “cat”:
- Da raiz ‘c’ já existe, desce pra ‘a’ (já existe), então cria um filho ‘t’ no nó ‘a’ e marca esse ‘t’ como fim.
- Inserir “dog”:
- Da raiz não tem ‘d’, cria nó ‘d’, depois ‘o’, depois ‘g’ e marca esse ‘g’ como fim.
O resultado é:
raiz
├─ c
│ └─ a
│ ├─ r*
│ └─ t*
└─ d
└─ o
└─ g*
(o asterisco indica nó de fim de palavra)
raiz
├─ c
│ └─ a
│ ├─ r*
│ └─ t*
└─ d
└─ o
└─ g*
(o asterisco indica nó de fim de palavra)
Passo 5
Agora a mesma coisa na Ordem B.
Ordem B: dog → cat → car
- Inserir “dog”: cria d → o → g*.
- Inserir “cat”: da raiz cria c → a → t*.
- Inserir “car”: da raiz ‘c’ já está, desce para ‘a’, já está, então cria ‘r’ e marca ‘r’ como fim.
O desenho final fica exatamente igual:
raiz
├─ c
│ └─ a
│ ├─ r*
│ └─ t*
└─ d
└─ o
└─ g*
raiz
├─ c
│ └─ a
│ ├─ r*
│ └─ t*
└─ d
└─ o
└─ g*
Resposta
Independente da ordem em que a gente inseriu {“car”, “cat”, “dog”}, a Trie resultante teve exatamente os mesmos nós e arestas. Isso mostra que a estrutura de uma Trie não depende da ordem de entrada das chaves.