Para eliminar un nodo en el árbol binario, debemos buscar el nodo. Eso es posible en un mínimo de O (log N) y max O (N). Dependiendo del nodo, tenemos que reorganizar los punteros. ¿Cómo calculamos la complejidad del tiempo de eso?Cuál es la complejidad de tiempo de eliminar un nodo en un árbol binario
La mayor parte de la complejidad es la búsqueda del nodo. Una vez que se ha encontrado, siempre que se conserve el nodo principal, solo quedan unas pocas asignaciones más para eliminar el nodo. Entonces es un orden constante.
Eso depende de cómo se borre. La forma más común consiste en encontrar el sucesor del nodo y luego reemplazar el nodo con ese sucesor. Esto se puede hacer en O (h), donde h es la altura del árbol. En el peor de los casos, esto es O (n), pero en un árbol equilibrado es el caso más desfavorable O (lg n).
¿Dónde obtiene el "peor tiempo de búsqueda como max O (N)"? Eso nunca debería pasar en un BST. En el peor de los casos, debería ser max O (h) para búsqueda y eliminación, donde 'h' es la altura del árbol. Vea esto helpful article.
O (h) puede ser O (n) en un árbol patológicamente degenerado. – templatetypedef
Sí mejor la complejidad caso es O (log n) (cuando perfectamente equilibrado) y
peor de los casos la complejidad es O (n)
1 - 2 - 3 - 4
Pero el principal problema con la supresión BST (Hibbard Deletion) es que no es simétrico. Después de muchas inserciones y eliminaciones, BST pierde su equilibrio. Los investigadores demostraron que después de una cantidad suficientemente larga de insertar al azar y eliminar la altura del árbol se convierte en sqrt (n). entonces ahora cada operación (búsqueda, inserción, eliminación) tomará sqrt (n) tiempo que no es bueno en comparación con O (logn).
Esto es un problema abierto de larga duración (alrededor de 50 años) para una eliminación simétrica eficiente para BST. para árbol equilibrado garantizado, tenemos que usar RedBlack Tree etc.
+1, Bonito y conciso. –