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
Agora vamos construir a Trie na Ordem A.

Passo 4

Construindo a Trie (Ordem A):
  1. Inserir “car”:
    • Da raiz, cria nó para ‘c’, depois para ‘a’, depois para ‘r’ (marcamos esse nó como fim).
  2. 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.
  3. 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)

Passo 5

Agora a mesma coisa na Ordem B.
Ordem B: dog → cat → car
  1. Inserir “dog”: cria d → o → g*.
  2. Inserir “cat”: da raiz cria c → a → t*.
  3. 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*

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.

Exercícios relacionados