Trade-offs

Borrado perezoso

Algunas implementaciones no borran el nodo: lo marcan como borrado y lo saltan en las búsquedas. Se limpian todos de vez en cuando.

Una implementación de árbol no borra los nodos: los marca como borrados, los salta en las búsquedas y los limpia de vez en cuando. ¿Qué precio tiene el borrado perezoso?Ninguno: es siempre mejor, porque borrar cuesta O(1) y buscar no cambia en ningún casoLos nodos marcados siguen ocupando memoria y altura: con muchos borrados, las búsquedas recorren nodos muertosRompe el invariante del árbol, porque los nodos marcados quedan fuera de orden respecto al restoLas búsquedas fallan, porque saltar un nodo marcado corta el camino como una posición vacía en un sondeo