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):
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).
– 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” ( ) → esquerda de “the”
– “brown” ( ) → esquerda de “quick”
– “fox” ( em “brown”) → direita de “brown”
– “jumps” ( em “fox”) → direita de “fox”
– “dog” ( em “fox”) → esquerda de “fox”
– “lazy” ( em “jumps”) → direita de “jumps”
– “over” ( em “quick”) → direita de “quick”
– “quick” (
– “brown” (
– “fox” (
– “jumps” (
– “dog” (
– “lazy” (
– “over” (
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
/
quick the
/
brown over
fox
/
dog jumps
lazy