Construa uma árvore de busca binária para as palavras oenology phrenology, campanology, ornithology, ichthyology, limnology, alchemy e astrology usando a ordem alfabética.
Passo 1
O enunciado pede para montar uma árvore de busca binária (BST) contendo as palavras
oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy e astrology
seguindo a ordem alfabética. Numa BST, cada nova palavra é comparada ao nó atual: se for “menor” (alfabeticamente anterior) caminha para a subárvore esquerda; se for “maior”, para a subárvore direita. Vamos inserir as palavras na ordem em que foram dadas.
oenology, phrenology, campanology, ornithology, ichthyology, limnology, alchemy e astrology
seguindo a ordem alfabética. Numa BST, cada nova palavra é comparada ao nó atual: se for “menor” (alfabeticamente anterior) caminha para a subárvore esquerda; se for “maior”, para a subárvore direita. Vamos inserir as palavras na ordem em que foram dadas.
Passo 2
Inserimos a primeira palavra como raiz:
oenology
(árvore só com o nó raiz)
oenology
(árvore só com o nó raiz)
Passo 3
Inserimos phrenology. Comparamos com o nó “oenology”:
“phrenology” > “oenology” ⇒ vai para a subárvore direita.
Agora a árvore é:
“phrenology” > “oenology” ⇒ vai para a subárvore direita.
Agora a árvore é:
oenology
\
phrenology
Passo 4
Inserimos campanology. Comparamos com “oenology”:
“campanology” < “oenology” ⇒ vai para a subárvore esquerda.
“campanology” < “oenology” ⇒ vai para a subárvore esquerda.
oenology
/ \
campanology phrenology
Passo 5
Inserimos ornithology. Comparamos com a raiz:
“ornithology” > “oenology” ⇒ vai para a direita (em phrenology).
Em seguida comparamos com “phrenology”:
“ornithology” < “phrenology” ⇒ vai para a esquerda de phrenology.
“ornithology” > “oenology” ⇒ vai para a direita (em phrenology).
Em seguida comparamos com “phrenology”:
“ornithology” < “phrenology” ⇒ vai para a esquerda de phrenology.
oenology
/ \
campanology phrenology
/
ornithology
Passo 6
Inserimos ichthyology. Comparamos com “oenology”:
“ichthyology” < “oenology” ⇒ vai para a esquerda (em campanology).
Comparamos com “campanology”:
“ichthyology” > “campanology” ⇒ vai para a direita de campanology.
“ichthyology” < “oenology” ⇒ vai para a esquerda (em campanology).
Comparamos com “campanology”:
“ichthyology” > “campanology” ⇒ vai para a direita de campanology.
oenology
/ \
campanology phrenology
\ /
ichthyology ornithology
Passo 7
Inserimos limnology. Caminho:
limnology < oenology ⇒ esquerda em campanology
limnology > campanology ⇒ direita em ichthyology
limnology > ichthyology ⇒ direita de ichthyology
limnology < oenology ⇒ esquerda em campanology
limnology > campanology ⇒ direita em ichthyology
limnology > ichthyology ⇒ direita de ichthyology
oenology
/ \
campanology phrenology
\ /
ichthyology ornithology
\
limnology
Passo 8
Inserimos alchemy. Caminho:
alchemy < oenology ⇒ esquerda em campanology
alchemy < campanology ⇒ esquerda de campanology
alchemy < oenology ⇒ esquerda em campanology
alchemy < campanology ⇒ esquerda de campanology
oenology
/ \
campanology phrenology
/ \ /
alchemy ichthyology ornithology
\
limnology
Passo 9
Inserimos astrology. Caminho:
astrology < oenology ⇒ esquerda em campanology
astrology < campanology ⇒ esquerda em alchemy
astrology > alchemy ⇒ direita de alchemy
astrology < oenology ⇒ esquerda em campanology
astrology < campanology ⇒ esquerda em alchemy
astrology > alchemy ⇒ direita de alchemy
oenology
/ \
campanology phrenology
/ \ /
alchemy ichthyology ornithology
\ \
astrology limnology
Resposta
A árvore de busca binária final, em diagrama ASCII, é:
oenology
/ \
campanology phrenology
/ \ /
alchemy ichthyology ornithology
\ \
astrology limnology