UNIVERSIDAD MAYOR DE SAN SIMON

FACULTAD DE TECNOLOGIA

DEPARTAMENTO DE INFORMÁTICA Y SISTEMAS

ELEMENTOS DE LA PROGRMACIÓN Y ESTRUCTURA DE DATOS

GRUPO: PIXEL
INTRODUCCION:

En programación, una estructura de datos es una forma de organizar un

conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de
facilitar la manipulación de estos datos como un todo y/o individualmente.

Definición General

Una estructura de datos es una forma especializada de organizar y almacenar datos en una computadora de manera que se
pueda acceder y modificar de manera eficiente.

En Java, las estructuras de datos se implementan mediante diversas clases que proporcionan métodos predefinidos para
realizar operaciones comunes como la inserción, eliminación, búsqueda y ordenamiento de datos.

En este informe, nos enfocaremos en las estructuras de datos fundamentales que son ampliamente utilizadas en la
programación y el desarrollo de software. Estas estructuras son:

Listas

Una lista es una estructura de datos que organiza elementos en una secuencia flexible y dinámica, permitiendo cambios de
implementación y almacenamiento de elementos homogéneos.

Pilas

Las pilas son estructuras LIFO (Last In, First Out) donde el último elemento añadido es el primero en salir, útiles para
evaluaciones de expresiones, gestión de llamadas y algoritmos de retroceso.

Colas

Las colas son estructuras FIFO (First In, First Out) que mantienen una secuencia predecible en la ejecución de operaciones,
donde el primer elemento en entrar es el primero en salir.

Árboles

Los árboles son estructuras jerárquicas con un nodo raíz y nodos secundarios, usados para sistemas de archivos, bases de
datos y operaciones eficientes de búsqueda, inserción y eliminación.

Grafos

Los grafos son estructuras de datos no lineales con nodos conectados por enlaces, utilizados para representar relaciones
complejas entre datos sin las restricciones jerárquicas de un árbol.

Discusión sobre la elección de la estructura de datos adecuada según el problema a resolver.

A lo largo de este informe, exploraremos la implementación, características y casos de uso de varias estructuras de datos.
Analizaremos sus ventajas y desventajas con ejemplos prácticos, proporcionando una comprensión esencial para optimizar
aplicaciones y gestionar datos eficientemente.

Colas:

Definición y principios de funcionamiento:

La idea de la cola es simular el funcionamiento de una cola de la vida real, por ejemplo, la cola de un banco. Imagina que
tienes una pistola de juguete parecida a la del ejemplo de pila, pero ahora, para cargarla, debes introducir las pelotas por la
parte trasera del cañón. Eso es una Cola.

Una cola es una estructura de datos que sigue el principio de FIFO (First In, First Out), donde los elementos se insertan al
final de la cola y se extraen del principio. Este tipo de estructura de datos es útil para manejar flujos de entrada y salida de
datos, como en sistemas de cola de impresión o en la gestión de tareas.

Tipos de colas:

1) Cola Simple:

 Definición: Una cola simple es una estructura de datos donde los elementos se insertan y se extraen en el orden
en que se insertaron.

 Implementación: En Java, se puede implementar una cola simple utilizando una clase ArrayList o una
clase LinkedList.

2) Cola doblemente terminada:

 Definición: Una cola con prioridad doblemente terminada es una estructura de datos donde los elementos se
insertan y se extraen en función de su prioridad. Esta estructura permite que los elementos con mayor prioridad
se extraigan primero.

 Implementación: En Java, se puede implementar una cola con prioridad doblemente terminada utilizando una
clase PriorityQueue de la biblioteca estándar.

3) Cola de prioridad:
 Una cola de prioridad es una estructura de datos especial que permite almacenar elementos de manera ordenada
según su prioridad. A diferencia de una cola simple (FIFO), en una cola de prioridad los elementos se extraen
según su prioridad, independientemente del orden en que fueron insertados
 Las principales características de una cola de prioridad son:
 Los elementos se insertan en cualquier orden, pero se extraen según su prioridad.
 La prioridad de un elemento se determina por su valor o según un criterio definido por un comparador.
 Generalmente, las colas de prioridad se implementan internamente como montículos (heaps), lo que
