Caso real

Borrar en un rojinegro

En un árbol rojinegro, el borrado es la operación más complicada: después de quitar el nodo, hay hasta seis casos de recoloreo y rotación para restaurar el invariante de los colores. Por eso muchas explicaciones lo omiten, y por eso, en la práctica, casi nadie implementa su propio rojinegro: se usa el de la biblioteca.

Piensa en un compañero que quiere escribir su propio rojinegro porque «borrar son solo los tres casos que acabamos de ver». ¿Qué le falta a ese razonamiento?

Un compañero propone escribir su propio árbol rojinegro en vez de usar el de la biblioteca, porque «borrar son solo los tres casos del BST». ¿Qué le respondes?Que no hace falta: su propio BST ya es O(log n) en el peor caso, sea cual sea el ordenQue tras borrar como en un BST hay que reparar el balance con recoloreos y rotacionesQue es buena idea: con los tres casos del BST basta, porque el balance se arregla solo al volverQue el rojinegro solo se balancea al insertar, así que borrar no añade ningún caso nuevo al código