Universidad de Cuenca

Facultad de Ciencias Químicas

Ingeniería Industrial

ORDENAMIENTO CON ÁRBOL BINARIO

Profesor/a:
Paul Fernando Vanegas Pena

Estudiantes:

Paul Chumbay-Michael Sagñay-Jonatan Farez

Paul.chumbay@ucuenca.Edu.ex-jonnathan.farez@ucuenca.edu.ec-
michael.sagnay@ucuenca.edu.ec

18 de enero de 2024
Resumen: La organización eficiente de ▪ Nodo Izquierdo y Derecho:
información es esencial en diversos contextos, Los nodos conectados a otro
y el ordenamiento de registros en tablas es una nodo.
operación clave para lograrlo. En este sentido, ▪ Hoja: Nodo sin nodos hijos.
se presenta un enfoque especial conocido ▪ Altura del Árbol: Longitud
como el "método del árbol binario" para llevar máxima de la raíz a una hoja.
a cabo esta tarea. En el desarrollo del tema, se La forma en la que un árbol binario funciona
abordan temas como el concepto de árbol se basa en la jerarquía. En este ejemplo
binario, la documentación asociada a dicho tendremos los números [13,14,10,7,4,6,1,3,8]
algoritmo, la complejidad y el rendimiento del se escoge una raíz, en este caso el 8 y se
mismo, así como las ventajas y desventajas comprará el resto de números con este, si son
inherentes. menores se ubicarán a la izquierda y si son
mayores a la derecha, esta forma de
1. MARCO TEORICO ordenamiento continuara con los siguientes
• Visual Basic for Application: Es un nodos.
lenguaje de programación integrado Por ejemplo, en la siguiente figura el nodo 3 es
en Microsoft Excel que permite menor a la raíz 8 por lo que se va a la izquierda,
automatizar tareas y personalizar y el nodo 6 que es menor a 8 pero mayor a 3 se
funciones en las hojas de cálculo. ubica al lado derecho de este.

• Árbol Binario: Es una estructura de

datos jerárquica que consta de nodos
interconectados. Cada nodo tiene
hasta dos nodos hijos: uno a la
izquierda y otro a la derecha. Estos
árboles se utilizan comúnmente para
representar estructuras jerárquicas,
como en la implementación de
estructuras de datos y algoritmos de
búsqueda y ordenamiento.

▪ Raíz: Nodo principal desde el

cual se ramifican los demás
nodos.
 2. ALGORITMO
Sub Arbol_binario() If low < high Then
Dim ws As Worksheet pivot = arr((low + high) \ 2, 1)
Dim rng As Range i = low - 1
Dim arr As Variant j = high + 1
Dim hasChange As Boolean Do
Do
Set ws = ThisWorkbook.Sheets("Hoja1") i=i+1
Do Loop While arr(i, 1) < pivot
Set rng = ws.Range("A1:A" &
ws.Cells(ws.Rows.Count, Do
"A").End(xlUp).Row) j=j-1
arr = rng.Value Loop While arr(j, 1) > pivot
hasChanged = BinaryTreeSort(arr)
rng.Value = arr If i <= j Then
Application.Wait Now + temp = arr(i, 1)
TimeValue("00:00:01") arr(i, 1) = arr(j, 1)
arr(j, 1) = temp
Loop While hasChanged i=i+1
End Sub j=j-1
hasChanged = True
Function BinaryTreeSort(ByRef arr As End If
Variant) As Boolean Loop While i <= j
Dim low As Long, high As Long
low = LBound(arr)
high = UBound(arr) If low < j Then BinaryTreeSortRecursive
BinaryTreeSortRecursive arr, low, high, arr, low, j, hasChanged
BinaryTreeSort If i < high Then
End Function BinaryTreeSortRecursive arr, i, high,
Sub BinaryTreeSortRecursive(ByRef arr As hasChanged
Variant, ByVal low As Long, ByVal high As End If
Long, ByRef hasChanged As Boolean)
Dim i As Long, j As Long
Dim pivot As Variant, temp As Variant End Sub
 3. DOCUMENTACION DEL posición correcta, hay que tomar en cuenta un
ALGORITMO árbol binario puede tener a lo máximo 2 nodos.
Dada la actualidad se puede decir que el uso 3. Eliminación
de arboles binarios son varios por la razón de Esta operación es más compleja que las
que ayudan a la organización de datos e operaciones anteriores, porque se tiene que
implementar algoritmos más rápidos y tomar en cuenta que:
eficientes a la hora de procesar datos, un - Eliminar un nodo sin hijos o nodo hoja
ejemplo de ello se podría decir que es usado en - Eliminar un nodo con un subárbol hijo
sistemas de archivos, interfaces gráficos, - Eliminar un nodo con dos subárboles
sistemas de toma de decisiones, entre otros hijo
más.(Elizabeth & Cháirez, n.d.) Aparte de estos también tenemos otras
Árbol binario de búsqueda operaciones que son utilizadas.
Es conocido también como árbol binario no 4. Comprobar si está vacío.
vacío, de raíz R; son una solución más En pocas palabras verifica si el árbol está
eficiente para realizar búsquedas eficientes en vacío.
colecciones ordenadas de elementos, también 5. Calcular la altura o profundidad.
llamada en ingles Binary Search Tree (BST), Esta determina la altura (profundidad) del
dentro de ella se pueden realizar diferentes árbol.
operaciones que se puede ver en lo siguiente. 6. Determinar el número de nodos hoja.
• Operaciones de un árbol binario Cuenta el numero de hojas de nodos hoja.
En este podemos encontrar las siguientes 7. Recorrido.
operaciones como: Comienza por el nodo raíz para continuar por
1. Búsqueda las ramas o nodos internos hasta los nodos
Este proceso empieza en la raíz donde se terminales.
compara los datos que se tiene con el dato que Árbol AVL
pide el usuario, si no se encuentra el dato en la Son denominados más como arboles
raíz, cambia al subárbol de lado izquierdo si es equilibrados, es decir, que los subárboles
menor y el lado derecho si el número es mayor derechos e izquierdos son de la misma

