UNIVERSIDAD NACIONAL TECNOLÓGICA DE LIMA SUR

FACULTAD DE INGENIERÍA Y GESTIÓN

ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS

ALGORITMOS Y ESTRUCTURA DE DATOS

ÁRBOLES EN PYTHON

PROFESOR: MANUEL ALCÁNTARA RAMIREZ

MANSILLA CAMACHO, ELI SANTIAGO

LIMA, 2020

1
 ÍNDICE

INTRODUCCIÓN................................................................................................................... 3
CAPÍTULO I: DEFINICIONES FUNDAMENTALES................................................................4
1. DEFINICIONES Y PROPIEDADES DE LOS ÁRBOLES..................................................6
2. ÁRBOLES BINARIOS............................................................................................................8
3. ÁRBOLES BINARIOS DE BÚSQUEDA.............................................................................11
CAPÍTULO II: ÁRBOLES EN PYTHON................................................................................13
1. IMPLEMENTACIÓN DE UN ÁRBOL BINARIO DE BÚSQUEDA...................................13
2. OPERACIONES EN UN ÁRBOL BINARIO DE BÚSQUEDA.........................................13
2.1 Insertar...........................................................................................................................13
2.2 Recorrido e impresión..................................................................................................15
A. Recorrido inorden (IRD)..........................................................................................15
B. Recorrido preorden (RID).......................................................................................16
C. En postorden (IDR).................................................................................................16
2.3 Buscar............................................................................................................................17
2.4 Suprimir..........................................................................................................................17
3. CÓDIGO PARA ÁRBOLES BINARIOS DE BÚSQUEDA EN PYTHON........................19
CAPÍTULO III: EJERCICIOS................................................................................................21
CAPÍTULO IV: APLICACIONES...........................................................................................25
CONCLUSIONES................................................................................................................. 27
BIBLIOGRAFÍA.................................................................................................................... 28

2
 INTRODUCCIÓN

Los árboles son una de las estructuras más importantes dentro de la programación.
Se pueden aplicar a la solución de distintos tipos de problemas, como el
ordenamiento, la búsqueda, la representación matemática, etc. El presente trabajo
tiene como objetivo presentar una síntesis de la teoría de árboles y sus
aplicaciones. Se utilizará Python como lenguaje base para el desarrollo de nuestra
explicación. Python es un lenguaje de código abierto, considerado como un lenguaje
interpretado de alto nivel.

En el primer capítulo brindaremos un acercamiento a los fundamentos de estas

estructuras, su propiedades y características. En el segundo capítulo plantearemos
algunos ejercicios dentro del lenguaje tratado para ejemplificar la teoría. Finalmente,
en un tercer capítulo, presentaremos algunas aplicaciones de los árboles en
programas concretos.

3
 CAPÍTULO I: DEFINICIONES FUNDAMENTALES

Las estructuras de datos se clasifican en estáticas y dinámicas, según su capacidad

para cambiar de forma y tamaño. También se pueden clasificar en lineales y no
lineales, según la distribución de sus elementos.

Los árboles son estructuras no lineales y dinámicas de vital importancia dentro de la

computación. Son estructuras jerárquicas, aplicadas sobre elementos llamados
nodos.

Podemos definir el árbol de la siguiente manera: un árbol es un conjunto finito de

nodos y ramas, de modo que:

- Existe un nodo denominado nodo raíz.

- Las ramas conectan los nodos, de tal manera que se impone una relación
jerárquica entre ellos.
- Cada nodo del árbol es raíz de algún subárbol contenido en el árbol principal.

Los árboles son estructuras recursivas, ya que cada subárbol es a su vez un árbol.

Se pueden utilizar para representar fórmulas matemáticas, para registrar la historia

de un campeonato de fútbol, construir un árbol genealógico, para enumerar
secciones de un libro, etc.

Pensemos en un libro que tenga la siguiente estructura:

TÍTULO

1. CAPÍTULO 1
a. Sección 1
i. Subsección
b. Sección 2
i. Subsección 1
ii. Subsección 2

4
 iii. Subsección 3
2. CAPÍTULO 2
a. Sección 1
i. Subsección
b. Sección 2
i. Subsección 1
ii. Subsección 2
c. Sección 3
i. Subsección