permite realizar las operaciones de inserción y extracción del elemento de mayor prioridad de manera
eficiente

Operaciones básicas

1. enqueue(): Añade un elemento al final de la cola.

 2. dequeue(): Elimina y devuelve el elemento del frente de la cola.

3. peek(): Devuelve el elemento del frente sin eliminarlo.

4. isEmpty(): Verifica si la cola está vacía.

5. size(): Devuelve el número de elementos en la cola.

Ventajas:

1. Eficiencia: Las colas permiten manejar flujos de datos de manera eficiente.

2. Simplificación de la implementación: Facilitan la implementación de sistemas de cola de impresión y otras

aplicaciones.

3. Flexibilidad: Pueden ser implementadas con diferentes tipos de prioridades.

Desventajas:

1. Limitaciones en el tamaño: Las colas tienen un tamaño limitado, lo que puede ser un problema en aplicaciones que
requieren manejar grandes volúmenes de datos.

2. Retroalimentación limitada: Las colas no proporcionan retroalimentación sobre los elementos que se están
procesando.
Ejemplos de implementación:

1. Cola Simple con ArrayList

2. Cola con Prioridad Doblemente Terminada con PriorityQueue

Aplicaciones practicas y casos de uso

1. Sistemas de cola de impresión: Las colas se utilizan para gestionar la impresión de documentos en orden.

2. Gestión de tareas: Las colas se utilizan para gestionar la ejecución de tareas en orden.

3. Algoritmos de búsqueda: Las colas se utilizan para gestionar la búsqueda de elementos en un árbol.

2. Listas

Definición y Tipos de Listas

En programación, una lista es una colección ordenada de elementos, donde cada elemento puede ser accedido por su posición
(índice). Las listas pueden crecer y encogerse dinámicamente, lo que las hace muy flexibles y adecuadas para muchos tipos
de tareas. En Java, las listas son una parte fundamental de la biblioteca de colecciones.

ArrayList

ArrayList es una implementación de una lista utilizando un array redimensionable. Permite el acceso rápido a elementos
mediante índices y es eficiente para operaciones de lectura.

Definición: Una lista implementada sobre un array dinámico que puede crecer según sea necesario.

Ventajas: Acceso rápido a elementos mediante índices, buena para búsquedas y lectura de elementos.

Desventajas: Inserciones y eliminaciones son costosas si no se realizan al final de la lista, ya que pueden requerir el
desplazamiento de elementos.

LinkedList

LinkedList es una implementación de una lista mediante nodos enlazados. Cada nodo contiene un elemento de datos y una
referencia al siguiente nodo en la lista.
Definición:

Una lista donde cada elemento está contenido en un nodo que apunta al siguiente nodo en la secuencia.

Ventajas: Inserciones y eliminaciones son eficientes, especialmente al comienzo y al final de la lista.

Desventajas: Acceso lento a elementos mediante índices debido a la necesidad de recorrer la lista.

Operaciones Básicas

 Inserción
ArrayList: Se realiza en tiempo constante O (1) si se inserta al final de la lista. Si se inserta en una posición
intermedia, puede ser O(n) debido al desplazamiento de elementos.
LinkedList: Inserciones al inicio o al final son O (1). Inserciones en una posición intermedia pueden ser O(n) si se
necesita recorrer la lista para encontrar la posición.
 Eliminación
ArrayList: Eliminaciones al final son O (1), pero eliminaciones en posiciones intermedias son O(n) debido al
desplazamiento de elementos.
LinkedList: Eliminaciones al inicio o al final son O (1). Eliminaciones en una posición intermedia pueden ser O (n).
 Búsqueda
ArrayList: Acceso mediante índice es O (1). Búsqueda secuencial de un elemento específico es O(n).
LinkedList: Tanto el acceso mediante índice como la búsqueda secuencial son O (n).
 Actualización
ArrayList: Actualización de un elemento por índice es O (1).
LinkedList: Actualización de un elemento por índice puede ser O (n).

Ventajas y Desventajas de Cada Tipo de Lista

ArrayList

Ventajas:

 Acceso rápido mediante índices.

 Mejor rendimiento para búsquedas y lecturas.

