UNIVERSIDAD NACIONAL MAYOR DE
SAN MARCOS
Universidad decana de América
Facultad de Ingeniería de Sistemas e
Informática
Escuela Profesional de Ingeniería de Sistemas.
Estructura de Datos
Prof. Gilberto A. Salinas
Semana 01
Estructura de datos no lineales
Arboles en General
(n-arios o multicamino)
Ciclo 2021-1
Agenda
1. Introducción
2. Definición
• Características
3. Conceptos de arboles
4. Operaciones
5. Aplicaciones
6. Referencias
5
1. Introducción
1. ¿Qué es un arbol?
• Un arbol es un TAD que almacena elementos con una relacion jerárquica entre
ellos.
• Relación padre e hijo entre sus elementos
• Facilita la representación de la realidad:
• Estructura de sistema de archivos de nuestra PC.
• Arbol genealógico
• Organigramas
• Estructura de un libro
• Sitios web
• Bases de datos
6
Arboles N-arios
1. ¿Qué es un arbol?
• Ejemplo: El sistema de archivos de nuestra PC
PC
HD USB2
Usuarios W10 Archivos de Programa Archivos de Cursos Musica Videos
Progamax86
Windows CodeBlocks Java
System System32
7
1. Introducción
Árboles en General o n-arios
Es una estructura utilizada para modelar jerarquías con una relación de 1 a N entre un
grupo de elementos.
Automóvil
Carrocería Chasis Motor
Sistema Sistema Sistema Sistema
Eléctrico Combustión Refrigeración Tracción
Modelo de la relación Pieza-Componente
8
Arboles N-arios
1. Definición A
• Conceptos básicos
• Raiz. Único nodo sin padre.
• Nodo interno. Tiene al menos un hijo
B C D
• Nodo externo. No tienen hijos.
• Sub árbol. Arbol formado por un nodo y
sus descendientes.
• Ancestros y descendientes directos E F G H
• Ancestros y descendientes.
I J K
9
1. Árbol en General o n-ario
Un árbol en General o n-ario. Es una estructura NO LINEAL recursiva en la cual cada
elemento tiene un número cualquiera de árboles asociados.
Elementos V
V
...
a1 a2 ... aN Subarboles a1 a2 aN
Representación de Árboles n-arios
10
1. Árbol en General o n-ario
Definicion. Un árbol en General o n-ario. Se define formalmente como el par (V, A).
Donde V es un conjunto finito de vértices y A un conjunto finito de caminos.
Elementos V
V
...
a1 a2 ... aN Subarboles a1 a2 aN
Representación de Árboles n-arios
11
1. Árboles en General
Conceptos de arboles :
1. Raíz
2. Vértices o Nodos
3. Hojas
4. Camino
5. Longitud de camino
6. Antecesor propio
7. Altura
8. Momento
9. Peso
10. Raíz e hijos
11. Grado
12. Orden y grado
12
3. Conceptos: 1. Raiz
Denominaremos RAIZ al único nodo que no tiene padre y que corresponde al NODO de
nivel CERO .
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
13
3. Conceptos: 2. Vértices (nodos), elementos
Sea n1, n2, ..., nk vértices o nodos de un árbol tal que ni es el padre de ni+1 para todo i de 1
a k.
Nivel
n1 0
n2
1
n3 2
...
ni i-1
ni+1 i
...
nk k
14
3. Conceptos: 3. Hojas
Denominaremos HOJAS a los NODOS que no tienen hijos
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
15
3. Conceptos: 4. Camino
La secuencia vértices o nodos n1, n2, ..., nk se denomina camino desde n1 hasta nk.
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
16
3. Conceptos: 5. Longitud de camino
La LONGITUD de camino es el numero de nodos de la secuencia menos 1. Longitudcamino
= # Nodos - 1
n1
n2
n3
n4
n5
Longitudcamino = #nodos –1 = 5 – 1 = 4
17
3. Conceptos: 5. Longitud de camino
El camino de un nodo hacia SI MISMO tiene longitud CERO
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
18
3. Conceptos: 6. Antecesor y descendiente
Si existe un camino del nodo A hacia el nodo B, se dice que A es antecesor de B y B es
descendiente de A.
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
19
3. Conceptos: 6. Antecesor y descendiente
Un antecesor o descendiente de un nodo que no sea el mismo, recibe el nombre de
ANTECESOR PROPIO y DECENDIENTE PROPIO respectivamente. Raiz no tiene
antecesor..., Las hojas ...
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
20
3. Conceptos: 7. Altura
La ALTURA de un árbol es la longitud de camino mas larga desde la RAIZ hacia la HOJA .
n1
n2
n3
n4
n5
n6
k
21
3. Conceptos: 8. Momento
El MOMENTO de un árbol es el numero de NODOS que contiene el árbol.
n1
n2
n3
El Momento del
árbol es 6
22
3. Conceptos: 9. Peso
El PESO de un árbol es el numero de HOJAS que contiene un árbol.
n1
n2
n3
El árbol tiene
Peso 4
23
3. Conceptos: 10. Raíz e hijos ()
Todos los nodos tienen HIJOS a excepción de las hojas. Todos los nodos tienen padre a
excepción de la RAIZ
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
24
3. Conceptos: 11. Grado de un nodo
El GRADO de un NODO es el numero de HIJOS que tiene un NODO. El Grado de las hojas
es CERO.
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
25
3. Conceptos: 12. Orden o grado
El Orden o grado de un elemento o nodos de un a árbol n-ario es el número de subárboles
que este tiene asociados
Nivel
n1 0
n2 1
n3 2
...
ni i-1
ni+1 i
...
nk k
26
Arboles n-arios. Ejemplos
Implementacion Estatica de arbol n-ario. Explica los valores de las
caracteristicas del arbol mostrado en la
figura:
1
• Grado del arbol
• Momento del arbol
• Peso del arbol
• Numero nodos internos
2 3 4 5 • Altura del arbol
5 6 7 8 9 10 11 12 13
14 15
27
5. Operaciones
Recorridos de arboles
• Recorridos en profundidad
• Preorden
• Inorden
• Postorden
• Recorrido en anchura
• Por niveles
• Inserción.
• Búsqueda
• Eliminación
28
5. Arboles 1-2-3
Arbol n-ario 1-2-3. Es un arbol n-ario ordenado
• Es un arbol n-ario de orden 3
• Cada nodo tiene 1 o 2 elementos y están ordenados
• Cada nodo tiene 1, 2 o 3 subárboles asociados o hijos
• No tiene elementos repetidos
• Cada nodo consta de un elemento de lado izquierdo y otro de lado derecho ordenados
• Si el nodo tiene dos elementos:
• El primer subárbol contiene elementos menores a los elementos de lado izquierdo del nodo padre
• El segundo subarbol contiene elementos mayores al primer elemento y menores al segundo elemento del nodo
padre .
• El tercer subarbol contiene elementos mayores al segundo elemento del nodo padre.
29
5. Arboles 1-2-3
Arbol n-ario 1-2-3. Es un arbol n-ario ordenado
• Es un arbol n-ario de orden 3
• Cada nodo tiene 1 o 2 elementos y están ordenados
• Cada nodo tiene 1, 2 o 3 subárboles asociados o hijos
• No tiene elementos repetidos
• Cada nodo consta de un elemento de lado izquierdo y otro de lado derecho ordenados
• Si el nodo tiene dos elementos:
• El primer subárbol contiene elementos menores a los elementos de lado izquierdo del nodo padre
• El segundo subarbol contiene elementos mayores al primer elemento y menores al segundo elemento del nodo padre .
• El tercer subarbol contiene elementos mayores al segundo elemento del nodo padre.
30
5. Arboles 1-2-3
Arbol n-ario 1-2-3.
Tres subáboles
40 80
20 30 50 70 85 100
52 60 74 78 102 105
Dos subárboles
subarboles Un subárbol
31
5. Operaciones
Operaciones básicas
• Inserción
• Recorridos
• Búsqueda
• Eliminación
32
5. Arboles 2-3
Arbol n-ario 2-3, es un árbol n-ario 1-2-3, además:
• Introducción
- Optimiza el tiempo acceso a la estructura de datos de memoria secundaria
- Baja complejidad en los algoritmos de actualización
- O(log3N)
33
3. Arboles 2-3
Arbol n-ario 2-3, es un árbol n-ario 1-2-3, además:
• Todas las hojas se encuentran el mismo nivel
• El crecimiento se hace a nivel de raíz y no de las hojas
• Todos los nodos internos tienen al menos 2 subárboles asociados no vacíos aunque la
raíz derecha este vacía.
- Si el nodo tiene un elemento, debe tener 2 subárboles
- Si el nodo tiene dos elementos, debe tener 3 subárboles
• Todos los nodos pueden tener hasta dos elementos
34
5. Arboles 2-3
Operaciones
• Inserción
• Búsqueda
• Eliminación
35
5. Arboles Tries
Es un árbol n-ario para la representación de un conjunto grande de palabras (diccionarios).
Aplicaciones
• Corrector ortográfico interactivo
• Diccionario español 3 millones aproximado de palabras
• La búsqueda debe ser menor a un milisegundo
36
5. Arboles B, B+, B*
Es un árbol n-ario ordenado y balanceado
• Es una generalización de un árbol n-ario 2-3
• Se vera en detalle mas adelante
37
Referencias
• Joyanes L. y Zahonero I. (2004) Algoritmos y estructura de datos. Una perspectiva en C.
Madrid España: McGraw-Hill.
• Cortez A. (2013) Algoritmica técnicas algorítmicas. Lima. Peru: CEPREDIN
• Joyanes L. y Zahonero I. (2008) Estructura de datos en Java. Madrid, España: McGraw-
Hill.
• Cairo O y Guardati S. (2006) Estructura de datos. Mexico: McHraw-Hill.
• Villalobos J. (1996) Diseño y Manejo de Estructuras de Datos en C. Santa Fe de Bogota,
Colombia: McGraw-Hill.
• Ficheros en C y C++ .[Ultima actualización 13.06.2017] [Accesado en Lima, 19.05.2020,
1820 horas], http://c.conclase.net/ficheros/
• https://cs.smu.ca/~porter/csc/ref/stl/cont_list.html
• https://decsai.ugr.es/~jfv/ed1/c++/cdrom4/paginaWeb/stl.htm
• https://docs.oracle.com/javase/8/docs/api/?java/util/Collection.html
38
