REPÚBLICA BOLIVARIANA DE VENEZUELA
COLEGIO UNIVERSITARIO DE ADMINISTRACIÓN Y MERCADEO
ESTRUCTURA DE DATOS
VALENCIA-ESTADO CARABOBO
LISTAS, PILAS Y COLAS:
Nombre: Yaher Juseh Cárdenas Carache
Cédula de Identidad: 25.338.699
Carrera: Informática
Sede: Industrial
CUAM-“CUESTION DE EXCELENCIA”
Introducción:
La presente investigación tiene como finalidad efectuar una búsqueda exhaustiva y
practica de los conceptos de Listas, Pilas y Colas; Tablas Hash; Arboles Generales,
binarios y binarios de búsqueda; Arboles AVL; Arboles APO y por último el concepto de
Grafos, todos con sus ejemplos prácticos a fin de incrementar una mejor comprensión de
lo que es Estructura de Datos en informática y de igual manera sentar las bases sólidas
para la comprensión de estos conceptos básicos y el desarrollo de estos conocimientos
en futuras habilidades de programación, facilitando así nuestro recorrido en este nuevo
mundo de la informática.
CUAM-“CUESTION DE EXCELENCIA”
Listas, Pilas y Colas:
Listas Dinámicas:
Cuando hablamos de listas simplemente tratamos de estructuras lineales en
secuencia (una al lado de la otra) y dinámicas de datos. Es este dinamismo el que le
brinda la ventaja de que se adhieran a posiciones de memoria a medida que se necesitan
y se liberan cuando ya no se requieren (En lenguajes como Java se borran y en C++ se
liberan), es decir se llegan a expandir o a contraer dependiendo de la aplicación. Ahora
bien en Estructura de Datos tenemos los siguientes tipos de listas dinámicas:
Lista Simplemente Enlazada: Es una colección de nodos que tienen una
sola dirección y que en conjunto forman una estructura de datos lineal. Cada nodo es un
objeto compuesto que guarda una referencia a un elemento (campo de información) y una
referencia a otro nodo (campo puntero o dirección).
La referencia que guarda un nodo a otro nodo se puede considerar un enlace o
un campo puntero hacia el segundo nodo y el salto que los relaciona recibe el nombre
de salto de enlace o salto de puntero. El primer nodo de una lista recibe el nombre
de cabeza, cabecera o primero (HEAD) y el último es llamado final, cola o último
(TAIL) (es el único nodo con la referencia a otro objeto como nula (NULL)).
NOTA: Un nodo de una lista enlazada simple puede determinar quien se encuentra
después de él pero no puede determinar quien se encuentra antes, ya que solo cuenta
con la dirección del nodo siguiente pero no del anterior.
Listas Doblemente Enlazadas: Es una colección de nodos, en la cual cada uno de ellos
tiene dos apuntadores, uno apuntando a su predecesor (p) y otro a su sucesor (s). Por
medio de estos punteros se podrá entonces avanzar o retroceder a través de la lista,
según
se tomen las direcciones de uno u otro puntador.
CUAM-“CUESTION DE EXCELENCIA”
Las operaciones que se pueden llevar a cabo en este tipo de estructuras son las
mismas que con listas simplemente ligadas. En esta sección se presentarán las
operaciones de: Recorrido de Lista, Inserción de un Elemento y Borrado de un Elemento.
Recorrido de lista:
Al tener cada nodo una doble liga, la lista se puede
recorrer tanto del inicio al final, mediante las ligas
derechas, como en sentido inverso; es decir, del final al
principio, con las ligas izquierdas. Cualquiera que sea la
dirección del recorrido, el algoritmo es similar al que se
presenta para listas simplemente ligadas.
Inserción de un elemento.
La inserción de un elemento consiste en agregar un
nuevo nodo a la lista y establecer los apuntadores
correspondientes. No se considerará el caso de lista
vacía.
Borrado de un elemento.
La operación de eliminación de un nodo en una lista doblemente ligada al igual que en
el caso de las listas simplemente ligadas, consiste en eliminar un elemento de la lista,
redefiniendo los apuntadores correspondientes y liberando el espacio de la memoria
ocupado por el nodo. En la eliminación se pueden presentar diferentes casos, aunque
algunos de ellos son simétricos, ya que cada nodo tiene apuntadores hacia delante –
derecha – y atrás-izquierda
En los algoritmos que presentan la solución a los diferentes casos de borrado de un
elemento de una lista, no se considera que ésta se encuentre vacía. Este caso, como ya
se ha repetido en varias ocasiones, se puede controlar en el programa principal o bien
con una condición simple al inicio de cada algoritmo.
Lista Simplemente Circular (No tiene cola): Cada nodo tiene un enlace, similar al de
las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero.
Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente
insertados después de uno que ya tengamos referenciado. Por esta razón, es usual
quedarse con una referencia solamente al último elemento en una lista enlazada circular
simple, esto nos permite rápidas inserciones al principio, y también permite accesos al
primer nodo desde el puntero del último nodo.
Lista Doblemente Circular (No tiene cola): En las listas doblemente ligadas circulares,
el campo liga izquierda del primer nodo de la lista apunta al último, y el campo liga
derecho de éste apunta al primero.
CUAM-“CUESTION DE EXCELENCIA”
La principal ventaja de las listas circulares es que permiten la navegación en
cualquier sentido a través de la misma y, además, se puede recorrer toda la lista
partiendo de cualquier nodo, siempre que tengamos un apuntador a éste. Sin embargo,
debemos destacar que es necesario establecer condiciones adecuadas para detener el
recorrido de una lista y evitar caer en ciclos infinitos. Al igual que en el caso de listas
simplemente ligadas circulares, se suele utilizar un nodo de cabecera.
Pilas (Stack) :
Es un tipo especial de lista lineal en la que la inserción y borrado de nuevos
elementos se realiza solo por un extremo que se denomina cima o tope (Top). La pilas es
una estructura con numerosas analogías en la vida real: una pila de de platos, una pila de
monedas, una pila de cajas, una pila de camisas,
etc. Manejan la analogía LIFO (Last in First out,
que es el último que ingreso es el primero que
sale).
Dado que las operaciones de insertar y
eliminar (Push) (Pop) se realizan por un solo
extremo (el superior), los elementos solo pueden
eliminarse en orden inverso al que se insertan en
la pila.
El último elemento que se pone en la pila
es el primero que se puede sacar, por ello, a
estas estructuras se les conoce por el nombre de
LIFO. Las operaciones más usuales asociadas a las pilas son:
-Push: Meter, poner o apilar, operación de insertar un elemento en la pila.
-Pop: Sacar, quitar o desapilar, operación de eliminar un elemento de la pila.
Para representar una pila se debe definir un vector con un determinado tamaño
(longitud máxima) ver array [l…n]<tipo_dato>
Se considerara un elemento entero Tope (p, cima) como el puntero de la pila
Tope es el subíndice del array correspondiente al elemento cima de la pila (esto es, el
que ocupa la última posición). Si la pila está vacía Tope = [].
CUAM-“CUESTION DE EXCELENCIA”
- En principio, la pila está vacía y el
puntero de la pila o Tope esta en cero.
- Al meter un elemento en la pila, se
incrementa el puntero en una unidad.
- Al sacar un elemento de la pila se
decrementa en una unidad el puntero.
- Al manipular una pila se deben realizar
algunas comprobaciones.
o En una pila vacía no se
pueden sacar datos (P=0).
o Si la pila se implementa con un
array de tamaño fijo, se pueden llenar cuando Tope= n (n, longitud total
de la pila) y el intento de introducir más elementos en la pila producirá un
desbordamiento de la pila.
Las pilas se pueden representar en cualquiera de las tres formas siguientes.
NOTA: Siempre tiene que tener una misma salida y entrada es decir, apilo y extraigo por
el mismo extremo.
Idealmente una pila puede contener un número ilimitado de elementos y no producir
desbordamiento. En la práctica sin embargo el espacio de almacenamiento disponible es
finito. La codificación de una pila requiere un cierto equilibrio, ya que si la longitud máxima
de la pila es demasiado grande se gasta mucha memoria, mientras que un valor pequeño
de la longitud máxima producirá desbordamientos frecuentes.
Para trabajar fácilmente con pilas es conveniente diseñar subprogramas de
adicionar (push) y eliminar (pop) elementos. También es necesario con frecuencia
comprobar si la pila está vacía, esto puede conseguirse con una variable o función
booleana ESVACIA de modo que cuando su valor sea verdadero la pila esta vacía y falso
en caso contrario.
Aplicaciones de las Pilas: Las pilas son utilizadas ampliamente para solucionar una
amplia variedad de problemas. Se utilizan en compiladores, sistemas operativos y en
programas de aplicación.
CUAM-“CUESTION DE EXCELENCIA”
Veamos algunas de las aplicaciones mas interesantes.
-Recursividad.
-Equilibrio de Símbolos.
-Tratamiento de expresiones aritméticas.
-Llamadas o subprogramas.
Ejemplo de Pilas con Código:
Empezamos declarando las variables que vamos a utilizar (líneas 1 a 4). Las cadenas las vamos a
leer carácter por carácter a
través de ch, para guardar la
pila utilizaremos el arreglo s,
y p para saber cuál es la
posición del último elemento
en la pila. El entero i lo
usaremos en ciclos y n para
saber cuántos casos
debemos procesar.
En seguida tenemos el
procedimiento push (líneas 6
a 10) y la función pop (líneas
12 a 16), que nos sirven para
meter y sacar datos de la
pila. Para guardar un dato,
se lo mandamos como
parámetro a push, donde
incrementamos la posición
del último elemento y
guardamos en esta posición
al parámetro. Para obtener
un dato, llamamos a la
función pop, en la cual
devolvemos el valor del
último dato en la pila y
decrementamos la posición
del último dato. En ningún
momento estamos revisando
si la pila está llena o vacía,
por lo que debemos tener
cuidado al usarla (o agregar
dichas verificaciones).
La parte principal del código la tenemos entre las líneas 18 y 41. Empezamos leyendo la cantidad
de casos (línea 19). Para cada caso, leemos caracter por caracter hasta llegar al fin de línea. En la
línea 22 inicializamos el tope de la pila. Cuando leemos un paréntesis que abre, lo agregamos a la
pila (líneas 26 y 27). Si encontramos uno que cierra, sacamos un dato de la pila y revisamos si
cierra correctamente (líneas 28 a 35); en caso de que no lo haga, ponemos la posición de la pila a
una posición cualquiera (distinta de cero) y nos salimos. Al final, revisamos si la cadena es válida
de acuerdo a si la pila termino vacía o no.
CUAM-“CUESTION DE EXCELENCIA”
Colas:
En las colas (también conocidas como queues, buffers o FIFO – first in, first out) los
primeros elementos que entran son los primeros en ser procesados. Esto lo podemos ver
en las filas en los bancos: los primeros que se forman son los primeros en ser atendidos.
Posee dos términos Encolar (acceso directo al primer elemento) y Desencolar (acceso
directo al último elemento). Son dinámicas y brindan acceso inmediato a los datos.
Una cola se comporta como una caja con varios elementos, en donde solo se pueden
realizar dos operaciones: encolar (enqueue) y desencolar (dequeue). Al encolar un
elemento, se agrega al final de la cola, y al desencolar se elimina el elemento que está en
el frente de la cola.
Ejemplo de uso: En sistemas operativos, la cola se utiliza para almacenar procesos
en espera de ser ejecutados. En redes de computadoras, las colas se utilizan para
almacenar paquetes en espera de ser transmitidos. En sistemas de impresión, las colas
se utilizan para almacenar documentos en espera de ser impresos. En resumen, una cola
es una estructura de datos en la que las operaciones de inserción se realizan en un
extremo (final de la cola) y las operaciones de eliminación se realizan en otro extremo
(frente de la cola). Es una estructura de datos esencial para la programación y es utilizada
en una variedad de problemas y aplicaciones.
Ventajas de las colas
- Orden de procesamiento: Las colas permiten el procesamiento de elementos en un
orden específico, lo que puede ser útil en aplicaciones que requieren un procesamiento
secuencial de tareas.
- Escalabilidad: Las colas son escalables y permiten la gestión de grandes cantidades
de elementos.
- Aplicaciones en Simulación y Planificación: Las colas son ampliamente utilizadas en
la simulación y planificación de eventos, como en la simulación de sistemas de cola en la
industria.
Desventajas de las colas
- Limitaciones en la accesibilidad a elementos: En una cola, solo es posible acceder al
primer elemento en la cola, lo que puede ser una desventaja en casos donde se necesita
acceder a elementos intermedios.
CUAM-“CUESTION DE EXCELENCIA”
- Dificultad en la eliminación de elementos intermedios: Las colas no están diseñadas
para la eliminación eficiente de elementos intermedios, lo que puede ser una desventaja
en casos donde se requiera modificar la secuencia de procesamiento de elementos.
Tablas Hash (Hash Table):
Una tabla Hash es un contenedor asociativo (tipo Diccionario) que permite un
almacenamiento y posterior recuperación eficientes de elementos (denominados valores)
a partir de otros objetos, llamados claves. Tras esta explicación preliminar vamos a entrar
en detalle. Una tabla hash se puede ver como un conjunto de entradas. Cada una de
estas entradas tiene asociada una clave única, y por lo tanto, diferentes entradas de una
misma tabla tendrán diferentes claves. Esto implica, que una clave identifica
unívocamente a una entrada en una tabla hash.
Por otro lado, las entradas de las tablas hash están compuestas por dos
componentes, la propia clave y la información que se almacena en dicha entrada.
La estructura de las tablas hash es lo que les confiere su gran potencial, ya que
hace de ellas unas estructuras extremadamente eficientes a la hora de recuperar
información almacenada. El tiempo medio de recuperación de información es constante,
es decir, no depende del tamaño de la tabla ni del número de
elementos almacenados en la misma.
Una tabla hash está formada por un array de entradas,
que será la estructura que almacene la información, y por una
función de dispersión. La función de dispersión permite asociar el
elemento almacenado en una entrada con la clave de dicha
entrada. Por lo tanto, es un algoritmo crítico para el buen
funcionamiento de la estructura. Cuando se trabaja con tablas
hash es frecuente que se produzcan colisiones. Las colisiones se
producen cuando para dos elementos de información distintos, la
función de dispersión les asigna la misma clave. Como se puede
suponer, esta solución se debe arreglar de alguna forma. Para
ello las tablas hash cuentan con una función de resolución de
colisiones.
Existen dos tipos de tablas hash, en función de cómo resuelven las colisiones:
Encadenamiento separado: Las colisiones se resuelven insertándolas en una lista. De esa
forma tendríamos como estructura un vector de listas. Al número medio de claves por lista
se le llama factor de carga y habría que intentar que esté próximo a 1.
Direccionamiento abierto: Utilizamos un vector como representación y cuando se
produzca una colisión la resolvemos reasignándole otro valor hash a la clave hasta que
encontremos un hueco
CUAM-“CUESTION DE EXCELENCIA”
Un ejemplo práctico para ilustrar
qué es una tabla hash es el
siguiente: Se necesita organizar los
números telefónicos que llegan
diariamente de tal forma que se
puedan ubicar de forma rápida,
entonces se hace lo siguiente: se
apertura un libro de páginas
amarillas para guardar todos los
números telefónicos (una tabla), y se divide en 10 contenedores (ahora es una hash
table o tabla fragmentada), y la clave para guardar los teléfonos es el día de registro
(índex). Cuando se requiere buscar un teléfono se busca por el día que fue registrado y
así se sabe en qué zócalo (bucket) está.
Funcionamiento: Las operaciones básicas implementadas en las tablas hash son:
a) Inserción
La forma de implementar en función esta operación es pidiendo la llave y el valor,
para con estos poder hacer la inserción del dato. Para almacenar un elemento en la tabla
hash se ha de convertir su clave a un número. Esto se consigue aplicando la función
resumen (hash) a la clave del elemento.
El resultado de la función resumen ha de mapearse al espacio de direcciones
del vector que se emplea como soporte, lo cual se consigue con la función módulo. Tras
este paso se obtiene un índice válido para la tabla. El elemento se almacena en la
posición de la tabla obtenido en el paso anterior. Si en la posición de la tabla ya había otro
elemento, se ha producido una colisión. Este problema se puede solucionar asociando
una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente
elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos.
b) Búsqueda
La forma de implementar en función esta operación es pidiendo la llave y con esta
devolver el valor. Para recuperar los datos, es necesario únicamente conocer la clave del
elemento, a la cual se le aplica la función resumen. El valor obtenido se mapea al espacio
de direcciones de la tabla. Si el elemento existente en la posición indicada en el paso
anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si
la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver
el problema de las colisiones al almacenar el elemento.
La mayoría de las implementaciones también incluyen la función de borrar a la
cual se le envía una llave que deberá eliminar. También se pueden ofrecer funciones
como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten
almacenar múltiples valores bajo la misma clave. Para usar una tabla hash se necesita:
-Una estructura de acceso directo (normalmente un array).
CUAM-“CUESTION DE EXCELENCIA”
-Una estructura de datos con una clave
-Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o
rango) los números naturales.
Resolución de colisiones: Si dos llaves generan un hash apuntando al mismo índice, los
registros correspondientes no pueden ser almacenados en la misma posición. En estos
casos, cuando una casilla ya está ocupada, debemos encontrar otra ubicación donde
almacenar el nuevo registro, y hacerlo de tal manera que podamos encontrarlo cuando se
requiera.
Para dar una idea de la importancia de una buena estrategia de resolución de
colisiones, considérese el siguiente resultado, derivado de la paradoja de las fechas de
nacimiento. Aun cuando supongamos que el resultado de nuestra función hash genera
índices aleatorios distribuidos uniformemente en todo el vector, e incluso para vectores de
1 millón de entradas, hay un 95% de posibilidades de que al menos una colisión ocurra
antes de alcanzar los 2500 registros. Hay varias técnicas de resolución de colisiones, pero
las más populares son encadenamiento y direccionamiento abierto.
Arboles Generales, Arboles Binarios y Binarios de Busqueda:
Arboles Generales:
Los árboles Generales son estructuras NO LINEALES; que se utilizan para
representar u organizar objetos de forma que las búsquedas sean eficientes. Un árbol
consta de un número finito de elementos llamados nodos y de un conjunto finito de líneas
dirigidas llamadas ramas, estás son las que conectan a los nodos entre sí.
Nodo raíz o puede ser
considerado nodo padre y
también hay nodos hijos.
Los Hijos de un nodo y los hijos de
estos hijos se les conocen como
descendientes y el padre y los
abuelos de un nodo son los
ascendientes.
El nivel de un
Dos o más nodos con el Un nodo sin hijos
nodo es su
mismo padre se llaman se llama nodo
distancia hasta el
nodos hermanos. hoja.
nodo raíz
CUAM-“CUESTION DE EXCELENCIA”
- Los nodos que no son hojas se denominan nodos internos.
- La longitud de un camino es el número de arcos que contiene o, de forma
equivalente, el número de nodos del camino menos uno.
- El nivel de un nodo es la longitud del camino que lo conecta al nodo raíz.
- La profundidad o altura de un árbol es la longitud del camino más largo que conecta
raíz a una hoja.
- Un subárbol de un árbol es un subconjunto de nodos del árbol, conectados por ramas
del propio árbol, esto es, a su vez un árbol.
-
Las formas más comunes de representar un árbol en papel es de forma
invertida o como una lista:
COMO ÁRBOL INVERTIDO:
El nodo raíz se encuentra en la parte más alta
de la jerarquía, de la que descienden ramas
hacia los nodos hijos.
COMO LISTA:
Se representa entre paréntesis
comúnmente en algebra. Cada
paréntesis abierto indica el comienzo de un nuevo nivel y cada paréntesis cerrado, el fin
de un nivel.
Arboles Binarios:
Un árbol binario es una estructura recursiva no puede tener más de dos nodos
hijos (pero si (0, 1,2).
El factor de equilibrio de un árbol binario es la diferencia en altura entre los
subárboles derecho menos la altura del subárbol izquierdo.
CUAM-“CUESTION DE EXCELENCIA”
Un árbol está perfectamente equilibrado si su equilibrio o balance es cero, dado
que esta definición ocurre raramente se aplica que el factor de equilibrio de cada nodo
puede tomar los valores -1, 0, +1 para que este equilibrado.
Un árbol binario completo de profundidad n es un árbol en el que para cada nivel,
del 0 al nivel n-1, tiene un conjunto lleno de nodos, y todos los nodos hoja a nivel n
ocupan las posiciones más a la izquierda del árbol. Esto sucede cuando el último nivel
está lleno.
Estructura de un Árbol Binario: Un árbol binario se construye con nodos. Cada nodo
debe contener el campo dato (datos a almacenar) y dos campos de enlace (apuntador),
un subárbol izquierdo y uno derecho.
Clasificación de los Arboles Binarios: Existen cuatro tipos de árbol binario: Arbol
Binario Distinto, Arbol Binario Similares, Árbol Binario Equivalentes, Arbol Binario
Completos. A continuación se hará una breve descripción de los diferentes tipos de árbol
binario así como un ejemplo de cada uno de ellos.
CUAM-“CUESTION DE EXCELENCIA”
N° Tipo de Árbol Ejemplo
A. B. DISTINTO: Se dice que dos árboles
binarios son
01
distintos cuando sus estructuras son
diferentes.
02
A. B. SIMILARES: Dos arboles binarios
son similares cuando sus estructuras son
idénticas, pero la información que
contienen sus nodos es diferente.
A. B. EQUIVALENTES Son aquellos
03 arboles que son similares y que además
los nodos contienen la misma información.
A. B. COMPLETOS Son aquellos arboles
en los que todos sus nodos excepto los del
04 ultimo nivel, tiene dos hijos; el subarbol
izquierdo y el subarbol derecho
Recorrido de un Árbol: El recorrido de un árbol supone visitar todos y cada uno de los
nodos una sola vez, existen 2 enfoques para la secuencia de recorrido:
- En el recorrido en profundidad.- Todos los descendientes de un hijo se procesan
antes del siguiente hijo.
- En el recorrido en anchura.- Cada nivel se procesa totalmente antes de que
comience el siguiente nivel.
Dado que un árbol binario consta de raíz, subarbol izquierdo y subarbol derecho, se
pueden definir tres tipos de recorrido en profundidad.
NID <<PREORDEN>>
1. Visitar el nodo raíz (N).
2. Recorrer el subárbol izquierdo (I) en preorden.
3. Recorrer el subárbol derecho (D) en preorden.
En el recorrido preorden, la raíz se procesa antes que los subárboles izquierdo y
derecho.
CUAM-“CUESTION DE EXCELENCIA”
IND <<ORDEN>>
1. Recorrer el subárbol izquierdo (I) en orden.
2. Visitar el nodo raíz (N).
3. Recorrer el subárbol derecho (D) en orden.
IDN <<POSTORDEN>>
4. Recorrer el subárbol izquierdo (I) en postorden.
5. Recorrer el subárbol derecho (D) en postorden.
6. Visitar el nodo raíz (N).
Árbol Binario de Búsqueda:
Un árbol binario de búsqueda es aquel en que, dado un nodo, todos los
datos del subarbol izquierdo son menores que los datos de ese nodo, mientras que
todos los datos del subarbol derecho son mayores que sus propios datos.
CUAM-“CUESTION DE EXCELENCIA”
Los arboles binarios ordenados tiene sentido, pero una propiedad característica de
ellos es que no son únicos para los mismos datos.
Un nodo de un árbol de búsqueda no difiere en nada de los nodos de un árbol binario,
tiene un campo de datos y dos enlaces de los subárboles izquierdo y derecho
respectivamente.
Operaciones con Arboles Binarios de Búsqueda: Los árboles binarios de búsqueda, al
igual que los arboles binarios, tienen naturaleza recursiva y, en consecuencia, las
operaciones sobre los arboles son recursivas. Las operaciones son:
- Búsqueda de un nodo.
- Inserción de un nodo.
CUAM-“CUESTION DE EXCELENCIA”
- Borrado de un nodo.
- Recorrido de un árbol (Los mismos recorridos de un árbol binario, preorden, inorden
postorden.
La búsqueda de un nodo comienza en el
nodo raíz y sigue estos pasos:
1. La clave buscada se compara con la
clave del nodo raíz.
2. Se las claves son iguales, la búsqueda
se detiene.
3. Si la clave buscada es mayor que la
clave raíz, la búsqueda se reanuda en el
subárbol derecho. Si la clave buscada es
menor que la raíz la búsqueda se reanuda
con el subárbol izquierdo.
Arboles Balanceados AVL:
Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y
Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus
subárboles izquierdo y derecho no difieren en más de 1.
Características:
1. Árbol binario de búsqueda.
2. Arboles balanceados.
3. La Inserción y retiro desbalancean el árbol.
4. La diferencia de alturas del árbol derecho con el izquierdo es de (-1,0,1).
Factor de balance o equilibrio
Se usa factor de balance o equilibrio cuando nuestro árbol se encuentra
desbalanceado por derecha o por izquierda. (FE = altura subárbol derecho - altura
subárbol izquierdo) o al contrario.
Para balancear nuestros arboles tenemos las siguientes herramientas
1. Rotación a la derecha
2. Rotación a la izquierda
3. Doble rotación a la derecha
4. Doble rotación a la derecha
CUAM-“CUESTION DE EXCELENCIA”
-Rotación a la izquierda: Esta rotación se usará cuando el subárbol derecho de un nodo
sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la
raíz del subárbol derecho tenga una FE de 1 ó 0, es decir, que esté cargado a la derecha
o esté equilibrado.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el
primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p,
anterior al nodo donde se halló p, se le identificara como q .
Se realiza una simple rotación a la izquierda de 45° desde P .
La raíz del árbol queda con FB -1, de manera que es balanceado.
-Rotación por la derecha: Esta rotación se usará cuando el subárbol izquierdo de un
nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y
CUAM-“CUESTION DE EXCELENCIA”
además, la raíz del subárbol izquierdo tenga una FE de -1 ó 0, es decir, que esté cargado
a la izquierda o equilibrado. Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia arriba, el
primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con una p,
anterior al nodo donde se halló p, se le identificara como q .
Se realiza una simple rotación a la derecha de 45° desde P .
La raíz del árbol queda con FB 0, de manera que es balanceado.
-Doble rotación a la izquierda: Se hace doble rotación a la izquierda si se cumplen los
siguientes entes:
1. El nodo insertado por p tiene un factor de balance (F.B.) menor que 1
2. El nodo insertado por q tiene un factor de balance igual a 1 o -1.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia
arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con
una p, anterior al nodo donde se halló p, se le identificara como q.
CUAM-“CUESTION DE EXCELENCIA”
Hay que hacer una simple rotación a la derecha desde q y una simple rotación a la
izquierda desde p.
La raíz del árbol queda con FB 0, de manera que es balanceado.
Por último verificamos que el inorden de igual de cuando no era avl a cuando lo
rotamos para convertirlo el avl.
-Doble rotación a la derecha: Se hace doble rotación a la derecha si se cumplen los
siguientes entes:
1. El nodo insertado por p tiene un factor de balance (F.B.) menor que 1
2. El nodo insertado por q tiene un factor de balance igual a 1 o -1.
Ejemplo:
Se identifica p y q, determinando el FB del árbol; si se observa de abajo hacia
arriba, el primer FB que sea diferente a 1 se le señala con una flecha y se le identifica con
una p, anterior al nodo donde se halló p, se le identificara como q .
Hay que hacer una simple rotación a la izquierda desde q y una simple rotación a
la derecha desde p.
CUAM-“CUESTION DE EXCELENCIA”
La raíz del árbol queda con FB 0, de manera que es balanceado.
Por último verificamos que el inorden de igual de cuando no era avl a cuando lo
rotamos para convertirlo el avl.
Retiro de nodos
Recordamos un poco la idea del algoritmo de eliminación sobre árboles binarios de
búsqueda. Primero se recorre el árbol para detectar el nodo a eliminar. Una vez hecho
esto hay tres casos a diferenciar por su complejidad:
Si dicho nodo es una hoja procedemos a eliminarlos de inmediato, sin más.
Si dicho nodo tiene un sólo hijo, el nodo puede eliminarse después de ajustar un
apuntador del padre para saltar el nodo.
Si dicho nodo tiene dos hijos el caso es un poco más complicado. Lo que se estila
hacer es reemplazar el nodo actual por el menor nodo de su subárbol derecho (y luego
eliminar éste).
Hay que tener en cuenta que después de retirar un nodo, si el árbol queda des
balanceado tendremos que proceder a balancearlo usando las técnicas dichas
anteriormente.
Ejemplo:
En el siguiente árbol avl vamos a retirar el nodo 6.
Como apreciamos luego de retirar el 6 nuestro árbol quedo desbalanceado, por lo que
debemos balancearlo usando las técnicas anteriormente mencionadas.
CUAM-“CUESTION DE EXCELENCIA”
Arboles Parcialmente Ordenado (APO):
Un árbol A se dice parcialmente ordenado (APO) si cumple la condición de que la
etiqueta de cada nodo es menor (de igual forma mayor) o igual que las etiquetas de los
hijos (se supone que el tipo_elemento base admite un orden) manteniéndose además tan
balanceado como sea posible, en el caso óptimo equilibrado.
BORRADO EN LOS APO
- No se puede quitar el nodo sin más, ya que se desconectaría la estructura. Si se quiere
mantener la propiedad de orden parcial y el mayor balanceo posible con las hojas en el
nivel más bajo alojadas de izquierda a derecha , lo que podría hacerse es poner
provisionalmente la hoja más a la derecha del nivel más bajo como raíz provisional.
Empujaremos entonces esta raíz hacia abajo intercambiándola con el hijo de etiqueta
menor hasta que no podamos hacerlo más (porque sea ya una hoja o porque la etiqueta
sea ya menor que la de cualquiera de sus hijos).
INSERCIÓN EN LOS APO
CUAM-“CUESTION DE EXCELENCIA”
- El nuevo elemento que se inserta, lo podríamos situar provisionalmente en el nivel m ás
bajo tan a la izquierda como sea posible (se comienza en un nuevo nivel si el último nivel
está completo). A continuación se intercambia con su padre repitiéndose este proceso
hasta que se cumpla la condición de orden parcial (bien porque ya esté en la raíz o
porque tenga ya una etiqueta mayor que la de su padre).
TDA APO
- Una instancia del tipo de dato abstracto APO sobre un dominio Tbase es un árbol binario
con etiquetas en Tbase y un orden parcial que consiste en que la etiqueta de un nodo es
menor o igual que la de sus descendientes. Para poder gestionarlo, debe existir la
operación menor (<) para el tipo Tbase.
- El espacio requerido para el almacenamiento es O(n), donde n es el número de
elementos del árbol.
- En un APO tenemos un vector de tipo Tbase llamada vec donde alamacenaremos los
elementos del APO. Tenemos n elementos que nos da el número de elementos del APO.
Por último tenemos max elementos que nos indica la cantidad de posiciones reservadas
en vector, como es natural debe ser mayor o igual a n elementos.
CUAM-“CUESTION DE EXCELENCIA”
Grafos:
Los grafos son una composición interesante de conjuntos de objetos que
denominamos nodos. En ellos se almacena diferentes tipos de elementos o datos que
podemos utilizar para procesar o conocer con fines específicos.
Adicionalmente estos nodos, suelen estar unidos o conectados a otros nodos a
través de elementos que denominamos aristas. Los nodos pertenecientes a un grafo
pueden contener datos estructurada o no estructurada y al interrelacionarse con otros
nodos producen relaciones interesantes que podemos analizar con diferentes finalidades.
Estos elementos son reconocidos por su capacidad de manejar altos volúmenes de datos
y ser fácilmente procesados por motores de búsqueda o gestores de bases de datos
orientados a grafos.
Utilidades de las imágenes de grafos:
Los grafos en imágenes nos permiten entender la profundidad de las relaciones
que existen entre los datos. Gracias a estas propiedades de análisis los analistas
comerciales de las empresas pueden comprender mejores los segmentos de mercado y
optimizar las propuestas de productos y servicios para sus clientes.
Uno de los sectores que más puede sacarle provecho a las propiedades de las
imágenes de grafos es el sector financiero y bancario. Los análisis de grafos que arrojan
estás imágenes son extremadamente útiles para la prevención de delitos financieros
como el blanqueo de capitales o el fraude electrónico. Ejemplos:
Los sistemas financieros pueden construir estructuras gráficas similares a la de la
imagen anterior para representar a sus clientes en nodos. Con las aristas que conectan
los nodos podemos conocer las relaciones que se generan entre ellos y según la
configuración de patrones de riesgo podemos detectar actividad inusual e ir a profundidad
Al detectar un patrón de riesgo o
actividad sospechosa de actividad
delictivos podemos obtener imágenes
específicas dentro del grafo para analizar
las operaciones realizadas de forma
eficiente y rápida para evitar operaciones
fraudulentas.
CUAM-“CUESTION DE EXCELENCIA”
Conclusión:
Por la investigación efectuada se pudo concluir que cada uno de estos procesos,
clases y funciones tienen la finalidad de agilizar los procesos de control, verificación,
análisis, recorrido, dinamismo y flexibilidad a la hora de manejar datos; en lo que se
refiere a las listas pudimos evidenciar que brindan flexibilidad y acceso inmediato a los
datos, más sin embargo tienen como desventaja la secuencia lineal; en cuanto a las Colas
se pudo comprender que funcionan bajo el proceso de FIFO y los procesos de Encolar y
Desencolar; en lo que respecta a Pilas observamos que tiene las propiedades Push y Pop
(adicionar y eliminar); por otra parte las Tablas Hash o Table Hash nos permiten organizar
dentro de un array o arreglo varios datos y buscarlos bajo un index o índice.
Continuamos nuestra búsqueda con la comprensión de los Arboles Generales,
binarios y binarios de búsqueda los cuales dentro de su estructura de nodos son base
fundamental en la Estructura de Datos en cualquier lenguaje de programación. Los
arboles AVL o Balanceados y los Arboles Parcialmente Ordenados son arboles binarios
de búsqueda ya que sus subárboles forman un conjunto de nodos ordenados. Y
finalizamos con la comprensión de los Grafos que son herramientas de gran utilidad para
la construcción de estructuras graficas permitiéndonos entender la relación de los nodos y
aristas en datos estructurados o no estructurados.
Por lo anteriormente expuesto podemos concluir que cada uno de estas funciones
no solo son usadas en Estructura de Datos sino forman parte de nuestra vida cotidiana
diaria y coadyuvan al mejoramiento y el manejo de los datos e informaciones.
CUAM-“CUESTION DE EXCELENCIA”