Desventajas:

 Inserciones y eliminaciones costosas en posiciones intermedias.

 Requiere redimensionamiento del array cuando se alcanza la capacidad máxima.
LinkedList

Ventajas:

 Inserciones y eliminaciones eficientes en cualquier posición.

 No requiere redimensionamiento.

Desventajas:

 Acceso lento mediante índices.

 Mayor uso de memoria debido a las referencias adicionales en cada nodo

Ejemplos de Implementación en Java

ArrayList

Aquí se importa la clase ArrayList del paquete java.util. Este paquete contiene las clases de colección más comunes en Java.

 Se define una clase pública EjemploArrayList. Dentro de esta clase, se define el método main, que es el punto de
entrada para la ejecución del programa.
 Se crea una instancia de ArrayList que almacenará elementos de tipo String. Inicialmente, la lista está vacía.
 Se añaden tres elementos a la lista utilizando el método add. Cada llamada a add agrega el nuevo elemento al final
de la lista.
 Se accede al elemento en el índice 1 (segundo elemento) utilizando el método get, y se imprime en la consola. Los
índices en ArrayList son de base cero, lo que significa que el primer elemento tiene el índice 0.
 El método set se utiliza para actualizar el elemento en el índice 1 con un nuevo valor, en este caso, "Elemento
actualizado".
  El método “remove” elimina el elemento en el índice 2 (tercer elemento) de la lista. Después de esta operación, la
lista se ajusta y los índices de los elementos restantes cambian en consecuencia.
 El método contains verifica si "Elemento actualizado" está presente en la lista. Si es así, se imprime "Elemento
encontrado".
 Finalmente, se imprime el contenido completo de la lista utilizando el método toString de ArrayList, que devuelve
una representación de cadena de los elementos en la lista.

LinkedList

Importar la clase LinkedList del paquete java.util. Este paquete contiene las clases de colección más comunes en Java, que se
utilizan para almacenar y manipular grupos de objetos.

 Se define una clase pública llamada EjemploLinkedList. Dentro de esta clase, se define el método main, que es el
punto de entrada para la ejecución del programa en Java. Todo el código que sigue dentro del método main se
ejecutará cuando se inicie el programa.
 Se crea una instancia de LinkedList que almacenará elementos de tipo String. Inicialmente, la lista está vacía.
 Se añaden tres elementos a la lista utilizando el método add. Cada llamada a add agrega el nuevo elemento al final
de la lista. Después de estas inserciones, la lista contiene:
"Elemento 1"
"Elemento 2"
"Elemento 3"
 Se accede al elemento en el índice 1 (el segundo elemento) utilizando el método get, y se imprime en la consola. En
este caso, se imprimirá "Elemento en el índice 1: Elemento 2".
 El método set se utiliza para actualizar el elemento en el índice 1 con un nuevo valor, en este caso, "Elemento
actualizado". Después de esta operación, la lista contiene:
"Elemento 1"
 "Elemento actualizado"
"Elemento 3"
 El método remove elimina el elemento en el índice 2 (el tercer elemento) de la lista. Después de esta operación, la
lista contiene:
"Elemento 1"
"Elemento actualizado"
 El método contains verifica si "Elemento actualizado" está presente en la lista. Si es así, se imprime "Elemento
encontrado". En este caso, dado que "Elemento actualizado" está en la lista, se imprimirá "Elemento encontrado".
 Finalmente, se imprime el contenido completo de la lista utilizando el método toString de LinkedList, que devuelve
una representación de cadena de los elementos en la lista. En este caso, se imprimirá "Contenido de la lista:
[Elemento 1, Elemento actualizado]".

Aplicaciones Prácticas y Casos de Uso

ArrayList

Almacenamiento de colecciones grandes donde el acceso rápido es crucial: Debido a su capacidad para acceder rápidamente
a los elementos mediante índices, ArrayList es adecuado para aplicaciones como cachés en memoria y listas de resultados de
búsqueda.

Aplicaciones donde las inserciones y eliminaciones son raras: Si la mayoría de las operaciones son lecturas, ArrayList es una
excelente opción debido a su eficiencia en estas operaciones.

