Questão FC266067
Considere a árvore rubro-negra abaixo: Os nós preenchidos com a cor preta representam os vértices pretos da árvore rubro-negra e os demais nós representam os vértices vermelhos. As
Algoritmos e Lógica de Programação
IDECAN · 2019
Considere a árvore rubro-negra abaixo:
Os nós preenchidos com a cor preta representam os vértices pretos da árvore rubro-negra e os demais nós representam os vértices vermelhos.
Assinale a alternativa que contém o percurso em pré-ordem após a inserção de um nó contendo o valor 21.
- 20, 10, 30, 35, 23, 25, 21
- 20, 10, 30, 23, 25, 21, 35
- 20, 10, 23, 21, 30, 25, 35
- 20, 10, 23, 30, 25, 35, 21
- 20, 10, 30, 23, 21, 25, 35
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
Ao inserir 21, percorremos a árvore: é maior que 20 (vai à direita), menor que 30 (à esquerda), menor que 25 (à esquerda) e menor que 23, ficando inicialmente como filho esquerdo de 23 como um nó vermelho.
Para restaurar as propriedades da Árvore Rubro-Negra, aplica‑se o procedimento de correção (recolorações e, se necessário, rotações). O ajuste resulta em 30 tendo 23 como filho esquerdo e 35 como filho direito; 23 fica com 21 à esquerda e 25 à direita.
O percurso em pré-ordem visita: raiz, subárvore esquerda e depois subárvore direita. Assim, visitamos 20 (raiz), 10 (esquerda), depois a subárvore direita começando em 30, em seguida 23, seus filhos 21 e 25, e por fim 35.
Sequência resultante: 20, 10, 30, 23, 21, 25, 35.
Conteúdo do catálogo FC Concursos · Atualizado em