PUERTA | PUERTA CS 2013 | Pregunta 7

¿Cuál de los siguientes es el límite superior más estrecho que representa la complejidad temporal de insertar un objeto en un árbol de búsqueda binaria de n Nodes?
(A) O(1)
(B) O(Logn)
(C) O(n)
(D) O(nLogn)

Respuesta: (C)
Explicación: Para insertar un elemento, primero debemos buscar su lugar. La operación de búsqueda puede tomar O(n) para un árbol sesgado como el siguiente.

To insert 50, we will have to traverse all nodes.
        10
         \
          20
            \
             30
               \
                40

Cuestionario de esta pregunta