LinkedList

Manipulación frecuente de datos: En aplicaciones donde los elementos son insertados y eliminados con frecuencia,
LinkedList es más eficiente.

Implementación de colas y deques: LinkedList es ideal para estructuras de datos como colas y deques donde las operaciones
de inserción y eliminación se realizan en ambos extremos de la lista.

Sistemas que requieren inserciones y eliminaciones constantes en el medio de la lista: Por ejemplo, en sistemas de
procesamiento de datos en tiempo real donde los datos son constantemente añadidos y removidos.

3. Pilas.

Una pila o Stack es una colección de elementos donde el último elemento agregado es el primero en ser eliminado, es una
estructura de datos basada en la idea de LIFO (Last In, First Out). Esto significa que el elemento que fue agregado más
recientemente es el primero en ser retirado. Esta estructura de datos se usa comúnmente para almacenar y manipular datos de
forma ordenada y eficiente. Es una estructura de datos lineal que se basa en el principio de último en entrar, primero en salir
(LIFO). Es una especie de anti-cola. Imagina una baraja de cartas o una pila de libros en una caja. El libro que puso en la pila
primero está en la parte inferior, y el primero que sacaremos de la caja es el libro que estaba en la parte superior, es decir, el
último que entró en la caja. Uno de los usos más importantes de la pila es organizar llamadas a subrutinas. El punto de
llamada en la pila almacena la dirección de retorno de la subrutina después de que finaliza (y posiblemente los parámetros
pasados). Con cada llamada anidada (incluida la recursiva) de subrutinas, se agregan nuevas direcciones de retorno a la pila.
Con cada operación de retorno de la subrutina (retorno), la dirección de retorno se elimina de la pila y se le transfiere el
control. Esta aplicación es tan importante para la programación que en la mayoría de los procesadores, la pila de retorno se
implementa en hardware en el conjunto de instrucciones. Sin embargo, en otros casos, la pila debe modelarse en estructuras
de datos más generales.

Operaciones básicas.

Cuando se habla de pilas, siempre se implementan 4 operaciones básicas. Las operaciones son las siguientes:

 Push: la operación Empujar se usa cuando desea agregar un elemento a la pila. Dependiendo de cómo haya
estructurado la pila, el nuevo elemento se agregará al frente o al final de la pila. Si la pila ya está llena, se mostrará
un mensaje de desbordamiento de pila.
 Objetc pop (): la función Pop se utiliza para expulsar o eliminar un miembro de la pila. Pop es diametralmente
opuesto a Push ya que estas dos operaciones ocurren en extremos opuestos de la pila. Si la pila ya está llena, se
mostrará un mensaje de subdesbordamiento.
 Objet peek (): esta función es principalmente para verificar el elemento superior de la pila. Peek devuelve el
elemento superior de la pila.
 boolean Empty (): devuelve verdadero si la pila está vacía y falso si la pila tiene al menos un miembro.

Ventajas.

Las pilas en Java permiten almacenar objetos y proporcionan un acceso fácil y rápido a los últimos elementos añadidos.
Además, son muy útiles para implementar funcionalidades de ‘undo’ y ‘redo’, pues para esto se pueden utilizar métodos para
guardar una copia reciente del estado de los datos.

Desventajas.

La principal desventaja de usar pilas en Java radica en que una vez que un objeto se ha agregado a la pila, solo se puede
acceder a él como el último elemento. El acceso a otras posiciones de la pila siempre requiere la eliminación previa de los
elementos superiores. Además, las pilas no proporcionan operaciones de búsqueda, ya que los elementos se ubican según su
orden de inserción.

Ejemplo.
Para nuestro ejemplo pondremos tres “esferas”, naranja, violeta y verde, en la pila. Revisemos la pila para ver si está vacía.
Luego, extraeremos bolas de la pila hasta que la pila esté vacía.

Dado que Stack se hereda de Vector Class e implementa la interfaz “List , Stack” , además de las clásicas operaciones push
y pop para esta estructura de datos para agregar y extraer elementos, también tiene operaciones estándar para “agregar ()” y
“eliminar ()” de estructura de lista. En nuestro ejemplo, la adición de elementos se puede implementar de la misma manera
utilizando el método “add()” . Sin embargo, puede extraer usando “remove()” solo con un elemento especificado, lo que no
tiene sentido para la estructura de datos de la pila.

