Diferencia entre revisiones de «Estructuras de datos dinámicas/Árboles»
Contenido eliminado Contenido añadido
Línea 202:
La rama izquierda de desbalancea, le falta un nodo negro para todos sus caminos, y aún tenemos la violación rojo-rojo. Solucionamos ambos problemas haciendo un cambio de color.
====Inserción descendente====
Objetivo: garantizar que en el momento de la inserción S no es
En el camino descendente, si un nodo X tiene dos hijos rojos, el color de X cambia a rojo y el de sus dos hijos a negro. El número de nodos negros en los caminos por debajo de X permanece inalterable.
Si X es la raíz, la convertiríamos en roja, hay que volver a negro (esto no puede violar ninguna de las reglas).
Si el padre de X es rojo, hay que aplicar rotación simple o doble.
¿Qué pasa si el hermano del padre de X es también rojo? Esta situación NO puede darse, gracias al proceso efectuado en el camino descendiente.
==Árboles B==
Mientras que la altura de un árbol binario completo es, aproximadamente, <math>log_{2} N</math>, la altura de un árbol M-ario completo es, más o menos, <math>log_{M} N</math>.
| |||