Diferencia entre revisiones de «Estructuras de datos dinámicas/Árboles»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 18:
<li>La altura de un nodo es 1 más que la mayor altura de un hijo suyo. La altura de un árbol es la altura de la raíz.
<li>Los nodos que tienen el mismo padre son hermanos.
<li>Si hay un camino del nodo u al nodo v, u es ascendiente de v y v es descendiente de u. Si u <math>
<li>El tamaño de un nodo es el número de descendientes (incluido él mismo). El tamaño de un árbol es el tamaño de su raíz.
==Operaciones básicas==
Línea 151:
===Árboles rojinegros===
Árbol binario de búsqueda, donde cada nodo está coloreado con los colores rojo o negro, y se verifican las siguientes propiedades:
1. La raíz es negra.
2. Si un nodo es rojo, sus hijos deben ser negros.
3. Todos los caminos desde un nodo a un nodo vacío deben contener el mismo número de nodos negros.
Las condiciones (2) y (3) aseguran que el árbol nunca esté demasiado desbalanceado. (2) asegura que no puedan haber demasiados nodos rojos, y (3) dice que, despreciando el número de nodos rojos, que es limitado, el árbol es perfectamente balanceado.
La condición (1) es trivial: si la raíz es roja, simplemente se colorea negra, ya que esto no violará ninguna regla.
En los ARN la operación eliminar se complica.
Cuando se necesitan árboles equilibrados y se requieren muchas eliminaciones se emplean los AA-Árboles que añaden una condición adicional a las impuestas por los ARN:
4. Los hijos izquierdos no pueden ser rojos.
====Altura de un ARN====
En un ARN con n nodos, la altura h será:
<math>h
=====Demostración=====
La condición (3) nos permite asegurar que, despreciando el número de nodos rojos, el árbol es perfectamente balanceado, y, en virtud de esa característica, su altura <math>h
====Operaciones====
Se pueden realizar operaciones de búsqueda con complejidad O(log N), por lo expuesto anteriormente.
Línea 173 ⟶ 178:
====Inserción ascendente====
Sea X la nueva hoja añadida, P su padre, S el hermano de P (si existe) y G el abuelo.
1. Los nuevos nodos se insertan en el árbol como hojas de color rojo.
2. Si el padre es negro, hemos acabado.
3. Si el padre es rojo violamos la regla 2, entonces debemos modificar el árbol de forma que se cumpla la regla (2) sin introducir violaciones de la propiedad (3).
4. Si el padre P es la raíz, se colorea negro. La altura negra aumenta en 1, pero el balance se preserva. Hemos acabado.
=====Reparación del balance=====
Asumiendo que P no es la raíz
5. Si S es rojo, se puede aplicar un cambio de color:
Se elimina así la violación, y el balance de negros se mantiene.
¿Qué pasa si el padre de G es también rojo?
Solución: propagar este procedimiento hacia arriba hasta conseguir que no haya dos nodos rojos consecutivos o alcanzar la raíz. Esta propagación es análoga a la que se hace en los árboles AVL.
6. Si S es negro, tenemos dos casos, con sus simétricos asociados: violación en el margen, y violación por dentro.
7. Si es una violación es por dentro, la convertimos a una violación en el margen haciendo una rotación:
Como X y P son rojos, no añaden nada en el balance de negros a los caminos que pasan por g, de manera que el balance se preserva.
8. Teniendo el caso de violación por dentro, se efectúa una rotación simple.
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.
Línea 195 ⟶ 208:
¿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>.
Un B-árbol de orden M es un árbol M-ario que verifica:
<li>Cada página, excepto la página raíz y las páginas hojas, tienen entre M/2 y M descendientes, y entre (M/2 -1) y (M-1) elementos.
| |||