Aplicaciones prácticas y casos de uso.

 Implementación de un historial de navegación: Utilizar una pila para almacenar las URL visitadas, de modo que
al retroceder se acceda a las URL en el orden inverso.
 Validación de sintaxis en lenguajes de programación: Emplear una pila para verificar la correcta apertura y cierre
de paréntesis, corchetes y llaves en código Java.
 Evaluación de expresiones matemáticas: Utilizar una pila para evaluar expresiones posfijas (notación polaca
inversa) de manera eficiente.
 Gestión de llamadas a funciones en un compilador: Utilizar una pila para gestionar el orden de las llamadas a
funciones y sus parámetros.
 Implementación de Undo/Redo en aplicaciones: Mantener una pila de operaciones realizadas para permitir
deshacer y rehacer acciones de manera secuencial.
 Backtracking en algoritmos de búsqueda: Utilizar una pila para realizar el seguimiento de opciones y facilitar el
retorno a estados anteriores en algoritmos de búsqueda.
 Manejo de historiales en editores de texto: Mantener una pila de estados anteriores del texto editado para permitir
deshacer cambios de manera ordenada.
 Gestión de llamadas a funciones recursivas: Utilizar una pila para almacenar las llamadas pendientes en funciones
recursivas y evitar desbordamientos de pila.
  Implementación de un gestor de tareas: Utilizar una pila para mantener un historial de tareas realizadas,
permitiendo deshacer y rehacer acciones de manera eficiente.
 Validación de palíndromos: Utilizar una pila para comparar caracteres en una cadena y verificar si es un
palíndromo.

4.Grafos (Graphs):

Definición. - Un grafo es una estructura compuesta por un conjunto de vértices (también llamados nodos) y un conjunto de
aristas (también conocidas como arcos o enlaces) que conectan pares de vértices. Los grafos se utilizan en diversas
disciplinas como la informática, la matemática, la biología y las ciencias sociales para modelar y analizar relaciones entre
objetos.

Componentes de un grafo:

1. Vértices (Nodos):
 Representan los puntos fundamentales de un grafo.
 Cada vértice puede contener información o ser identificado por una etiqueta única.
 En representaciones visuales, los vértices suelen dibujarse como puntos o círculos.
2. Aristas (Arcos):
 Representan las conexiones entre los vértices.
 Una arista conecta dos vértices, indicando una relación entre ellos.
Pueden ser de dos tipos:
 No dirigidas: La relación es bidireccional. Se representan con líneas simples.
 Dirigidas (Arcos): La relación es unidireccional y se representan con flechas.

Tipos de Grafos:

1) Dirigidos
Un grafo dirigido que también se le conoce como dígrafo, cada arista tiene una dirección específica. Esto significa
que la relación entre dos vértices es unidireccional.
Su aplicación: Modelado de sistemas donde la dirección de la relación es importante, como en redes de tráfico,
circuitos electrónicos, y grafos de dependencia.
2) No dirigidos
Un grafo no dirigido, las aristas no tienen dirección, lo que significa que la relación entre dos vértices es
bidireccional.
 Su aplicación: Modelado de sistemas donde la reciprocidad es inherente, como en redes de colaboración, mapas de
ciudades, y grafos de conexiones físicas.
3) Ponderados
Un grafo ponderado, cada arista tiene un peso o costo asociado. Este peso puede representar diferentes cosas, como
distancias, tiempos, costos, capacidades y más, etc.
Su aplicación: Problemas de optimización, como encontrar el camino más corto (algoritmo de Dijkstra), el árbol de
expansión mínima (algoritmo de Prim o Kruskal), y el flujo máximo en una red.

Representación de Grafos

