Diferencia entre revisiones de «Árbol AA»
Contenido eliminado Contenido añadido
Línea 93:
== Borrado ==
Como en la mayoría de árboles binarios balanceados, el borrado de un nodo interno puede convertirse en el borrado de un nodo hoja al intercambiar el nodo interno bien con su predecesor o sucesor más próximo, dependiendo del que esté en el árbol o de los deseos del implementador. Para recuperar un predecesor símplemente se debe seguir un enlace izquierdo y después todos los enlaces derechos restantes. De forma similar, el sucesor se puede encontrar al ir una vez a la derecha y una vez
Para re-equilibrar un árbol existen diferentes aproximaciones. La que describió Andersson en su [http://user.it.uu.se/~arnea/abs/simp.html publicación original] es la más simple, y se describirá aquí, aunque implementaciones reales pueden optar por un enfoque más optimizado. Tras un borrado, el primer paso para mantener la validez es reducir el nivel de todos los nodos cuyos hijos están dos niveles por debajo de ellos, o a los que les faltan hijos. Después, todo el nivel debe ser torsionado y dividido. Esta aproximación se ha visto favorecida por el hecho de que se basa en tres pasos independientes y fáciles de entender:
| |||