Ensayo Arboles

Jhair Agila

^[1] 

Arboles (Enero de 2023)

Resumen – El uso de árboles en el mundo de la programación es más común de lo que se suele pensar, es por esto que se han dividido en varios tipos de árboles entre los que están son los arboles binarios, arboles AVL y los árboles-B, mismos que se darán cabida en este ensayo debido a su gran usabilidad y representatividad el entorno de las TIC.

1. introducción

Los arboles son una parte fundamental de código en el mundo actual por lo que nos ayudan a clasificar información de forma ordenada, sin embargo, para una mejor interpretación es preciso identificar a que tipo de árbol pertenecen es por esto que se a llegado a construir una clasificación estándar de los tipos de árboles, mismos que se documentan en este documento (arboles binarios, AVL y B),  

Teniendo en cuenta el dominio, se procederá a estudiar cada uno de ellos con el fin de determinar su eficacia, lugares de uso, proceso de construcción, características esenciales, desventajas y los procesos que involucra cada uno de ellos

Bajo este principio se desarrollará el presente ensayo investigativo el cual nos ayudara a plantear principalmente en que caso podemos usar cada uno de ellos, cuáles son las operaciones adicionales a las que puede conllevar y como y cuando se puede usar cada uno de ellos.

1. DESARROLLO.

Es importante tener un amplio conocimiento de lo que significa los algoritmos de ordenación, pues estos como su nombre mismo los indica tratan de colocar los objetos en posiciones específicas, estas pueden ser ascendentes o descendentes, con el fin de hacerlo más entendible y poder llevar a cabo otras operaciones.

Entre algunos de algoritmos de ordenación que existen están el método Shell, Quicksort y Búsqueda Binaria.

1. Arbol binario

Un árbol binario de búsqueda es un árbol binario con etiquetas de los nodos ordenados de forma que el elemento situado en un nodo es mayor que todos los que se encuentran en su subárbol izquierdo, y menor que todos los que se sitúan en su subárbol derecho.

A continuación, se propondrá un ejemplo de un árbol binario de búsqueda con nodos que almacenan valores enteros. Si se selecciona cualquiera de ellos se podrá comprobar que los

elementos que se sitúan en el subárbol izquierdo son menores y los que se sitúan la parte derecha son mayores.

En este ejemplo es importante rescatar que si se desea añadir un subárbol a los nodos simplemente se lo hace, por ejemplo, en el nodo hoja 14 se le podría añadir otro nodo hijo etiquetado 13.

Es imposible construir un árbol de búsqueda binaria que tenga elementos repetidos, pues no cumple con su principio, sin embargo, cabe destacar que hay como personalizarlos diciendo que los nodos hijos pueden ser menores iguales a la raíz, pero por simplicidad y estructuración no es recomendable ya que es un estándar [1].

Un punto importante a destacar es que si se listan los nodos del ABB en in-order nos da una lista de elementos ordenadas, esta propiedad es similar al método de ordenamiento del Quicksort, donde el nodo raíz haría énfasis en la partición del Quicksort, sin embargo, cabe destacar que en el ABB existe un gasto extra de memoria debido a los punteros [2].

1. Arboles AVL

El termino AVL proviene de las iniciales de Adelson-Velskii y Landis, que son los hombres que idearon este árbol. En términos sencillos es un árbol de búsqueda al que se le añade una condición de equilibrio, esto radica en presentar la máxima diferencia de su altura en 1.

A continuación de muestra un ejemplo de los árboles binarios de búsqueda.

[pic 1]

Como se puede observar en la imagen solo el primero es AVL, por lo que la diferencia entre las alturas es de 1, mientras que la segunda imagen no representa un arbol binario de busqueda AVL, ya que el subarbol izquierdo tiene de altura 3 y el subarbol derecho una altura de 1 [3].

Por otro lado, tenemos que definir el termino de equilibrio de un nodo: Fe(nodo) = altura(derecho) – altura(izquierdo). En un árbol AVL el nodo de equilibrio es de -1, 0 o 1. Es importante destacar que tras su inserción o borrado solo los ascendentes del nodo pueden sufrir cambios y en todo caso solo podrían cambiar una unidad, sin embargo, existe una etapa en donde se recorren ascendentes, si alguno este desequilibrado (+2, -2) se vuelve a equilibrar mediante operaciones denominadas rotaciones [4].

Operación en arboles AVL

El árbol AVL posee algunas operaciones entre ellas están las de acceso, inserción y borrado que se realizan de forma similar a un ABB, salvo que se añade una etapa posterior de reequilibrio (el requilibrio recorre los ascendentes del nodo que ha sufrido una modificación, resaltando sus factores de equilibrio y aplicando las rotaciones en su momento adecuado).

El recorrido se detiene hasta llegar al nodo raíz o cuando subárbol del nodo actual haya sufrido cambios en la altura con respecto a la situación de la operación anterior, esto se puede llegar a realizar de forma recursiva, sin embargo, algo importante a destacar es controlar la altura de los subárboles dH a lo largo del recorrido.

La inserción (dH > 0) si un hijo (y) incrementa su altura, el padre (x) también lo incrementa si su factor de equilibrio era -1 o 0 (hijo izquierdo) o +1 (hijo derecho).

Sin embargo, existen rotaciones del árbol que es la reestructuración del subárbol BB que mantiene la propiedad de su ordenación [4].

Es por esto que existen las operciones de inseccion y borrado, que recorren lo ascendentes, recalculando los factores de requilibrio y teniendo en cuenta la altura del subarbol, donde es posible que el recorrido del arbol sea +2 o -2 (desequilibrado), en ese caso se aplica una determinada rotación que reestable el nodo del arbol, existen dos tipos (simple y doble) en un sentido y en otro. Teneiendo en cuenta el tipo de reestructutacion que se le quiera dar al arbol es preciso tener en cuenta seis casos:

• Rotación 2|1 (Simple derecha).
• Rotación 2|0 (Simple derecha).
• Rotación 2|-1 (Doble derecha).
• Rotación -2|-1 (Simple izquierda).
• Rotación -2|0 (Simple izquierda).
• Rotación -2|1 (Doble izquierda) [4].

1. Arboles B

Los árboles B son arboles de búsqueda que fueron desarrollados por “Rudolf Bayer“y “Eduard M. McVeigh”, que trabajaron en la empresa “Boomerang”, el termino arboles-B no significa binario, razón por la que árbol B no son binarios y ni tampoco son balanceados.

El uso de estos árboles radica ordenar ficheros, donde se han convertido en el sistema de indexación más utilizado.

Entre las características que debe cumplir un árbol-B están:

• Un parámetro muy importante en el árbol-B es el orden que es el número máximo de ramas que puede tener un nodo.
• Si de un nodo de un árbol-b parten n ramas ese nodo contendrá n-1 claves
• El árbol esta ordenado
• Todos los nodos hoja entran al mismo nivel.
• Todos los nodos intermedios excepto la raíz debe tener entre n/2 y n ramas no nulas
• El máximo numero de claves por nodos es de m-1
• El mínimo de numero de claves por nodo es de (m/2)-1
• La profundidad es el número máximo de consultas que se pueden hacer para encontrar la clave

Ejemplo de un árbol de orden 5 y 2 de profundidad.

Las operaciones que se pueden realizar con este tipo de árbol son 3: insertar clave, eliminar clave y buscar clave [5]

...