I. Listas de Adyacencia
Una lista de adyacencia es una colección de listas, donde cada lista está asociada a un vértice del grafo. Cada entrada
en la lista de un vértice contiene los vértices adyacentes a él.
Ventajas:
-Eficiencia en espacio: Útil para grafos dispersos (con pocas aristas), ya que solo se almacenan las aristas existentes.
-Fácil adición de vértices y aristas: Agregar un vértice o una arista es sencillo y eficiente.
Desventajas:
-Acceso menos directo: Verificar si existe una arista entre dos vértices puede ser más lento en comparación con una
matriz de adyacencia.
II. Matrices de Adyacencia
Una matriz de adyacencia es una matriz cuadrada de tamaño nxn, donde n es el número de vértices. Cada entrada
A[i][j] indica si existe una arista entre los vértices i y j.
Ventajas:
-Acceso directo: Comprobar si existe una arista entre dos vértices es rápido, simplemente revisando la entrada
correspondiente en la matriz.
-Simplicidad: La estructura es simple y directa, lo que facilita algunas operaciones.
Desventajas:
-Ineficiencia en espacio: No es eficiente para grafos dispersos, ya que se necesita espacio O(n)2
independientemente del número de aristas.
-Dificultad para añadir vértices: Agregar nuevos vértices puede requerir la redimensión de la matriz, lo cual es
costoso.

Operaciones y algoritmos básicos

1. Búsqueda en profundidad DTS

2. Búsqueda en amplitud BFS

 3. Algoritmo de Dijkstra

Aplicaciones prácticas y casos de uso

Casos de Uso:

 Detección de Comunidades: Identificación de grupos de usuarios con intereses o conexiones comunes mediante algoritmos
de detección de comunidades.
  Recomendación de Amigos: Utilización de grafos para sugerir nuevas conexiones basadas en amigos comunes o intereses
compartidos.
 Análisis de Influencia: Determinación de los usuarios más influyentes en una red social analizando la centralidad de los
vértices.
 Exploración de Contenidos: Permitir a los usuarios descubrir nuevos productos o contenidos basándose en las conexiones
en el grafo.
 Análisis de Preferencias: Identificar patrones de preferencias y tendencias emergentes en la base de usuarios.
 Rutas Óptimas: Encontrar la ruta más corta o más rápida entre dos puntos utilizando algoritmos como Dijkstra o A*.
 Gestión del Tráfico: Analizar y predecir patrones de tráfico para optimizar la gestión del tráfico en tiempo real.
 Planificación de Viajes: Proveer itinerarios de viaje eficientes que minimicen el tiempo de desplazamiento o el costo.

Ejemplos de Uso:

 Facebook utiliza grafos para sugerir amigos, encontrar comunidades y analizar las interacciones entre usuarios para
mejorar la experiencia de usuario.
 Netflix utiliza grafos para recomendar películas y series a los usuarios basándose en sus visualizaciones anteriores y las
de usuarios con gustos similares.
 Google Maps utiliza grafos para calcular rutas óptimas, predecir tiempos de llegada y sugerir rutas alternativas en caso
de tráfico.
 Amazon utiliza grafos para recomendar productos a los usuarios y optimizar la gestión del inventario.

5.Árbol (Trees)

Un árbol en programación y estructura de datos es una estructura jerárquica que consiste en nodos conectados por aristas (o
enlaces). Cada nodo contiene un valor o dato y puede tener cero o más nodos hijos. Un árbol se define por la relación de
paternidad entre los nodos, donde un nodo raíz no tiene padre y todos los demás nodos tienen exactamente un padre.

Los árboles son considerados las estructuras de datos no Lineales y dinámicas de datos muy importantes del área de
computació.

Los árboles son muy utilizados en informática como un método eficiente para búsquedas grandes y complejas.

Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles.

Definición de un Árbol

Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.

Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.

Nodo Padre: Se utiliza este termino para llamar a todos aquellos nodos que tiene al menos un hijo.

Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.
Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en común dentro de la estructura.

Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura.

Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que ademas tiene al menos un hijo.

Tipos de árboles

1. Árbol Binario

Esta estructura se caracteriza por que cada nodo solo puede tener máximo 2 hijo, dicho de otra manera es un Árbol
n-ario de Grado 2

2. Árbol Binario de Búsqueda (BST)

La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los
fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles,tan sólo recordar que la propiedad que
define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha.

3. Árbol AVL

