Considere uma árvore de busca binária tendo como nós os números de 1 até 1000 . Nós procuramos um nó marcado com 363. Qual das seguintes sequências não podem ser os valores dos nodos visitados na busca por 363 ?
(a) 2; 252; 401; 398; 330; 344; 397; 363.
(b)
.
©
.
(d) 2; 399; 387; 219; 266; 382; 381; 278; 363.
(e)
.
(a) 2; 252; 401; 398; 330; 344; 397; 363.
(b)
©
(d) 2; 399; 387; 219; 266; 382; 381; 278; 363.
(e)
Passo 1
Resumo do enunciado: a gente tem uma árvore binária de busca com valores de 1 a 1000 e estamos procurando o valor 363. O caminho de busca deve obedecer às regras de BST, ou seja, em cada nó com chave K, se 363 < K vamos para a subárvore esquerda e se 363 > K vamos para a subárvore direita.
Definição do método: durante a busca a cada nó visitado mantemos dois limites (low e high) que definem o intervalo válido para as chaves seguintes. Inicialmente low = 1 e high = 1000. Ao visitar um nó de valor K verificamos low < K < high. Se K < 363 atualizamos low = K; se K > 363 atualizamos high = K.
Definição do método: durante a busca a cada nó visitado mantemos dois limites (low e high) que definem o intervalo válido para as chaves seguintes. Inicialmente low = 1 e high = 1000. Ao visitar um nó de valor K verificamos low < K < high. Se K < 363 atualizamos low = K; se K > 363 atualizamos high = K.
Passo 2
Análise da sequência (a): 2; 252; 401; 398; 330; 344; 397; 363. Em cada passo 2<363→ low=2; 252<363→ low=252; 401>363→ high=401; 398>363→ high=398; 330<363→ low=330; 344<363→ low=344; 397>363→ high=397; e por fim 363 está entre low=344 e high=397. Tudo bate, (a) é possível.
Passo 3
Análise da sequência (b): 924; 220; 911; 244; 898; 258; 362; 363. Passando por cada valor mantemos low=1, high=1000 e atualizamos conforme 924>363→ high=924; 220<363→ low=220; 911>363→ high=911; 244<363→ low=244; 898>363→ high=898; 258<363→ low=258; 362<363→ low=362; e o 363 final cabe no intervalo (362,898). Logo (b) é possível.
Passo 4
Análise da sequência ©: 925; 202; 911; 240; 912; 245; 363. Após 925>363→ high=925, 202<363→ low=202, 911>363→ high=911, 240<363→ low=240. No quinto nó aparece 912, mas 912>high=911, o que viola o intervalo. Logo © não é possível.
Passo 5
Análise da sequência (d): 2; 399; 387; 219; 266; 382; 381; 278; 363. Aplicando o mesmo método vemos que todos os valores caem nos intervalos atualizados corretamente, então (d) é possível.
Passo 6
Análise da sequência (e): 935; 278; 347; 621; 299; 392; 358; 363. Depois de 935>363→ high=935, 278<363→ low=278, 347<363→ low=347, 621>363→ high=621, chega 299 mas 299<low=347, violando o intervalo. Logo (e) não é possível.
Resposta
As sequências © e (e) não podem ocorrer na busca por 363.