Podemos representar esta información de la siguiente manera:

Ilustración 1: Representación de grafo

Ilustración 2: Diagrama de Venn

( A ( B ( D ( I ), E ( J, K, L )), C ( F ( O ), G ( M, N ), H ( P ))))

Anidación de paréntesis

5
1. DEFINICIONES Y PROPIEDADES DE LOS ÁRBOLES

a) Cada nodo es la raíz de un árbol.

b) En un árbol de n nodos, el número de ramas es n-1.
c) Si hay una rama que se desprende de n hacia h, se dice que n es el padre de h,
por tanto, h es hijo de n.
d) Cada nodo tiene un único padre, excepto la raíz.
e) Los nodos hermanos son los que tienen el mismo padre.
f) Los nodos que no tienen hijos, es decir, no presentan ramificaciones, son
llamados nodos hoja.
g) Grado del nodo: es el número de descendientes directos de un determinado
nodo.
h) Grado del árbol: es el máximo grado de todos los nodos del árbol.
i) Nivel o profundidad de un nodo: es el número de arcos que deben ser
recorridos para llegar a un determinado nodo. La profundidad de la raíz es 0. La
profundidad de un nodo es igual a la profundidad de su padre + 1.
j) Altura de un nodo longitud del camino más largo, comienza en el nodo y termina
en una hoja. La altura de un nodo hoja es 0. La altura de un nodo es igual a la
mayor altura de sus hijos + 1
k) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
l) Los descendientes de un nodo (c en el diagrama) son aquellos nodos accesibles
por un camino que comience en el nodo.
m)Los ascendientes de un nodo son los nodos del camino que va desde la raíz a él.

6
 Ilustración 3: Altura del árbol. Ilustración 4: Profundidad del árbol.

A. Longitud de camino interno

Es la suma de longitudes de camino de todos los nodos del árbol. Se calcula

mediante la fórmula:

h
LCI =¿ ∑ ni∗i
i=1

Donde:

i: nivel de árbol
h: altura
ni: número de nodos del nivel i

Media de la longitud de camino interno: para esto se divide la LCI entre el

número de nodos del árbol (n).

LCI
LCIM =
n

B. Longitud de camino externo

Árbol extendido: es un árbol en donde el número de hijos de cada nodo es igual al

grado del árbol. Si alguno de los árboles no cumple, se deben incorporar tantos
nodos especiales como se requieran.

Nodo especial: tienen como objetivo reemplazar las ramas vacías o nulas

7
Entonces la longitud de camino externo es la suma de las longitudes de camino de
todos los nodos especiales del árbol. Se calcula por la fórmula.

h +1
LCE=¿ = ∑ nei∗i
i=2

Donde:

i: nivel del árbol

h: altura
nei: número de nodos especiales en el nivel i

Media de la longitud de camino externo (LCEM): dividir la LCE entre el número de

nodos especiales del árbol (n e).

LCE
LCEM=
ne

Donde:

e: número de arcos que se deben recorrer en

promedio para llegar, partiendo de la raíz, a un
nodo especial cualquier del árbol.

2. ÁRBOLES BINARIOS

Es un árbol en donde cada nodo puede tener como máximo dos subárboles, no
izquierdo y otro derecho. Un árbol vacío es un tipo especial de árbol binario. La
altura de un árbol vacío es -1.

Los árboles binarios se usan para representar la solución a un problema de dos

alternativas, para representar árboles genealógicos, la historia de un campeonato de
tenis, etc.

8
 Ilustración 5: Ejemplos de árboles binarios

Ilustración 6: Representación de la historia de un campeonato mediante un árbol binario.

A. Árboles distintos: cuando sus estructuras son diferentes.

a) b)
a y b son árboles distintos

B. Árboles similares: cuando sus estructuras son idénticas, pero la información

de sus nodos es diferente entre sí.

9
 a) b)
a y b son árboles similares

C. Árboles equivalentes: son árboles similares y sus nodos tienen la misma

información.

a) b)
a y b son árboles equivalentes

D. Árboles binarios completos: Todos sus nodos, excepto los del último nivel,
tienen 2 hijos: subárboles izquierdo y derecho.

a)

10
 b)
a y b son árboles completos

Número de nodos de un árbol completo de altura h:

Número de nodos ( ABC )=2h−1

3. ÁRBOLES BINARIOS DE BÚSQUEDA

Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del
subárbol izquierdo de T deben ser menores o iguales al valor del nodo T. De forma
similar, todos los valores de los nodos del subárbol derecho de T deben ser
mayores o iguales al valor del nodo T”.

 Un recorrido inorden por el árbol recorre los elementos en orden de menor a

mayor.
 El elemento mínimo es el primer nodo sin hijo izquierdo en un descenso por
hijos izquierdos desde la raíz.
 El elemento máximo es el primer nodo sin hijo derecho en un descenso por
hijos derechos desde la raíz.
 En un árbol de búsqueda se pueden realizar las operaciones de: búsqueda,
inserción, eliminación e impresión. Las detallaremos en el siguiente capítulo.

11
Ilustración 7: Distribución de los elementos en un árbol binario de búsqueda.

Ilustración 8: Gráfico de un árbol binario de búsqueda.

12
 CAPÍTULO II: ÁRBOLES EN PYTHON

1. IMPLEMENTACIÓN DE UN ÁRBOL BINARIO DE BÚSQUEDA

Para implementar un árbol binario de búsqueda, utilizaremos una clase. En Python,

las clases proporcionan una forma de empaquetar datos y funcionalidad. Al crear
una nueva clase, se crea un nuevo tipo de objeto, permitiendo crear
nuevas instancias de ese tipo. Cada instancia de clase puede tener atributos
adjuntos para mantener su estado. Las instancias de clase también pueden tener
métodos (definidos por su clase) para modificar su estado.

Para este caso, utilizaremos la clase Nodo, como veremos a continuación.

class Nodo:
def __init__(self, dato):
[Link] = None
[Link] = None
[Link] = dato

Una vez creada la clase Nodo, necesitamos definir las funciones básicas para este
tipo de árbol: Insertar, recorrido e impresión, buscar y eliminar.

2. OPERACIONES EN UN ÁRBOL BINARIO DE BÚSQUEDA

2.1 Insertar

Construye los nodos y los inserta en el árbol binario de

Función
búsqueda.

Entrada Información del nodo.

Salida Sin salida.

13
 Condiciones de El árbol contiene un nodo con información, ubicado de
salida acuerdo con su valor clave y la regla definida en la función.

La función insertar introduce la información del nodo y lo ubica en el árbol según su

valor y las condiciones establecidas en la función. Para insertar un elemento se
realizan los siguientes pasos:

1.- Debe compararse la clave a insertar con la raíz del árbol. Si es mayor, debe
avanzarse hacia el subárbol derecho. Si es menor, debe avanzarse hacia el
subárbol izquierdo.

2.- Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes
condiciones:

 El subárbol derecho es igual a vacío, o el subárbol izquierdo es igual a vacío;

en cuyo caso se procederá a insertar el elemento en el lugar que le
corresponde.
 La clave que quiere insertarse es igual a la raíz del árbol; en cuyo caso no se
realiza la inserción.

Mostramos el código en Python para realizar esta operación:

def insertar(raiz, nodo):

if raiz is None:
raiz = nodo
else:
if [Link] < [Link]:
if [Link] is None:
[Link] = nodo
else:
insertar([Link], nodo)
else:
if [Link] is None:
[Link] = nodo
else:
insertar([Link], nodo)

2.2 Recorrido e impresión

14
 Recorre e imprime todos los elementos del árbol binario de
Función
búsqueda en el orden indicado.

Entrada Tipo de recorrido (preorden, inorden, postorden).

Salida Muestra todos los elementos del árbol.

Condiciones de
El árbol no sufre cambios.
salida

Una operación muy importante al trabajar con árboles es su recorrido. Este consiste
en visitar los nodos en forma ordenada; de tal manera que todos los nodos sean
visitados una sola vez. Existen tres tipos de recorrido:

 Recorrido en inorden
 Recorrido en preorden
 Recorrido en postorden

A. Recorrido inorden (IRD)

También se llama método simétrico. Se describe de la siguiente manera:

 Moverse hacia el subárbol izquierdo hasta alcanzar la máxima profundidad.

 Visitar el nodo en curso.
 Volver hacia el nodo anterior en el árbol y visitarlo.
 Moverse hacia el subárbol derecho del nodo anteriormente visitado siempre
