UNIVERSIDAD CENTRAL DEL ECUADOR
FACULTAD INGENIERÍA Y CIENCIAS APLICADAS
Integrantes:
• Alex Chicaiza
• José Cuadro
• Karla Domínguez
• María del Carmen Tipán
Docente:
Ing. Boris Herrera
2024
01. Definiciones
• Terminología de árboles
• Propiedades
02. Tipos de arboles
• Arboles binarios
• Arboles multicaminos
03. Recorridos de árbol binario
• Inorden
• Posorden
• Preorden
Los Árboles son las estructuras de datos mas
utilizadas, pero también una de las mas
complejas que se caracterizan por almacenar
sus nodos en forma jerárquica y no en forma
lineal como las Listas Ligadas,
Colas,Pilas,[Link] muy utilizados debido a que
son un método eficiente para búsquedas
grandes y complejas.
• Los árboles son una de las estructuras de
datos no lineales que sirve para representar
estructuras de información jerárquicas y
direcciones o etiquetas de una manera
organizada.
• Un árbol consta de un número finito de
elementos, a estos se les llama nodos estos
nodos están unidos por líneas llamadas
ramas.
• Nodo Raíz: Se refiere al primer nodo de un árbol, Solo un nodo
del árbol puede ser la raíz.
• Nodo Hoja: Son todos los nodos sin hijos, que siempre están en
los extremos de la estructura.
• Nodo Interior o Rama: Estos son todos aquellos nodos que no
• Nodos: Se le llama nodo a cada elemento que contiene el son la raíz y que además tiene al menos un hijo.
á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 término para llamar a todos
aquellos nodos que tienen al menos un hijo.
• Nodo hijo: Los hijos son todos aquellos nodos que tienen
un padre.
• Nodo hermano: Los nodos hermanos son aquellos nodos
que comparten un mismo padre en común dentro de la
estructura.
• Grado: Número de hijos de un nodo y está
• Altura: Se le llama altura al número máximo de niveles de un árbol. . limitado por el Orden, ya que este indica el
• Nivel: El nivel de un nodo es su distancia a la raíz, o longitud del número máximo de hijos que puede tener un
camino que lo conecta al nodo raíz. nodo.
• Peso: Es el número de nodos que tiene un árbol. • Camino: Secuencia de nodos conectados
• Orden.: El Orden de un árbol es el número máximo de hijos que dentro de un árbol.
• Longitud del camino: Cantidad de nodos que se
puede tener un Nodo.
deben recorrer para llegar desde la raíz a un
nodo determinado.
• Sub-Árbol: Conocemos como Sub-Árbol a todo
Árbol generado a partir de una sección
determinada del Árbol
Los arboles pueden clasificarse tomando en cuenta su estructura y funcionamiento.
A continuación, se presentan los tipos de árboles más utilizados (Cairó & Guardati, 2006):
Árboles binarios Árboles multicaminos
• Árboles binarios distintos • Árboles-B
• Árboles binarios similares • Árboles B+
• Árboles binarios equivalentes • Árboles 2-3
• Árboles binarios completos
• Árboles binarios llenos
• Árboles binarios degenerados
• Árboles binarios de búsqueda
• Árboles equilibrados
Árbol: AVL y Rojo-Negro
Árbol Binario
• Esta estructura se caracteriza por que cada nodo solo puede tener
máximo 2 hijos, dicho de otra manera, es un árbol grado dos.
Árbol Binario Árbol Binario Árbol Binario
Distinto Similar Equivalente
Son similares cuando sus estructuras son Aquellos que son similares y además los
Son distintos cuando sus estructuras
idénticas, pero la información que nodos contienen la misma información.
son diferentes.
contienen sus nodos difiere entre sí.
Árbol Binario
Completo
Un árbol binario completo de profundidad n es un árbol en
el que:
• Para cada nivel desde 0 hasta n−1, todos los nodos
están completamente llenos.
Árbol Binario
Llenos
Es un árbol lleno donde todos los nodos tienen cero o dos
hijos. Es decir, no existe un nodo que tenga un solo hijo.
Árbol Binario
Degenerado
• Es un tipo especial denominado árbol degenerado en el
que hay un solo nodo hoja y cada nodo no hoja sólo
tiene un hijo. Equivale
Árbol Binario
De Búsqueda
• Un árbol binario que tiene los nodos ordenados de
alguna manera se conoce como árbol binario de
búsqueda.
Árbol Binario
Equilibrado
• Árboles binarios en los cuales la altura de los
subárboles izquierdo y derecho de cualquier nodo no
difieren en más de una unidad.
• Esto incluye AVL y árboles rojo-negro.
Árbol Binario
Rojo - Negro
Árbol Binario
AVL • Los árboles rojo-negro son una buena opción cuando las
operaciones de reequilibrio deben ser eficientes, o
cuando el espacio es una restricción
• AVL: Adelson-Velskii y Landis
creadores del árbol.
• Los árboles AVL son una buena
opción cuando se necesita un
rendimiento de búsqueda,
inserción y eliminación rápido.
Árbol Binario
Multicaminos
• Un árbol multicaminos es una estructura de datos
homogénea, dinámica y no lineal, en donde a cada nodo
le pueden seguir una cantidad n de nodos hijos.
Árbol Binario-B Árbol Binario B+ Árbol Binario 2 - 3
• La raíz puede tener cualquier • Todas las claves se encuentran en las • Se define como un árbol en donde los
número de claves. hojas. nodos no terminales tienen 2 o 3
• Todas las hojas se encuentran a la • Cualquier camino desde la raíz hasta hijos.
misma profundidad, h la clave tiene la misma longitud. • Todos los nodos hoja tienen la misma
distancia desde la raíz.
RECORRIDO INORDEN
Atraviesa las hojas del lado izquierdo, pasa por la raíz y finaliza en las hojas
del lado derecho.
RECORRIDO POSORDEN
Atraviesa las hojas del lado izquierdo, pasa por las hojas del lado derecho y
termina en la raíz.
RECORRIDO PREORDEN
Visita primero la raíz, atraviesa las hojas de lado izquierdo y termina en las
hojas del lado derecho.
43
10 54
Recorrido:
8 15 50
8, 10, 15, 43,
50, 53, 54
53
43
10 54
Recorrido:
8 15 50
8, 15, 10, 53,
50, 54, 43
53
43
10 54
8 15 50
53
•
•
[Link] L. (2013) “Recorrido y búsqueda en árboles”.
[Link]
content/uploads/2017/06/[Link]
[Link] (2021) “Árboles Binarios Explicación e Implementación en Java”.
[Link]
[Link]ía, M. E. (s/f). La Estructura de datos Árbol. En Estructura de Datos (p. 13).
[Link]
[Link], O. (2014, agosto 22). Estructura de datos – Árboles. OSCAR
BLANCARTE SOFTWARE ARCHITECT.
[Link]
[Link]ó, O. y Guardati, S. (2002). Estructuras de Datos, 2da. Edición. McGraw-Hill.
[Link], H. (s/f). Ciencias computacionales. Instituto Nacional de Astrofísica,
Óptica y Electrónica.
[Link]
tico/Programacion_Estructuras_Datos/Capitulo_9_Arboles.pdf
7.Árbol B. (2016, abril 7). Estructura de Datos II.
[Link]
[Link] B+. (s/f). [Link].
[Link]
[Link]: Herramienta para la programación con estructuras de datos. (s/f).
[Link]. [Link]
[Link], D. G. (s/f). Arboles M-Way, 2-3 y 2-3-4. SlideShare.
[Link]
[Link], F. (s/f). Árbol rojo-negro. SlideShare.
[Link]
