Clase arboles - BDD

Introducción a los Árboles en Grafos

Concepto de Árbol

• Se inicia la clase sobre árboles, un tipo específico de grafo. Se menciona que se trabajará con un grafo particular y se establece la conexión con conceptos previos.

Grado de un Árbol

• El grado de un árbol se define como la máxima cantidad de hijos o subárboles que puede tener cada nodo. Este concepto es similar al grado en grafos, donde el grado se refiere a las relaciones salientes desde un nodo.

• La cantidad de relaciones salientes determina el grado del nodo, y el mayor número entre ellos define el grado del árbol.

Dirección en los Árboles

• Aunque los árboles son grafos dirigidos, su representación gráfica no siempre muestra explícitamente la dirección. Dependiendo de cómo se dibuje (de arriba hacia abajo o de izquierda a derecha), las relaciones seguirán esa dirección.

Características del Grado

• Se aclara que el conteo del grado comienza desde la raíz. Por ejemplo, si una raíz tiene 4 relaciones salientes, se considera un árbol de grado 4. Un árbol binario es aquel con un grado máximo de 2.

• Los árboles pueden ser clasificados según su grado: alternarios (grado mayor a 2), cuaternarios (grado 4), pentarios (grado 5), o genéricamente n-arios.

Condiciones para Definir un Árbol

Requisitos Esenciales

• Para que un grafo sea considerado un árbol debe cumplir ciertas condiciones:

• Debe ser dirigido.

• No debe contener ciclos; debe ser acíclico.

• Debe existir un único camino entre cada par de nodos.

Ejemplificación y Comparación

• En comparación con otros grafos, en los árboles hay una única vía para acceder a todos los nodos desde la raíz. Esto contrasta con otros tipos de grafos donde puede haber múltiples caminos entre nodos.

Ejemplos Prácticos y Dudas Comunes

Análisis Visual

• Se presentan ejemplos visuales para ilustrar qué constituye o no un árbol. Un caso específico muestra que si hay múltiples caminos entre dos nodos, no cumple con la definición necesaria para ser considerado como tal.

Discusión sobre Nodos Aislados

• Se discute si una estructura con solo un nodo puede considerarse como árbol. La conclusión es afirmativa bajo ciertas condiciones iniciales aunque aún no esté completamente definido por sus relaciones.

Diferenciación entre Tipos de Árboles

Clasificación General

• Se introduce la diferencia entre árboles algebraicos y computacionales, destacando que ambos tienen características específicas pero cumplen diferentes funciones dentro del contexto matemático y computacional.

Árboles Algebraicos y Computacionales

Definiciones de Árboles

• Se introducen las condiciones de un árbol algebraico y se define un sub-árbol como un conjunto del árbol que es un sub-árbol en sí mismo.

• Un sub-árbol principal derecho de un nodo incluye todos los nodos accesibles desde ese nodo, ejemplificado con nodos A, B, C, D.

Concepto de Árbol Principal Derecho

• Un árbol es considerado principal derecho si existe un único nodo desde el cual se puede alcanzar todo el árbol completo.

• Se menciona que el árbol presentado tiene una única raíz, lo que permite acceder a todos los nodos por un único camino.

Profundidad y Niveles del Árbol

• La profundidad se define como la distancia desde la raíz hasta cada nodo; por ejemplo, la raíz tiene profundidad 0 y otros nodos tienen profundidades incrementales.

• Los niveles del árbol son conjuntos de nodos; la altura del árbol se refiere a la cantidad total de niveles presentes.

Hojas y Ramas en el Árbol

• Las hojas son los nodos sin relaciones salientes; no necesariamente están al mismo nivel. En este caso, hay seis hojas identificadas.

• Los nodos que no son ni raíz ni hoja se denominan ramas. Ejemplificado con los nodos V larga, E y J.

Comparación con Estructuras Naturales

• Se compara la estructura del árbol computacional con una planta: raíces (nodo inicial), ramas (nodos intermedios), y hojas (nodos finales).

• Se discute cómo las ramas pueden surgir directamente desde la base sin necesidad de un tronco definido.

Presentaciones Computacionales

• Se introduce el concepto de presentaciones computacionales estáticas en grafos, mencionando matrices y vectores como formas representativas.

Estructura de Árboles Binarios y su Implementación

Introducción a la Estructura de Árboles

• En un árbol binario, la raíz se encuentra en la posición cero, con los niveles organizados por carga. Los nodos se distribuyen en un vector siguiendo una estructura jerárquica.

• Cada nodo tiene hijos que se denominan "hijo izquierdo" y "hijo derecho". Por ejemplo, el nodo 1 tiene como hijo izquierdo al nodo 2 y como hijo derecho al nodo 3.

Conversión entre Estructuras

• La conversión de un árbol dinámico a uno estático no es eficiente, ya que implica destruir la estructura existente para crear una nueva. Esto representa un gasto computacional significativo.

• La implementación estática es específica para árboles binarios; no es aplicable a árboles con grados mayores (por ejemplo, grado 5).

Cálculo de Posiciones en el Vector

• Para identificar los hijos en un árbol binario, se utilizan fórmulas específicas basadas en la posición del vector. Por ejemplo, el hijo izquierdo de un nodo se calcula usando su posición.

• Si el nodo C está en la posición 2 del vector, su hijo derecho estaría en la posición calculada mediante fórmulas matemáticas específicas.

Manejo de Nodos Vacíos y Overflow

• Se discute cómo manejar nodos vacíos o nulos cuando no hay hijos asignados. Un overflow puede ocurrir si intentamos acceder a posiciones fuera del rango del vector.

• La fórmula para encontrar el padre de un nodo también depende de su posición dentro del vector.

Implementación Dinámica vs Estática

• Al implementar árboles con grados diferentes (por ejemplo, grado 3 o grado 4), las fórmulas cambian ligeramente para adaptarse al número de hijos por nodo.

• En estructuras dinámicas, cada nodo puede tener punteros hacia sus hijos. Esto permite flexibilidad en la cantidad de nodos e hijos que pueden ser añadidos o eliminados.

Grado Variable y Atributos

• En implementaciones con grado variable, los nodos pueden tener atributos tanto para sí mismos como para las relaciones entre ellos. Esto permite una mayor personalización y funcionalidad dentro del árbol.

Estructura de Árboles y Balanceo

Conceptos Básicos de Árboles

• Se describe la estructura de un árbol con nodos, donde cada nodo puede tener descendencia. En este caso, el nodo B tiene descendencia F y G.

• Cada lista en la estructura representa un nivel, donde los nodos no hoja tienen el mismo grado. Un árbol completo se define por esta característica.

Características de los Árboles

• Un árbol es considerado completo si todos los nodos que no son hojas tienen el mismo grado. En este ejemplo, se menciona un árbol binario donde todos los nodos no hoja tienen grado 2.

• Se presenta un ejemplo de un árbol que no es completo porque uno de sus nodos (grado 1) no cumple con la condición del máximo número de hijos.

Balanceo en Árboles

• La noción de balanceo se compara con el equilibrio en un automóvil; un árbol está balanceado si las ramas desde la raíz tienen una cantidad similar o una diferencia indivisible entre ellas.

• Se discute cómo determinar si un árbol es balanceado al observar la cantidad de nodos en cada rama desde la raíz.

Ejemplos Prácticos

• Se analiza un caso específico donde hay tres nodos a la izquierda y dos a la derecha, concluyendo que el árbol está balanceado debido a que la diferencia es uno.

• Si se añade otro nodo a una rama ya desequilibrada, esto afectará negativamente el balanceo del árbol.

Profundización en Estructuras

• El concepto de "perfectamente balanceado" se aplica a todos los nodos del árbol, no solo a la raíz. Esto implica que cada subárbol también debe cumplir con las condiciones de balanceo.

• En futuras clases se explorará más sobre árboles binarios de búsqueda y su necesidad de mantener algún tipo de balanceo para optimizar búsquedas.

Crecimiento y Capacidad Máxima

• El crecimiento exponencial del número máximo posible de elementos en un árbol depende del grado definido y el número total de niveles.

• La fórmula para calcular el número máximo de elementos es: textgrado^textniveles - 1 . Por ejemplo, para grado 2 y 3 niveles, hay como máximo 7 nodos posibles.

• Para árboles más grandes (por ejemplo, grado 2 con 6 niveles), se pueden alcanzar hasta 63 nodos utilizando la misma fórmula mencionada anteriormente.

Introducción a los Algoritmos de Recorrido en Árboles

Conceptos Básicos de Recorridos en Árboles

• Se introduce el concepto de recorrer un árbol, comparándolo con grafos. Se menciona que se puede hacer un recorrido por niveles, comenzando desde la raíz y avanzando hacia abajo.

• El "barrio" es definido como una forma de recordar todos los nodos del árbol una única vez. Se presentan tres métodos para el recorrido: pre-orden, pos-orden e in-orden, siendo este último aplicable solo a árboles binarios.

Métodos de Recorrido

Pre-Orden

• En el recorrido pre-orden, se comienza en la raíz y se realizan llamadas recursivas antes de procesar el nodo actual.

Pos-Orden

• En el pos-orden, primero se hacen todas las llamadas recursivas y luego se trabaja sobre el nodo. Este método imprime al final.

In-Orden

• El in-orden implica recorrer primero por la izquierda, imprimir el nodo actual y luego continuar hacia la derecha. Este método es más complejo visualmente pero no necesariamente más eficiente.

Comparación entre Métodos

• No hay ventajas significativas entre los diferentes métodos de recorrido; todos pasan por cada nodo una única vez. Sin embargo, algunos algoritmos requieren un tipo específico de recorrido para funcionar correctamente.

Implementación Práctica

Estructura del Código

• La implementación incluye un código base donde se pasa la raíz del árbol a funciones recursivas que manejan los recorridos según su tipo (pre-order o post-order).

Ejemplo con Árboles de Expresión

• Se discute cómo los árboles de expresión son utilizados en calculadoras para representar operaciones matemáticas complejas mediante nodos binarios. Esto permite realizar cálculos secuenciales como suma y resta utilizando estructuras jerárquicas.

¿Cómo implementar estructuras de datos en bases de datos?

Discusión sobre árboles y operaciones

• Se menciona la elección de un barrio específico para trabajar con árboles, refiriéndose a diferentes tipos de recorridos como inorden, preorden y postorden.

• Se introduce el concepto de un algoritmo que trabaja con un árbol por niveles, destacando su relación con los algoritmos de búsqueda.

• Se aclara la terminología: POSORDEN se refiere a una operación específica dentro del contexto de árboles binarios.

• La impresión es discutida como una acción que no realiza cálculos, sino que simplemente muestra resultados en pantalla.

Implementación de grafos en bases de datos

• Se plantea cómo implementar un grafo en una base actual y se discute la cantidad adecuada de tablas necesarias para representar nodos y relaciones.

• La sugerencia es crear dos tablas: una para nodos (con identificadores únicos) y otra para relaciones entre nodos.

• Las relaciones se describen como conexiones entre nodos origen y destino, utilizando claves foráneas separadas para cada uno.

Consultas y estructura gráfica

• Se menciona cómo realizar consultas sobre la tabla de relaciones, enfatizando la importancia del nodo origen y destino en las descripciones.

• Se compara el uso de bases de datos relacionales con bases orientadas a grafos, mencionando Neo4j como ejemplo destacado por sus funcionalidades gráficas.

Ejemplo práctico: Instagram

• En el contexto social media, se explica cómo los usuarios pueden ver quiénes siguen o son seguidos mediante estructuras gráficas representativas.

• La implementación implica almacenar información sobre las relaciones entrantes y salientes entre usuarios dentro del sistema.

Estructura de Datos en Bases de Datos

Introducción a la Estructura de Nodos

• La estructura se asemeja a una lista de ausencias, pero los nodos no están enlazados por punteros debido al manejo de datos masivos.

• Se utilizarán índices para acceder rápidamente a la información del usuario, como quién sigue y las publicaciones relevantes.

Manejo de Relaciones entre Usuarios

• En lugar de punteros tradicionales, se gestionan relaciones mediante índices que apuntan a usuarios seguidos y seguidores.

• Cada relación tendrá atributos como fecha de inicio del seguimiento y punteros para enlazar todas las relaciones entrantes y salientes.

Implementación en Memoria

• La implementación en memoria se asemeja a un grafo, utilizando estructuras específicas para nodos y arcos. Esto es común en bases de datos orientadas a grafos.

• Ejemplos prácticos incluyen aplicaciones como Instagram o sistemas más complejos como vuelos comerciales o rutas de micros.

Diferencias entre Bases de Datos SQL y NoSQL

• Las bases NoSQL pueden ser documentales o clave-valor; ambas son diferentes pero cumplen funciones distintas dentro del mismo grupo general.

• A medida que avanza el curso, se explorarán comparaciones sobre consistencia entre diferentes tipos de bases de datos.

Consistencia y Funcionalidades

• Aunque es posible implementar funcionalidades similares entre SQL y NoSQL, cada tipo tiene sus ventajas según el contexto (ej., alta disponibilidad vs. consistencia).

• La programación necesaria para mantener la consistencia varía: SQL ofrece mecanismos automáticos mientras que NoSQL requiere programación adicional para lograrlo.

Importancia del Modelado en Programación Actual

• Los conceptos teóricos sobre modelado son cruciales hoy en día debido al avance tecnológico; entender cuándo usar cada tipo es esencial para los profesionales actuales.

¿Cómo se relacionan las bases de datos con las aplicaciones?

Funcionalidad y tipos de bases de datos

• Se discute la importancia de entender la funcionalidad de las bases de datos, mencionando que hay diferencias significativas entre bases de datos relacionales y no relacionales. La necesidad de una base nacional es cuestionada.

• Se menciona que no existe una relación uno a uno entre aplicaciones y bases de datos; una aplicación puede utilizar múltiples bases, lo que resalta la complejidad en el acceso a los datos.

• Ejemplo práctico: Instagram utiliza diferentes tipos de bases para gestionar seguidores y otras funcionalidades, lo que ilustra cómo distintas necesidades pueden requerir distintos motores de base de datos.

Elección del motor adecuado

• Se plantea la pregunta sobre cuándo usar un motor específico como Oracle o PostgreSQL. La elección depende del contexto y las funcionalidades requeridas por el proyecto.

• Se discuten aspectos económicos relacionados con licencias, destacando que Oracle es más costoso en comparación con opciones gratuitas como MySQL, lo cual influye en la decisión sobre qué base utilizar.