que exista y no haya sido visitado previamente, de otra forma, volver hacia el
nodo anterior.
 Repetir los pasos anteriores hasta que todos los nodos hayan sido
procesados.

def inorden(raiz):
if raiz is not None:
inorden([Link])
print([Link],end=" ")
inorden([Link])

15
 B. Recorrido preorden (RID)

En el recorrido en preorden se visita el nodo en curso antes de recorrer el subárbol

izquierdo.

 Visitar la raíz
 Recorrer el árbol izquierdo en preorden
 Recorrer el árbol derecho en preorden

def preorden(raiz):
if raiz is not None:
print([Link],end=" ")
preorden([Link])
preorden([Link])

C. En postorden (IDR)

El recorrido postorden visita el nodo después de recorrer los subárboles izquierdo y

derecho respectivamente. El procedimiento que implementa este tipo de recorrido
es el siguiente:

 Recorrer el árbol izquierdo en postorden

 Recorrer el árbol derecho en postorden
 Visitar la raíz

def postorden(raiz):
if raiz is not None:
postorden([Link])
postorden([Link])
print([Link],end=" ")

16
 2.3 Buscar

Toma un valor clave y lo busca en la información de los

Función
nodos.
Entrada Valor clave.

Salida Devuelve un nodo que contiene el valor clave.

Condiciones de
EL árbol no sufre cambios.
salida

Con esta operación se explora dentro del árbol, según la clave solicitada; devuelve
None si no se encuentra. A continuación, mostramos una implementación de esta
función sigue a continuación:

def buscar_dato(raiz, dato):

if raiz is None:
print("¡El elemento no existe!")
elif [Link] == dato:
print("¡Elemento encontrado!")
elif dato < [Link]:
return buscar_dato([Link], dato)
else:
return buscar_dato([Link], dato)

2.4 Suprimir

Función Suprime el nodo que contiene el valor clave señalado.

Entrada Valor clave.

Salida Ninguna.

Condiciones de
El nodo que contenía el valor clave no está en el árbol.
salida

17
Para eliminar un valor en un árbol binario de búsqueda se pueden presentar los
siguientes casos:

a) Que el elemento sea un nodo hoja.

b) Que el elemento sea un nodo sin hijo izquierdo o derecho. En este caso,
su único sub-árbol sube para toma el lugar del nodo.
c) Que el elemento posea dos sub-árboles. La eliminación puede ser por
sucesor o predecesor. Si es por sucesor, el sucesor no posee hijo
izquierdo, luego éste puede ser movido desde su posición a la del
elemento a eliminar, pero el nodo que se liberará la memoria será el
sucesor.

Algoritmo para eliminar un elemento

a) Verificar que el árbol no esté vacío

b) Introducir el elemento a eliminar
c) Buscar el elemento
d) Llamar a la función eliminar, enviando el parámetro con el valor clave.
e) La función eliminar debe considerar los tres casos de eliminación
f) Al eliminarlo, liberar la memoria del elemento y mostrar el árbol sin el
elemento.

def eliminar(raiz, dato):

if raiz is None:
print("...El elemento no existe...")
elif [Link] == dato:
if([Link] is None and [Link] is None):
[Link] = ""
print("...Elemento eliminado...")
elif([Link] is None and [Link] is not None):
[Link] = [Link]
[Link] = ""
elif([Link] is not None and [Link] is None):
[Link] = [Link]
[Link] = ""
print("...Elemento eliminado...")
elif dato < [Link]:
return eliminar([Link], dato)
else:
return eliminar([Link], dato)

18
Antes de cerrar el capítulo, presentaremos el código para implementar un árbol
binario de búsqueda, en donde encontraremos las operaciones que hemos descrito
anteriormente.

3. CÓDIGO PARA ÁRBOLES BINARIOS DE BÚSQUEDA EN PYTHON

A continuación, mostramos el código en Python para la implementación de un árbol

binario de búsqueda y las operaciones básicas que se pueden realizar en él.

class Nodo: #Creamos la

def __init__(self, dato): clase Nodo
[Link] = None
[Link] = None
[Link] = dato

def insertar(raiz, nodo): #Se crea la