Básicamente un árbol AVL es un árbol binario de búsqueda al que se le añade una condición de equilibrio. Esta
condición es que para todo nodo la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.

4 . Árbol red black

Un Red-Black tree es un árbol donde un bit extra define el color del nodo ya sea rojo o negro. Éste cuenta con unas
reglas extra o nuevas para poder ser programado. Sirve para implementar arrays asociativos, como para recorrerlo de
forma ordenada, son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peor
caso, en la inserción y el borrado son mucho más eficientes que los arboles AVL. La versión persistente del árbol
rojo-negro requiere un espacio O(log n) para cada inserción o borrado, además del tiempo.

Operaciones básicas de árbol (trees)

Inserción: Agregar un nuevo nodo al árbol.

Eliminación: Quitar un nodo del árbol.
Búsqueda: Encontrar un nodo con un valor específico.
Recorridos: Preorden: Raíz, Izquierda, Derecha. Inorden: Izquierda, Raíz, Derecha. Postorden: Izquierda, Derecha,
Raíz.

Ventajas y desventajas de los tipos de árboles

Árbol de búsqueda binaria

Ventajas:
Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda.
Es el método más eficiente para encontrar elementos en un arreglo ordenado.
Desventaja:
 Este método funciona solamente con arreglos ordenados, por lo cual si nos encontramos con arreglos que no están
en orden, este método, no nos ayudaría en nada.

Árbol AVL

Ventajas de arbol AVL

El número de accesos al árbol es menor que en una lista enlazada

 Por ejemplo, en un árbol lleno que tenga n nodos el camino más largo que hay que recorrer es log2(n+1),
*Si n=15, – recorrido máximo en un ABB=log216=4 – recorrido máximo en una lista es n=15 Si n=1023, –
recorrido máximo en un ABB=log21024=10 – recorrido máximo en una lista es n=1023

Desventajas de un arbol AVL

- Árboles equilibrados

*Las búsquedas son más eficientes cuando el árbol está equilibrado

*Un árbol equilibrado es aquel en el que las ramas izquierda y derecha de cada nodo tienen aproximadamente la
misma altura (el arbol lleno sería el árbol equilibrado perfecto con todos los nodos con subárboles izq y dch de
la misma altura)

*Si los nodos que se van insertando en el árbol aparecen en orden aleatorio el árbol tenderá a ser equilibrado

Ejemplos de implementación en java

Implementación de un arreglo asociativo con un árbol de búsqueda binaria

Representamos el arreglo asociativo mediante un objeto que tiene una referencia de la raíz de un ABB:

Class Map extends Program {

Nodo raiz= null;
… operaciones del arreglo asociativo …
}
Cuando el arreglo está vacío, la raíz es nula y representa entonces el árbol vacío. Cuando el arreglo tiene al menos una
asociación, la raíz no es nula y referencia un objeto de la clase Nodo que se define como:

Class Nodo {
Int llave;
String val;
Nodo izq;
Nodo der;
Nodo(int llave, String val, Nodo izq, Nodo der) {
This.llave= llave;
This.val= val;
This.izq= izq;
This.der= der;
}
}
En donde izq referencia la raíz del ABB izquierdo, o nulo si el ABB vacío, y der referencia respectivamente el ABB derecho.
Un nodo almacena una asociación (llave, val), al igual que en una lista enlazada un eslabón almacena un asociación del
arreglo asociativo.
La siguiente figura muestra dos posibles representaciones de un arreglo asociativo con asociaciones {3->”hola”, 5->”que”,
10->”tal”}:

Aplicaciones prácticas

Las aplicaciones más habituales para las estructuras de tipo árbol son:

Representación de modelos jerárquicos: todo modelo en el cual existan objetos que puedan contener dentro otros objetos (por
ejemplo, la estructura de archivos y carpetas, o bien la representación de organigramas de usuarios).

Optimización de búsqueda de datos mediante índices: los primeros sistemas de archivos de datos y posteriormente los
motores de bases de datos implementaron índices para optimizar la búsqueda de un registro mediante claves. Básicamente,
consta de un árbol B+, en el cual cada hoja (o nodo) contiene un valor numérico, que representa la mediana de su jerarquía.
Sus nodos hijos tendrán valores inferiores (nodos hijos a la izquierda) y superiores (nodos hijos a la derecha), y estos últimos
serán punteros al registro al cual representan.

