CGU-NET | UGC-NET CS 2017 2 de diciembre | Pregunta 22

Los siguientes números se insertan en un árbol de búsqueda binario vacío en el orden indicado:

10, 1, 3, 5, 15, 12, 16

¿Cuál es la altura del árbol de búsqueda binaria?
(A) 3
(B) 4
(C) 5
(D) 6

Respuesta: (A)
Explicación: Tenemos 10, 1, 3, 5, 15, 12, 16 claves y tenemos que insertar estas claves en una búsqueda binaria árbol (BST):

• Paso 1. Inserte 10 en el BST.
• Paso 2. Compara 1 con 10 es menor que 10 Entonces quedará niño por 10.
• Paso 3. Ahora compare la siguiente clave, es decir, 3 a 10, es menor que 10, estará en el subárbol izquierdo de 10. Ahora compare 3 con el siguiente Node, es decir, 1, 3 es mayor que 1, por lo que será el hijo derecho del Node 1.
• Paso 4. La siguiente tecla es 5, siga el mismo procedimiento que en el paso anterior. 5 será el hijo derecho del Node 3.
• Paso-5. La clave 15 se comparará primero con el Node principal y es mayor que 10, por lo que será el elemento secundario derecho del Node 10.
• Paso-6. La clave 12 se comparará con el Node principal primero, es mayor, por lo que la siguiente comparación será con el hijo derecho del Node principal, es decir, 15, ahora 12 es menor que 15, por lo que 12 será el Node secundario 15.
• Paso-7. Ahora, la última clave 16 se comparará primero con el Node principal, es mayor que 10, por lo que la comparación se desplazará al hijo derecho de 10, es decir, 15 y la clave 16 es mayor que 15 también, por lo que 16 será el hijo derecho del Node 15.

Aquí está el BST construido:


Este árbol tiene 4 niveles y la altura del árbol es nivel – 1 Entonces la altura de este árbol será 4-1 = 3.

Entonces, la opción (A) es correcta.

Cuestionario de esta pregunta