As a´rvores bina´rias que sera~o consideradas nesta sec¸a~o te^m uma propriedade fundamental: o valor associado a` raiz e´ sempre maior que o valor...

As a´rvores bina´rias que sera~o consideradas nesta sec¸a~o te^m uma propriedade fundamental: o valor associado a` raiz e´ sempre maior que o valor associado a qualquer no´ da sub-a´rvore a` esquerda (sae), e e´ sempre menor que o valor associado a qualquer no´ da sub-a´rvore a` direita (sad). Essa propriedade garante que, quando a a´rvore e´ percorrida em ordem sime´trica (sae - raiz - sad), os valores sa~o encontrados em ordem crescente. Considere a árvore binária de busca criada com as inserções: 10, 20, 1, 15, 13, 18, 12. Sobre a remoção do vértice 13, assinale a alternativa correta. Selecione uma alternativa: a) Para remover o vértice 13, o primeiro passo é buscar o vértice 13. Comparamos 13 com 10. O valor 13 é maior, então visitamos o filho direito de 10, que é o vértice 20. O valor 13 é menor que 20, então visitamos o filho esquerdo de 20, que é o vértice 15. O valor 13 é menor que 15, então visitamos o filho esquerdo de 15, que é 13, o valor buscado. Segundo passo é verificar o tipo de vértice: folha, pai de 1 filho, pai de 2 filhos. O terceiro passo é aplicar o algoritmo para remover vértice que é pai de 1 filho: o “neto” passa a ser filho do “avô” e o avô passa a ser pai do neto. b) Para remover o vértice 13, o primeiro passo é buscar o vértice 13. Comparamos 13 com 10. O valor 13 é maior então visitamos o filho direito de 10, que é o vértice 20. O valor 13 é menor que 20, então visitamos o filho esquerdo de 20, que é o vértice 15. O valor 13 é menor que 15, então visitamos o filho esquerdo de 15, que é o 13, valor buscado. Segundo passo é verificar o tipo de vértice: folha, pai de 1 filho, pai de 2 filhos. O terceiro passo é aplicar o algoritmo para remover vértice que é pai de 1 filho. O terceiro passo é aplicar o algoritmo para remover vértice que é pai de 1 filho: o “neto” passa a ser filho do “avô” e o avô passa a ser pai do neto. Importante atualizar o valor do pai de 13, que não pode ser mais o 15. c) Para remover o vértice 13, o primeiro passo é buscar o vértice 13. Comparamos 13 com 10. O valor 13 é maior então visitamos o filho direito de 10, que é o vértice 20. O valor 13 é menor que 20, então visitamos o filho esquerdo de 20, que é o vértice 15. O valor 13 é menor que 15, então visitamos o filho esquerdo de 15, que é o valor buscado. Segundo passo é verificar o tipo de vértice: folha, pai de 1 filho ou pai de 2 filhos. O terceiro passo é aplicar o algoritmo para remover vértice que é pai de 2 filhos no vértice 15. d) Para remover o vértice 13, o primeiro passo é buscar o vértice 13. Comparamos 13 com 10. O valor 13 é maior então visitamos o filho direito de 10, que é o vértice 20. O valor 13 é menor que 20, então visitamos o filho esquerdo de 20, que é o vértice 15. O valor 13 é menor que 15, então visitamos o filho esquerdo de 15, que é o valor buscado. Segundo passo é verificar o tipo de vértice: folha, pai de 1 filho, pai de 2 filhos. O terceiro passo é aplicar o algoritmo para remover vértice que é vértice-folha. Ou seja, desvincular 15 de 13 e 13 de 15, atualizando os valores do filho esquerdo de 15, que não é mais o 13, e atualizar o valor do seu pai, que não é mais o 15. e) Para remover o vértice 13, o primeiro passo é buscar o vértice 13. Procuramos primeiramente na subárvore do lado esquerdo da raiz. Se não encontramos, procuramos na subárvore do lado direito da raiz. Ou seja, visitamos a raiz, depois 1, depois 20, 15, 13. Encontramos. Então, removemos o vértice 13, desvinculando-o da árvore.