Diferencia entre revisiones de «Teoría de grafos/Contenido del curso»

Contenido eliminado Contenido añadido
m Deshecha la edición 120259 de 200.106.37.38 (disc.) - Revirtiendo a la edición anterior por vandalismo. + propuesta.
Línea 44:
 
== Árboles binarios de busqueda==
 
¿Qué son los árboles binarios de búsqueda?
Empezaremos recordando lo que son los árboles. Un árbol es una colección de nodos que puede
estar vacía o no.
Si no está vacía, el árbol estará formado por un nodo raíz y cero o más subárboles que están
unidos a la raíz por otras tantas aristas.
Para que un árbol sea binario es requisito indispensable el que el número máximo de hijos que
tenga cada nodo sea 2. Por lo tanto el árbol anterior no es un árbol binario, ya que el nodo A tiene 3
hijos.
Por último, un árbol será de búsqueda si todos sus nodos cumplen las siguientes condiciones:
• Todos los nodos situados a su izquierda son menores que él.
• Todos los nodos situados a su derecha son mayores que él.
Resumiendo, se puede decir que un árbol binario de búsqueda es un árbol en el que cada nodo
tiene a lo sumo dos hijos, y en el que para cada nodo todos los nodos a su izquierda son menores que él
y todos los nodos a su derecha son mayores que él.
Unidad 5.- Grafos y árboles
Ing. Miguel Ángel Durán Jacobo 27
El siguiente árbol es un ejemplo de árbol de búsqueda:
En cambio este árbol viola la condición de orden en el nodo 2, ya que un nodo a su derecha, 1, no es
mayor que él.
Transformación de un árbol general en un árbol binario.
En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol
binario. Para esto, debemos seguir los pasos que se describen a continuación:
1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además,
debe eliminarse el vínculo de ese padre con el resto de sus hijos.
3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol
binario correspondiente.
Unidad 5.- Grafos y árboles
Ing. Miguel Ángel Durán Jacobo 28
OPERACIONES BÁSICAS EN ÁRBOLES BINARIOS DE BÚSQUEDA
Como en toda estructura de datos hay dos operaciones básicas, inserción y eliminación.
Inserción: El procedimiento de inserción en un árbol binario de búsqueda es muy sencillo, únicamente hay que
tener cuidado de no romper la estructura ni el orden del árbol.
Cuando se inserta un nuevo nodo en el árbol hay que tener en cuenta que cada nodo no puede tener más
de dos hijos, por esta razón si un nodo ya tiene 2 hijos, el nuevo nodo nunca se podrá insertar como su hijo. Con
esta restricción nos aseguramos mantener la estructura del árbol, pero aún nos falta mantener el orden.
Para localizar el lugar adecuado del árbol donde insertar el nuevo nodo se realizan comparaciones entre
los nodos del árbol y el elemento a insertar. El primer nodo que se compara es la raíz, si el nuevo nodo es menor
que la raíz, la búsqueda prosigue por el nodo izquierdo de éste. Si el nuevo nodo fuese mayor, la búsqueda
seguiría por el hijo derecho de la raíz.
Este procedimiento es recursivo, y su condición de parada es llegar a un nodo que no tenga hijo en la
rama por la que la búsqueda debería seguir. En este caso el nuevo nodo se inserta en ese hueco, como su nuevo
hijo.
Vamos a verlo con un ejemplo sobre el siguiente árbol:
Se quiere insertar el elemento 6.
Lo primero es comparar el nuevo elemento con la raíz. Como 6 > 4, entonces la búsqueda prosigue por
el lado derecho. Ahora el nuevo nodo se compara con el elemento 8. En este caso 6 < 8, por lo que hay que
continuar la búsqueda por la rama izquierda. Como la rama izquierda de 8 no tiene ningún nodo, se cumple la
condición de parada de la recursividad y se inserta en ese lugar el nuevo nodo.
Borrar: El borrado en árboles binarios de búsqueda es otra operación bastante sencilla excepto en un caso.
Vamos a ir estudiando los distintos casos.
Tras realizar la búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el caso más
sencillo, únicamente habrá que borrar el elemento y ya habremos concluido la operación.
Unidad 5.- Grafos y árboles
Ing. Miguel Ángel Durán Jacobo 29
Si tras realizar la búsqueda nos encontramos con que tiene un sólo hijo. Este caso también es sencillo, para
borrar el nodo deseado, hacemos una especie de puente, el padre del nodo a borrar pasa a apuntar al hijo del
nodo borrado.
Por último, el caso más complejo, si el nodo a borrar tiene dos hijos. En este caso se debe sustituir el nodo a
borrar por mayor de los nodos menores del nodo borrado, o por el menor de los nodos mayores de dicho nodo.
Una vez realizada esta sustitución se borra el nodo que sustituyó al nodo eliminado (operación sencilla ya que
este nodo tendrá un hijo a lo sumo).
Sobre el siguiente árbol queremos eliminar el elemento 6. Tenemos dos opciones para sustituirlo:
• El menor de sus mayores: 7.
• El mayor de sus menores: 4.
Vamos a sustituirlo por el 7 (por ejemplo). El árbol resultante sería el siguiente, tras eliminar también el
elemento 7 de su ubicación original.
Otras operaciones
En los árboles de búsqueda la operación buscar es muy eficiente. El algoritmo compara el elemento a
buscar con la raíz, si es menor continua la búsqueda por la rama izquierda, si es mayor continua por la izquierda.
Este procedimiento se realiza recursivamente hasta que se encuentra el nodo o hasta que se llega al final del
árbol.
Unidad 5.- Grafos y árboles
Ing. Miguel Ángel Durán Jacobo 30
Otra operación importante en el árbol es el recorrido el mismo. El recorrido se puede realizar de tres
formas diferentes:
• Preorden: Primero el nodo raíz, luego el subárbol izquierdo y a continuación el subárbol derecho.
• In orden: Primero el subárbol izquierdo, luego la raíz y a continuación el subárbol derecho.
• Postorden: Primero el subárbol izquierdo, luego el subárbol derecho y a continuación la raíz.
Utilización de árboles binarios de búsqueda.
Los árboles binarios de búsqueda son unas estructuras de datos muy utilizadas en la informática. Una de
sus más importantes aplicaciones es el almacenamiento de información asociada con claves de búsqueda, ya que
permite un almacenamiento y recuperación de la información muy eficiente.
Sean T un árbol ordenado y A el conjunto de todos los vértices de T. Se define un árbol posiciónala binario B (t)
sobre el conjunto de vértices A, como sigue. Si v ∈ A, entonces, el hijo izquierdo VL de v en B (t) es el primer
hijo de v en T, si éste existe. El hijo derecho VR de v en B (t) es el siguiente hermano de v en T (en el orden dado
de los hermanos de T), si es que este existe.
Ejemplo. La figura a continuación muestra el dígrafo de un árbol etiquetado T. Se supone que cada conjunto de
hermanos está ordenado de izquierda a derecha, como en el dibujo. Así, los hijos del vértice 1, es decir, los
vértices 2, 3 Y 4, quedan ordenados con el vértice 2 en primer lugar, el 3, en segundo y el 4, en tercero. De
manera similar, el primer hijo del vértice 5 es el vértice 11, el segundo es el vértice 12 y el tercero es el vértice
13.
En la siguiente figura aparece el dígrafo del árbol posicional binario correspondiente, B(T).
Para obtenerla basta trazar una arista izquierda desde cada uno de los vértices v hacia su primer hijo (si
tiene hijos). Después se traza una arista derecha de cada uno de sus vértices v hacia su siguiente hermano.
Así, la arista izquierda del vértice 2, va al vértice 5, ya que el vértice 5 es el primer hijo del vértice 2 en el
árbol T. Además, la arista derecha del vértice 2, va hacia el vértice 3, ya que el vértice 3 es el siguiente hermano
en el renglón (entre todos los hijos del vértice 1).
Con frecuencia, la representación de B(T) a manera de lista doblemente enlazada se llama representación
en lista enlazada de T.
1
2 3 4
5 6 7 8 9 10
11 12 13
Unidad 5.- Grafos y árboles
Ing. Miguel Ángel Durán Jacobo 31
 
==Isomorfismos de árboles==