Supongamos que tenemos números entre 1 y 1000 en un árbol de búsqueda binaria y queremos buscar el número 364. ¿Cuál de las siguientes secuencias no podría ser la secuencia de Nodes examinada?
(A) 925, 221, 912, 245, 899, 259, 363, 364
(B) 3, 400, 388, 220, 267, 383, 382, 279, 364
(C) 926, 203, 912, 241, 913 , 246, 364
(D) 3, 253, 402, 399, 331, 345, 398, 364
Respuesta: (C)
Explicación: Tenemos que encontrar 364 en BST:
- En la primera opción, 925 es el Node raíz, nuestra clave es menor que 925, por lo que optamos por BST izquierdo. El siguiente Node es 221 → 912 → 245 → 899 → 259 → 363 → 364 respectivamente.
- En la segunda opción 3 es el Node raíz, vamos por BST correcto, es decir, 400 → 388 → 220 → 267 → 383 → 382 → 279 → 364 respectivamente.
- En la tercera opción, 926 es el Node raíz, vamos a BST izquierdo, es decir, 203 → 912 → 241, la siguiente clave es 913, no podemos ir a 913 después de 241 porque ya estamos en BST izquierdo de 912, nuestra clave seguramente estará en BST izquierdo de 912. Esta opción es incorrecta.
- En la cuarta opción 3 es el Node raíz, vamos por BST correcto, es decir, 253 → 402 → 399 → 331 → 345 → 398 → 364.
Entonces, la opción (C) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA