Estructura de Datos: Árboles y sus Componentes Básicos

Cursos Empresas Blog Live Conf Precios

Contenido del curso

Bienvenido al Curso

1
Algoritmos y Estructuras de Datos: Curso Básico
02:17 min

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

41
Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento
11:14 min

¿Qué sigue?

42
Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos
02:26 min

Tomar examen

Un árbol es una estructura de datos similar a una lista pero en lugar de que cada nodo apunte al siguiente de forma lineal, cada nodo apunta a un número de nodos.

Un árbol es un ejemplo de una estructura de datos no lineal y es la forma de representar la naturaleza jerárquica de una estructura en forma gráfica. Los árboles también funcionan como un tipo de datos abstracto que cuenta con su definición y descripción de propiedades y operaciones, y se diferencia principalmente de las listas, queues (colas) y pilas porque a diferencia de estas no se utiliza para ordenar elementos de forma lineal.

La raíz (root) de un árbol es el nodo sin nodos padres, un árbol puede tener máximo una raíz, como el nodo A en el ejemplo anterior.
Un enlace o "edge" se refiere al enlace entre un nodo padre a un nodo hijo.
Un nodo sin nodos hijos se conoce nodo "hoja" como los nodos E, J, K, H, I.
Los nodos hijos del mismo padre se conocen como "hermanos" (Siblings) por ejemplo, los nodos B, C, D son nodos hermanos hijos de A.
Por otro lado, los nodos anteriores a un nodo dado en la ruta hacia la raíz se conocen como ancestros, como G, C, y A para el nodo K en nuestra imágen de ejemplo.
El set de todos los nodos a cualquier profundidad dada se conoce como "nivel del árbol" en nuestro ejemplo B, C, D son del mismo nivel (nivel 1) siendo la raíz el nivel 0.

La profundidad de un nodo es la longitud del camino desde la raíz hasta el nodo, por ejemplo el nodo G tiene una profundidad de 2, A(1) - C(2) - G.
La altura de un nodo es el largo del camino del ndo al nodo más profundo por ejemplo en nuestra imágen la altura de B es 2, B - F(1) - J(2).
La altura del árbol es la altura máxima entre todos los nodos en un árbol, para un árbol la altura y la profundidad retornará el mismo valor, pero para nodos individuales podemos tener diferentes resultados, en el caso de nuestro árbol de ejemplo la altura y profundidad son de 3.

Estructura de Datos: Árboles y sus Componentes Básicos

Comentarios

Gabriel Vargas Monroy

Estudiante

Leisy Karina Algarra Fernandez

Estudiante

Moisés Manuel Morín Hevia

Estudiante

Fernando Famanía

Estudiante

Alfredo Alejandro Frias Sandia

Estudiante

GERARDO EMMANUEL ALONSO CELIS

Estudiante

Karen Paola Diaz Duarte

Estudiante

Carlos Santaniello

Estudiante

Efraín Hernández García

Estudiante

Zalo Testa

Estudiante

Youssef Abarca

Estudiante

Bernardo Aguayo Ortega

Estudiante

Nicolas Ovalle

Estudiante

Youssef Abarca

Estudiante

Nicolas Alpargatero

Estudiante

Carlos Enrique Ramírez Flores

Estudiante

Eduardo Monzón

Estudiante

Juan Pablo Perez

Estudiante

Harrinson Quintero

Estudiante

Pablo Aquino

Estudiante

Karen Paola Diaz Duarte

Estudiante

Henry Gutierrez Mora

Estudiante

José Padrón

Estudiante

Wilson Erik Ramírez Franco

Estudiante

Ricardo Celis

Profesor

Samuel Hurtado marin

Estudiante

Camilo Alexander Velandia Velandia

Estudiante

También hay que saber que los arboles se puede dividir dependiendo sus reglas y pueden haber arboles que al agregarle un nuevo nodo este se equilibra automáticamente(quiere decir que cada una de las hijas tiene una profundidad similar) como lo son:

Arbol AVL
Arbol Roji-Negro

PD: El arbol de la primera imagen se conoce como arbol n-ario significa que cada uno de sus nodos puede tener 2 o mas hijas.

PD-2: El arbol de la segunda imagen es un arbol binario ya que cada uno de sus nodos tiene como máximo 2 hijas, sin faltar a la regla

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.

Con un árbol Elon Musk gano sus primeros millones (.zip)

Exacto, Zip2 se vendio por mas de 300 millones.

Tengo una duda, en la explicación dice "La profundidad de un nodo es la longitud del camino desde la raíz hasta el nodo, por ejemplo el nodo G tiene una profundidad de 2, A(1) - C(2) - G."

Puede que este mal redactado y lo que quieran dar a entender sea lo siguiente: "La profundidad de un nodo es la longitud del camino desde la raíz hasta el nodo, por ejemplo el nodo G tiene una profundidad de 2, A(0) - C(1) - G."

Profundidad: Enlaces hacia la raíz. Altura: Enlaces hacia la hoja. Para una raíz la altura y la profundidad son la misma.

Esta muy bien explicado todo. Muchas gracias! ;)

Tengo entendido que la red Blockchain de Bitcoin funciona como un árbol Merkle. ¿Qué características en particular tiene ese tipo de árbol?

En el caso de Blockchain, los nodos que están más debajo deben pasar la información de abajo hacia arriba, es decir desde el nodo n al no A o el root. De manera que si se rompe un enlace o nodo los demás conservan la misma informacion

Una de sus características principales es que tiene la particularidad que cada nodo se etiqueta con un hash pero este último surge de la concatenación de las etiquetas de los hashes de sus nodos ancestros si no entiendo mal.

Interesante

ya casi acabamos

¿H e I son nodos hermanos al igual E y F?

La teoría por el momento se entiende ✅

lo podemos visualizar con ejemplos aquí: https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html

Interesante, gracias por compartir.

Gracias por el documento extra.

Excelente la explicación.

Genial, me quedo más claro los conceptos sobre árboles.

Aprendiendo más. Gracias!!

Estos temas son cruciales para llega Analitycs, IA, ML..

Excelente material, muy claro toda la explicación.

Excelente material, muchas gracias!

gracias Wilson!

Muy util para manejar html con codigo de programación entender los arboles.

genial

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort

Ordenamiento de Arrays con MergeSort en C

Algoritmos de Ordenamiento de Datos de Mayor a Menor

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Ordenamiento Quick Sort en Python paso a paso

Algoritmos 'Greedy'

Algoritmos Voraces: Principios y Aplicaciones Prácticas

Implementación de Algoritmo Greedy para Cambio de Monedas

Cambio de Monedas en C++: Implementación y Ejecución

Grafos y árboles

Introducción a Árboles y Grafos: Estructuras de Datos Básicas