hasta encontrar el dato deseado.(ÁRBOLES cantidad de nodos en su ranmificación del cual

BINARIOS DE BÚSQUEDA (ABB), n.d.) esto depende de las operaciones de inserción y

eliminación, aparte de esto también hay que
2. Inserción
verificar el equilibrio del árbol, por ende, se
Esta es parecida a la de búsqueda, del cual
usa las rotaciones de nodos que son:
implica agregar un nuevo nodo al árbol en la
- Rotación simple o la derecha
 - Rotación simple a la izquierda 3. El nivel de su hijo derecho es menor o
- Rotación doble a la derecha igual que el de su padre.
- Rotación doble a la izquierda 4. El nivel de su nieto derecho es
- Y también el uso de la Inserción y estrictamente menor que el de su
Eliminación dentro del árbol binario. abuelo.
Árboles Rojo-Negro 5. Cada nodo de nivel mayor que uno
Este es un árbol del cual fue creado en 1972 debe tener dos hijos.
que también es llamando “arboles-B binarios Esto también varia en la eliminación o
simétricos” o como “árbol binario de inserción de datos dentro del árbol binario ya
búsqueda” pero se diferencia por la razón de que son diferentes al de los otros arboles
que cada nodo tiene un atributo de color rojo o binarios.
negro. 4. COMPLEJIDAD Y DESEMPEÑO
Y este árbol binario tiene varios requisitos para DEL ALGORITMO
que deben seguir para ser un árbol binario
rojo-negro y al tratar de realizar cambios con La complejidad al implementar el código
la eliminación o inserción de nodos podría de un árbol binario de búsqueda en Excel
violar las propiedades de un árbol por lo que
resultó considerable debido a nuestras
también las rotaciones cambia en
limitaciones del manejo de herramientas
consideración de los colores.
en esta plataforma. Sin embargo, a pesar
Árbol AA
de estos desafíos, se logró crear un
Este tipo de árbol es un árbol binario de
búsqueda auto-balanceable del cual es usado ejemplo simplificado del árbol ramificado.

para la recuperación de datos y Para conseguirlo, hicimos uso de

almacenamiento, fue creado por Arne información adicional encontrada en
Anderson. diversas páginas, celdas adicionales y
Los árboles AA se implementan con la idea de fórmulas de Excel para poder simularlo,
que se valor mas por el nivel que el color, por demostrando la capacidad de adaptación
lo que cada nodo debe tener ciertas de Excel para abordar ciertos escenarios de
condiciones que son:
estructuras de datos.
1. El nivel de un nodo hoja es uno.
2. El nivel de un hijo izquierdo es
Respecto al rendimiento, el árbol binario
estrictamente menor que el de su
implementado en Excel es satisfactorio
padre.
para conjuntos de datos pequeños o
medianos. Sin embargo, se vuelve • Se puede volver ineficiente a
ineficiente a medida que la lista crece. La medida que el tamaño de datos
razón de esta limitación es que Excel no aumenta.
está específicamente diseñado para • Falta de flexibilidad.
ejecutar eficientemente estructuras de tipo • Limitaciones de tamaño
árbol. La plataforma no está optimizada • Para conjuntos de datos
para manejar de manera efectiva grandes se podría utilizar otro
estructuras de datos y algoritmos más tipo de ordenamiento
complejos, ya que su enfoque principal es
la hoja de cálculo. Estas restricciones
pueden afectar el rendimiento en 6. TENDENCIAS
escenarios donde se requiere una gestión
eficiente de árboles de búsqueda más 7. REFERENCIAS
grandes. • Moltó Martínez, G. (2010). El Árbol
Binario de Búsqueda.
5. VENTAJAS Y DESVENTAJAS http://hdl.handle.net/10251/7985
DEL ALGORITMO • Elizabeth, I. S. C., & Cháirez, A. (n.d.).
Ventajas: Principios de Diseño aplicados a Árboles
Binarios de Búsqueda REPORTE
• Su facilidad al usar datos pequeños TÉCNICO.
o simples, para aquellos que tienen • ÁRBOLES BINARIOS DE BÚSQUEDA
(ABB). (n.d.).
experiencia en Excel. Elizabeth, I. S. C., & Cháirez, A. (n.d.).
• No se necesita conocimientos de Principios de Diseño aplicados a Árboles
Binarios de Búsqueda REPORTE
programación para implementar TÉCNICO.
este enfoque en Excel ya que se
puede usar fórmulas básicas para
simular una estructura
de árbol binario.

Desventajas: