Diferencia entre revisiones de «Estructuras de datos dinámicas/Árboles»
Contenido eliminado Contenido añadido
Sin resumen de edición |
|||
Línea 1:
=Árboles=
<!-- Faltan
Árbol: estructura no lineal y dinámica de datos.
Dinámica: puede cambiar durante la ejecución de un programa.
Línea 11:
<li>Hay un único camino desde la raíz hasta cada nodo. La longitud del camino es su número de aristas.
==Definición recursiva==
Un árbol es o bien vacío
==Definiciones==
<li>Los nodos que no tienen hijos se denominan hojas.
<li>Un árbol con N nodos debe tener (N-1) aristas.
<li>La profundidad de la raíz es 0 y la de cualquier nodo es la de su padre más 1.
<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
<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 25:
<li>Eliminar
<li>Ir a la raíz
<li>Recorrer
==Implementación primer hijo - siguiente hermano==
==Árboles binarios==
Un árbol binario es o bien vacío o consta de una raíz, un hijo árbol binario izquierdo y otro derecho.
Línea 40 ⟶ 37:
<li>Todos los valores de los nodos del subárbol derecho de A deben ser mayores o iguales al valor del nodo A.
Un recorrido en inorden del árbol proporciona una lista en orden ascendente de los valores almacenados en los nodos.
Para describir las operaciones, se considera que estas se enmarcan dentro de la clase NodoBinario. El lenguaje utilizado es JAVA.
====Operación
{
if (o.equals(valor))
return true;▼
return true;
else if (o.compareTo(valor)<0) return buscar(getIzq(),o);
else return buscar(getDer(),o);
====Operación “insertar” ====
▲ if (o.compareTo(valor)<0)
▲ else setDer(insertar(getDer(),o));
}
Dentro de la clase NodoBinarioVacio:
public NodoBinario insertar(Comparable o)
{
}
====Operación “recorrer” ====
Los recorridos pueden ser en preorden, postorden o inorden (orden simétrico). Todos son O(N).
public void preOrder(SList aList)
{
aList.addElement(value);
left.preOrder(aList);
right.preOrder(aList);
}
public void inOrder(SList aList)
{
}
public void posOrder(SList aList)
{
}
Los recorridos no necesitan obligatoriamente recursividad, se puede emplear una pila
====Operación “borrado” ====
El nodo a borrar debe ser reemplazado por el nodo más a la derecha en el subárbol izquierdo o el nodo más a la izquierda en el subárbol derecho (el nodo más a la derecha del subárbol izquierdo será mayor o igual que cualquier otro nodo de ese subárbol y menor que todos los del subárbol derecho, y el nodo más a la izquierda del subárbol derecho será menor que todos los demás nodos de ese subárbol y mayor que todos los del subárbol izquierdo).
Para el caso en el que el nodo elegido tengo un subárbol, hay por lo menos
<li>La primera consiste en conservar la estructura del subárbol, y colgar del elemento ubicado en el extremo (el elemento menor o mayor) correspondiente al subárbol donde se encuentra el elemento a promover hacia la raíz (en este ejemplo, el subárbol izquierdo, por lo cual se buscará el elemento más a la izquierda), lo cual es consistente, porque todos los elementos en el subárbol promovido serán mayores que los del subárbol del cual estaban colgados a la derecha. El inconveniente que presenta esta solución es que debe utilizarse una función encontrarMínimo() o encontrarMáximo().
<li>La segunda solución consiste en colgar del padre del nodo promovido hacia la raíz, el subárbol remanente. Esto es consistente, porque todo elemento del subárbol derecho de un nodo será mayor que el valor de ese nodo, y viceversa.
Estas soluciones aprovechan la ventaja de contar con que el nodo promovido tiene, a lo sumo, un subárbol.
<li>Un hueco dejado por un nodo promovido también puede pensarse como una eliminación.
===Árboles binarios perfectamente equilibrados===
La eficiencia de las operaciones depende exclusivamente de la altura del árbol.
Línea 111 ⟶ 105:
Todos los árboles perfectamente equilibrados son AVL.
La longitud de camino media es prácticamente idéntica a la de un árbol perfectamente equilibrado.
En un AVL se puede realizar con complejidad del O(log
<li>Encontrar un nodo con una clave dada.
<li>Insertar un nodo con una clave dada.
<li>Borrar un nodo con una clave dada.
Un árbol AVL de altura H tiene por lo menos (Fibonacci(H+3) -1) nodos.
Los pasos necesarios para insertar un nodo en un árbol AVL son:
<li>Agregar el nodo como en un árbol binario de búsqueda.
Línea 122 ⟶ 116:
Casos en situación de reestructurar:
====Inserciones en los “márgenes” ====
1 y 4: inserciones en los “márgenes”: rotación simple: intercambia los papeles de los padres y de los hijos, manteniendo la ordenación.
// Rotación izquierda - izquierda
private static NodoAVL rotarConHijoIzq(NodoAVL A)
{
}
====Inserciones por “dentro” ====
2 y 3: inserciones por “dentro”: rotación doble.
Notar que una rotación simple no resuelve el problema, ya que la rama que provocó el desequilibrio se descuelga del nodo promovido y se cuelga al nodo que desciende un nivel, de manera que se mantiene con la misma profundidad, que es la que provocó el desequilibrio.
Por lo tanto, antes de rotar, debe desplazarse el desequilibrio a la rama correspondiente, es decir, transformamos el caso de una inserción por dentro, a un caso de inserción en el margen, utilizando una rotación.
// Rotación izquierda - derecha
private static NodoAVL rotarDobleConHijoIzq(NodoAVL A)
{
}
Como se ve, el problema se convirtió en un problema igual al del primer caso.
Los pasos necesarios para suprimir un nodo en un árbol AVL son:
Línea 156 ⟶ 150:
En la práctica se utilizan otros esquemas de equilibrio como los árboles rojinegros: como en los AVL las operaciones son logarítmicas en el peor caso. La ventaja es que las inserciones y eliminaciones pueden realizarse con un único recorrido descendente.
===Árboles rojinegros===
Árbol binario de búsqueda,
2. Si un nodo es rojo, sus hijos deben ser negros.
▲2. La raíz es negra.
3.
Las condiciones (
La condición (
▲Las condiciones (3) y (4) aseguran que el árbol nunca esté demasiado desbalanceado. (3) asegura que no puedan haber demasiados nodos rojos, y (4) dice que, despreciando el número de nodos rojos, que es limitado, el árbol es perfectamente balanceado.
▲La condición (3) es trivial. Si la raíz es roja, simplemente se colorea negra, ya que esto no violará ninguna regla.
En un ARN con n nodos, la altura h será:▼
Demostración▼
La condición (4) 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 h ≤ log2(n+1). La condición (3) evita que haya nodos rojos consecutivos, como máximo, la mitad de los nodos de un camino -que constituirán una altura- serán rojos.▼
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:
====Altura de un ARN====
▲En un ARN con n nodos, la altura h será:
<math>h /leq 2 log_{2}(n+1)</math>
▲=====Demostración=====
▲La condición (
====Operaciones====
Se pueden realizar operaciones de búsqueda con complejidad O(
Al realizar una inserción, la complejidad de búsqueda será O(
Si coloreamos el nuevo nodo rojo, el balance de negros quedará intacto, pero se puede incurrir en una violación rojo-rojo. Si lo coloreamos negro, no se incurrirá en una violación rojo-rojo, pero en este caso, siempre alteraremos el balance de negros.
Al eliminar, si el nodo a eliminar es negro, ambas violaciones pueden aparecer.
Línea 179 ⟶ 173:
====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.
2.
3.
4.
=====Reparación del balance=====
Asumiendo que P no es la raíz
5.
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.
7.
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.
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.
▲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 rojo, de manera que sólo haya que añadir una hoja roja y, si fuere necesario, realizar una rotación (simple o doble).
Línea 202 ⟶ 194:
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,
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.
<li>La página raíz, o es una hoja o tiene entre 2 y M descendientes.
<li>Las páginas hojas están todas al mismo nivel.
Línea 222 ⟶ 205:
Debe tenerse en memoria principal la página sobre la cual vamos a buscar. Considérese el elemento a buscar x.
Si la búsqueda es infructuosa dentro de la página se estará en una de las siguientes situaciones:
<li>
<li>
<li><math>x
Si en algún caso la referencia es nula, es decir, si no hay página descendiente, entonces no hay ningún elemento x en todo el árbol y se acaba la búsqueda.
===Inserción===
Siempre se inserta en los nodos hojas.
Primero se comprueba que la clave no se encuentre en el árbol.
Si la cantidad de elementos es menor que 2n:
<li>Se inserta en forma secuencial la clave.
Si la cantidad de elementos es 2n:
<li>Los 2n+1 elementos se dividen en dos páginas, excluyendo la clave del medio.
<li>La clave del medio se inserta en el nodo padre.
===Borrado===
Si la clave a ser borrada no está en una hoja, su predecesor inmediato
Si la hoja queda con menos de n elementos, se comprueba si se puede promover un elemento de un hermano adyacente a su padre, y bajar el del padre a la hoja.
Si el hermano tiene sólo n elementos, las dos hojas y la clave del medio se unen, y la clave del medio se elimina del nodo padre.
Línea 243 ⟶ 226:
<li>Existe un orden lineal entre las hojas, que están encadenadas mediante punteros para permitir un eficiente acceso secuencial.
===Búsqueda por clave===
Buscar en la raíz el valor
La búsqueda sigue por el puntero
===Inserción===
Se busca el nodo hoja correspondiente y se inserta la clave si no está allí.
Línea 250 ⟶ 233:
===Eliminación===
Se busca el nodo hoja correspondiente y se elimina la clave.
Si al eliminar una clave, n queda menor a (M/2 -1), entonces debe realizarse una redistribución de claves, tanto en el índice como en las páginas hojas.
|