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
[Link]@[Link]@[Link]-
[Link]@[Link]
18 de enero de 2024
Resumen: La organización eficiente de Nodo Izquierdo y Derecho:
información es esencial en diversos Los nodos conectados a otro
contextos, y el ordenamiento de registros en nodo.
tablas es una operación clave para lograrlo. Hoja: Nodo sin nodos hijos.
En este sentido, se presenta un enfoque Altura del Árbol: Longitud
especial conocido como el "método del árbol máxima de la raíz a una hoja.
binario" para llevar a cabo esta tarea. En el La forma en la que un árbol binario funciona
desarrollo del tema, se abordan temas como se basa en la jerarquía. En este ejemplo
el concepto de árbol binario, la tendremos los números [13,14,10,7,4,6,1,3,8]
documentación asociada a dicho algoritmo, la se escoge una raíz, en este caso el 8 y se
complejidad y el rendimiento del mismo, así comprará el resto de números con este, si son
como las ventajas y desventajas 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
en Microsoft Excel que permite es menor a la raíz 8 por lo que se va a la
automatizar tareas y personalizar izquierda, y el nodo 6 que es menor a 8 pero
funciones en las hojas de cálculo. mayor a 3 se 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.
Dim pivot As Variant, temp As Variant
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 = [Link]("Hoja1") i=i+1
Do Loop While arr(i, 1) < pivot
Set rng = [Link]("A1:A" &
[Link]([Link], Do
"A").End(xlUp).Row) j=j-1
arr = [Link] Loop While arr(j, 1) > pivot
hasChanged = BinaryTreeSort(arr)
[Link] = arr If i <= j Then
[Link] Now + temp = arr(i, 1)
TimeValue("[Link]") 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
End Sub Esta es parecida a la de búsqueda, del cual
3. DOCUMENTACION DEL implica agregar un nuevo nodo al árbol en la
ALGORITMO posición correcta, hay que tomar en cuenta un
Dada la actualidad se puede decir que el uso árbol binario puede tener a lo máximo 2
de arboles binarios son varios por la razón de nodos.
que ayudan a la organización de datos e 3. Eliminación
implementar algoritmos más rápidos y Esta operación es más compleja que las
eficientes a la hora de procesar datos, un operaciones anteriores, porque se tiene que
ejemplo de ello se podría decir que es usado tomar en cuenta que:
en sistemas de archivos, interfaces gráficos, - Eliminar un nodo sin hijos o nodo
sistemas de toma de decisiones, entre otros hoja
más. (Elizabeth & Cháirez, n.d.) - Eliminar un nodo con un subárbol hijo
Árbol binario de búsqueda - Eliminar un nodo con dos subárboles
Es conocido también como árbol binario hijo
no vacío, de raíz R; son una solución más Aparte de estos también tenemos otras
eficiente para realizar búsquedas eficientes en operaciones que son utilizadas.
colecciones ordenadas de elementos, también 4. Comprobar si está vacío.
llamada en ingles Binary Search Tree (BST), En pocas palabras verifica si el árbol está
dentro de ella se pueden realizar diferentes vacío.
operaciones que se puede ver en lo siguiente. 5. Calcular la altura o profundidad.
Operaciones de un árbol binario Esta determina la altura (profundidad) del
En este podemos encontrar las siguientes árbol.
operaciones como: 6. Determinar el número de nodos hoja.
1. Búsqueda Cuenta el numero de hojas de nodos hoja.
Este proceso empieza en la raíz donde se 7. Recorrido.
compara los datos que se tiene con el dato Comienza por el nodo raíz para continuar por
que pide el usuario, si no se encuentra el dato las ramas o nodos internos hasta los nodos
en la raíz, cambia al subárbol de lado terminales.
izquierdo si es menor y el lado derecho si el Árbol AVL
número es mayor hasta encontrar el dato Son denominados más como arboles
deseado. equilibrados, es decir, que los subárboles
(ÁRBOLES BINARIOS DE BÚSQUEDA (ABB), n.d.)
derechos e izquierdos son de la misma
cantidad de nodos en su ranmificación del
2. Inserción
cual esto depende de las operaciones de
inserción y eliminación, aparte de esto 1. El nivel de un nodo hoja es uno.
también hay que verificar el equilibrio del 2. El nivel de un hijo izquierdo es
árbol, por ende, se usa las rotaciones de estrictamente menor que el de su
nodos que son: padre.
- Rotación simple o la derecha 3. El nivel de su hijo derecho es menor
- Rotación simple a la izquierda o igual que el de su padre.
- Rotación doble a la derecha 4. El nivel de su nieto derecho es
- Rotación doble a la izquierda estrictamente menor que el de su
- Y también el uso de la Inserción y abuelo.
Eliminación dentro del árbol binario. 5. Cada nodo de nivel mayor que uno
Árboles Rojo-Negro debe tener dos hijos.
Este es un árbol del cual fue creado en 1972 Esto también varia en la eliminación o
que también es llamando “arboles-B binarios inserción de datos dentro del árbol binario ya
simétricos” o como “árbol binario de que son diferentes al de los otros arboles
búsqueda” pero se diferencia por la razón de binarios.
que cada nodo tiene un atributo de color rojo 4. COMPLEJIDAD Y DESEMPEÑO
o negro. DEL ALGORITMO
Y este árbol binario tiene varios requisitos
para que deben seguir para ser un árbol La complejidad al implementar el código
binario rojo-negro y al tratar de realizar
de un árbol binario de búsqueda en Excel
cambios con la eliminación o inserción de
resultó considerable debido a nuestras
nodos podría violar las propiedades de un
limitaciones del manejo de herramientas
árbol por lo que también las rotaciones
en esta plataforma. Sin embargo, a pesar
cambia en consideración de los colores.
de estos desafíos, se logró crear un
Árbol AA
Este tipo de árbol es un árbol binario de ejemplo simplificado del árbol
búsqueda auto-balanceable del cual es usado ramificado. Para conseguirlo, hicimos uso
para la recuperación de datos y de información adicional encontrada en
almacenamiento, fue creado por Arne diversas páginas, celdas adicionales y
Anderson. fórmulas de Excel para poder simularlo,
Los árboles AA se implementan con la idea demostrando la capacidad de adaptación
de que se valor mas por el nivel que el color,
de Excel para abordar ciertos escenarios
por lo que cada nodo debe tener ciertas
de estructuras de datos.
condiciones que son:
Respecto al rendimiento, el árbol binario Desventajas:
implementado en Excel es satisfactorio Se puede volver ineficiente a
para conjuntos de datos pequeños o medida que el tamaño de datos
medianos. Sin embargo, se vuelve aumenta.
ineficiente a medida que la lista crece. La Falta de flexibilidad.
razón de esta limitación es que Excel no Limitaciones de tamaño
está específicamente diseñado para Para conjuntos de datos
ejecutar eficientemente estructuras de tipo grandes se podría utilizar otro
árbol. La plataforma no está optimizada tipo de ordenamiento
para manejar de manera efectiva
estructuras de datos y algoritmos más
complejos, ya que su enfoque principal es 6. TENDENCIAS
la hoja de cálculo. Estas restricciones
pueden afectar el rendimiento en 7. REFERENCIAS
escenarios donde se requiere una gestión Moltó Martínez, G. (2010). El Árbol
eficiente de árboles de búsqueda más Binario de Búsqueda.
grandes. [Link]
Elizabeth, I. S. C., & Cháirez, A. (n.d.).
5. VENTAJAS Y DESVENTAJAS Principios de Diseño aplicados a Árboles
Binarios de Búsqueda REPORTE
DEL ALGORITMO TÉCNICO.
Ventajas: ÁRBOLES BINARIOS DE BÚSQUEDA
(ABB). (n.d.).
Su facilidad al usar datos
Elizabeth, I. S. C., & Cháirez, A. (n.d.).
pequeños o simples, para aquellos Principios de Diseño aplicados a Árboles
Binarios de Búsqueda REPORTE
que tienen experiencia en Excel. TÉCNICO.
No se necesita conocimientos de
programación para implementar
este enfoque en Excel ya que se
puede usar fórmulas básicas para
simular una estructura
de árbol binario.