if raiz is None: función insertar
raiz = nodo nodo y se
else: definen las
if [Link] < [Link]: condiciones para
if [Link] is None: llenar el árbol
[Link] = nodo binario
else:
insertar([Link], nodo)
else:
if [Link] is None:
[Link] = nodo
else:
insertar([Link], nodo)

def inorden(raiz): #Se definen cada

if raiz is not None: uno de los
inorden([Link]) recorridos de
print([Link],end=" ") lectura del
inorden([Link]) árbol.

def preorden(raiz):
if raiz is not None:
print([Link],end=" ")
preorden([Link])

19
 preorden([Link])

def postorden(raiz):
if raiz is not None:
postorden([Link])
postorden([Link])
print([Link],end=" ")

def buscar_dato(raiz, dato): #Se define la

if raiz is None: función buscar.
print("¡El elemento no existe!")
elif [Link] == dato:
print("¡Elemento encontrado!")
elif dato < [Link]:
return buscar_dato([Link], dato)
else:
return buscar_dato([Link], dato)

def eliminar(raiz, dato): #Se define la

if raiz is None: función
print("...El elemento no existe...") eliminar, según
elif [Link] == dato: los distintos
if([Link] is None and [Link] is casos.
None):
[Link] = ""
print("...Elemento eliminado...")
elif([Link] is None and [Link]
is not None):
[Link] = [Link]
[Link] = ""
elif([Link] is not None and
[Link] is None):
[Link] = [Link]
[Link] = ""
elif dato < [Link]:
return eliminar([Link], dato)
else:
return eliminar([Link], dato)

20
 CAPÍTULO III: EJERCICIOS

1. Realizar un programa que implemente un árbol de búsqueda binaria.

Ingresar los siguientes elementos: 7, 5, 9, 2, 6, 8, 12, 3, 10.

Para ingresar los elementos al árbol se hace la llamada a la función y se envían los
parámetros para cada caso.

raiz = Nodo(7) #Se ingresan los

insertar(raiz, Nodo(5)) elementos
insertar(raiz, Nodo(9)) manualmente para
insertar(raiz, Nodo(2)) la construcción
insertar(raiz, Nodo(6)) del árbol.
insertar(raiz, Nodo(8))
insertar(raiz, Nodo(12))
insertar(raiz, Nodo(3))
insertar(raiz, Nodo(10))

2. Imprimir los elementos del árbol, a partir de los tres tipos de recorrido.

A partir de los datos ingresados en el ejercicio anterior se puede mostrar los tres
tipos de recorrido estudiados.

