Usando a ordem alfabética, construa uma árvore de busca binária para as palavras na sentença “The quick brown fox jumps over the lazy dog.”

Passo 1

O enunciado pede para construir uma árvore de busca binária (BST) cujos nós são as palavras da frase “The quick brown fox jumps over the lazy dog.”, usando a ordem alfabética para decidir se cada palavra vai para a subárvore esquerda (se for “menor” no alfabético) ou para a subárvore direita (se for “maior” ou igual, tratando duplicatas indo sempre para a direita).

Passo 2

Primeiro, extraímos e normalizamos as palavras (tudo em minúsculas): \text{[the, quick, brown, fox, jumps, over, the, lazy, dog]} Regra de inserção em BST (lexicográfica, ignorando maiúsculas/minúsculas):
– Se a palavra nova < palavra do nó, insere na subárvore esquerda.
– Se a palavra nova ≥ palavra do nó, insere na subárvore direita (isso trata duplicatas).

Passo 3

Inserimos a primeira palavra “the” como raiz da árvore.

Passo 4

Inserimos em sequência as palavras menores que “the”:
– “quick” ( q<t) → esquerda de “the”
– “brown” ( b<q) → esquerda de “quick”
– “fox” ( f>b em “brown”) → direita de “brown”
– “jumps” ( j>f em “fox”) → direita de “fox”
– “dog” ( d<f em “fox”) → esquerda de “fox”
– “lazy” ( l>j em “jumps”) → direita de “jumps”
– “over” ( o>q em “quick”) → direita de “quick”
Após estas inserções, a subárvore esquerda de “the” fica assim:
 quick
 / \
 brown over
 \
 fox
 / \
 dog jumps
 \
 lazy

Passo 5

Por fim, inserimos a segunda ocorrência de “the” (igual à raiz), que vai para a subárvore direita da raiz.

Resposta

A BST final é:
the
/
quick the
/
brown over

fox
/
dog jumps

lazy

Exercícios de Livros Relacionados