Comparación y Contraste:Según eficiencia complejidad temporal y espacial

Colas

Eficiencia:

 Inserción (enqueue): (constante).

 Eliminación (dequeue): (constante).

Complejidad temporal:

 Búsqueda: Si no se conoce la posición del elemento.

Complejidad espacial:

 Para almacenar n elementos.

Pilas (Stack):

Eficiencia:

 Inserción (push): (constante).

 Eliminación (pop): (constante).

Complejidad temporal:

 Búsqueda: Si no se conoce la posición del elemento.

Complejidad espacial:

 Para almacenar n elementos.

Árboles:

Eficiencia:
  Inserción y búsqueda: En árboles balanceados.

Complejidad espacial:

 Para almacenar n nodos.

Grafos:

Eficiencia:

 Búsqueda y recorrido: Varía según el algoritmo (DFS, BFS, Dijkstra, etc.).

 Complejidad espacial:O(n + m) (lineal) para almacenar n nodos y m aristas.

Listas:

Eficiencia:

 Inserción y eliminación: O(1) (constante) para listas enlazadas, O(n) (lineal) para listas basadas en
arrays.
 Búsqueda: O(n) (lineal) si no se conoce la posición del elemento.
 Complejidad espacial:
 Para almacenar n elementos.

Conclusiones:

El estudio y la aplicación de estructuras de datos en Java no solo es esencial para el desarrollo de software eficiente, sino que
también es fundamental para resolver problemas complejos de manera efectiva. A medida que los datos continúan creciendo
en volumen y complejidad, las estructuras de datos seguirán siendo un área crítica en la informática y el desarrollo de
software.

Comprender y aplicar correctamente las estructuras de datos es esencial para cualquier programador. Te permiten resolver
problemas de manera eficiente y construir algoritmos robustos

Optimizar algoritmos de búsqueda y ordenamiento mejora el rendimiento. En aplicaciones móviles, estructuras de datos
eficientes optimizan la experiencia del usuario. Los grafos en redes sociales identifican comunidades e influenciadores. Las
estructuras de datos persistentes y distribuidas aseguran la integridad y disponibilidad de los datos.

Referencias:

 https://amsoft.medium.com/dominando-las-estructuras-de-datos-en-java-pilas-y-colas-09a4279264b1
 https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html
 Estructuras de Datos Abstractas en Lenguaje Java- Carlo Casorzo G.
 Documentación Oficial de Java:
 ArrayList (Java Platform SE 8 ) (oracle.com)
 LinkedList (Java Platform SE 8 ) (oracle.com)
 (https://www.aprenderaprogramar.com/index.php?option=com_content&view=article&id=608:la-estructura-de-
datos-pila-en-java-clase-stack-del-api-java-ejemplo-simple-y-ejercicios-resueltos-
cu00923c&catid=58&Itemid=180 )
 (Pilas en Java - Go Coding)
 https://www.apinem.com/grafos-en-programacion/
 https://www.apinem.com/grafos-en-programacion/#8-grafos-ponderados
 https://www.apinem.com/grafos-en-programacion/#13-usos-comunes-de-grafos-en-el-desarrollo-web
 https://www.uv.mx/personal/ermeneses/files/2021/08/Clase8-Arboles.pdf
 https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
 https://ccia.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_BB.htm
 https://www.hci.uniovi.es/Products/DSTool/avl/avl-queSon.html
 https://audreyn.medium.com/red-black-tree-d2dae804a197
 https://www.apinem.com/arboles-programacion/
 https://ed.team/comunidad/ventajas-y-desventajas-de-la-busqueda-binaria
 https://prezi.com/p/zvzthwaropip/arboles-avl/
 https://users.dcc.uchile.cl/~lmateu/CC10A/Apuntes/arboles/index.html
 https://es.quora.com/Cu%C3%A1les-son-las-aplicaciones-m%C3%A1s-habituales-para-las-estructuras-de-datos-de-
tipo-%C3%A1rbol