print("\n::::::: PRIMERA OPERACIÓN #Se hace la

(RECORRIDO) ::::::\n\n") llamada de las
funciones que
print("A. Recorrido INORDEN: ") mostrarán los
inorden(raiz) tres tipos de
print('\n') recorridos del
print("B. Recorrido PREORDEN: ") árbol.
preorden(raiz)
print('\n')
print("C. Recorrido POSTORDEN: ")
postorden(raiz)
print('\n')

21
 Ilustración 9: Salida del programa.

3. A partir de los recorridos del árbol ingresado, elaborar su representación

gráfica.

Se presenta el árbol construido a partir de los distintos recorridos arrojados por el

programa.

Ilustración 10: Representación gráfica del árbol ingresado.

4. Buscar en el árbol si existen los siguientes elementos: 5, 10, 20, 100.

print("Buscaremos los siguientes elementos: ") #Se hace la

print("\nElemento buscado: 5 --> ",end=" ") llamada para la
buscar_dato(raiz, 5) función buscar y
print("\nElemento buscado: 10 --> ",end=" ") se ingresan los
buscar_dato(raiz, 10) elementos en el
print("\nElemento buscado: 20 --> ",end=" ") mismo programa.
buscar_dato(raiz, 8)
print("\nElemento buscado: 100 --> ",end=" ")
buscar_dato(raiz, 20)

22
 Ilustración 11: Se muestra la salida del programa.

5. Eliminar los siguientes valores: 6, 20, 12.

Se ingresan en el programa los elementos a eliminar. El 6 es un nodo hoja, por lo

que la supresión es directa. El 12 tiene un hijo a la izquierda, en este caso se realiza
el reemplazo.
print("\n\n:::::::::::: TERCERA OPERACIÓN #Se hace la
(SUPRIMIR)::::::::::::\n\n") llamada a la
función eliminar
print("Eliminar el elemento: 6") y se ingresan
eliminar(raiz, 6) los elementos.
print("Datos restantes --> ",end=" ")
inorden(raiz)

print("\n\nEliminar el elemento: 20")

eliminar(raiz, 20)
print("Datos restantes --> ",end=" ")
inorden(raiz)

print("\n\nEliminar el elemento: 12")

eliminar(raiz, 12)
print("Datos restantes --> ",end=" ")
inorden(raiz)

23
Ilustración 12: Se muestra la salida del programa.

24
 CAPÍTULO IV: APLICACIONES

Como hemos visto en los capítulos anteriores, los árboles binarios son estructuras
muy útiles cuando se requiere de modelos para representar procesos en donde se
deben tomar decisiones o se necesita ordenar grandes cantidades de información
de forma eficiente.

A continuación, brindaremos información sintética de los ámbitos en donde se

aprovechan las funciones de los árboles binarios de búsqueda:

 Binary Space Partition (BSP): es un método muy eficiente para calcular las
relaciones de visibilidad entre un grupo estático de polígonos en 3D, vistos
desde un punto de vista arbitrarios. Se utiliza en casi todos los juegos de
vídeo 3D para determinar qué objetos deben ser prestados.
 Binario Trata: se usa en casi todos los routers de alto ancho de banda para
almacenar tablas-routers.
 Hash Árboles: también llamado árbol de Merkle, es una estructura de datos
estratificada que tiene como propósito relacionar cada nodo con una raíz
única asociada a éste. Se usan en los programas p2p.
 Montículos: es un árbol binario completo que utiliza para gestionar
eficientemente las colas, muy utilizadas para la programación en muchos
sistemas operativos. También se usa en la búsqueda de los algoritmos
utilizado en aplicaciones de la AI, como la robótica y los juegos de video.
 La Codificación Huffman Árbol (Chip Unit): es un tipo particular de código de
prefijo óptimo que se usa comúnmente para la compresión de datos sin
pérdida, tales como los utilizados por el .jpeg y .mp3 (archivo-formatos).
 Treap: estructura aleatoria de datos utilizadas en las redes inalámbricas y la
asignación de memoria.
 Árboles GGM: Se usa en aplicaciones criptográficas para generar un árbol de
números pseudoaleatorios.

25
 Árbol de sintaxis - Construido por compiladores y (implícitamente)
calculadoras para analizar expresiones.
 T-tree: son usadas a menudo por bases de datos que guardan la mayoría de
sus datos en la memoria.
 Los árboles binarios se usan con más frecuencia que los árboles n-arios
porque estos son, generalmente, más complejos y no ofrecen una ventaja en
cuanto a velocidad.

26
 CONCLUSIONES

Los árboles son estructuras muy importantes dentro de los lenguajes de

programación, ya que proporcionan métodos bastante efectivos cuando se necesita
ordenar información en grandes cantidades. Sin embargo, este tipo de árbol es
realmente provechoso cuando se trata de árboles autobalanceados o completos, ya
que la distribución de los datos facilitaría las operaciones de búsqueda. Esto
significa ahorrar tiempo y recursos de sistema, pues muchas veces nos
encontraremos frente a árboles degenerados, es decir, un nodo padre solo tiene un
nodo hijo, por lo cual nos encontraríamos más cerca de una lista enlazada.

Como hemos visto en el capítulo de aplicaciones, gran parte de la programación

contemporánea hace uso de los árboles binarios, ya que son realmente útiles para
el uso eficiente de la información.

27
 BIBLIOGRAFÍA

Cairó, O. y Guadarti, S. (2006). Estructuras de datos. (3ª ed.). México: MacGrawHill.

Vaca, R. (2011). Estructuras de datos y algoritmos. Tema 4: árboles. [Dispositivas

de Power Point]. Recuperado el 7 de julio, 2020, de
[Link]

VALIENTE, G. (2002). Algorithms on Trees and Graphs (1.ª ed.). Berlin: Springer.

Marzal, A. y Gracia, I. (2014). Introducción a la programación con Python (1.ª ed.).

España: Universitat Jaume.

28