.: Árboles Binarios vs Listas :.

:: Árboles Binarios o Listas Enlazadas ::

---

---

Materia. Lab de Leng de Progr
Hora. V1 (Jueves)

En la siguiente entra, e inspirándome en mi programa realizado en base a listas para el reporte de Lenguajes Imperativos, decidí hacer la comparación en cuestión de listas y los árboles binarios.

Primeramente, pasaré a hacer el recordatorio de lo que es un árbol binario.

Definición de Árbol Binario.

Estructura de datos de memoria dinámica de una cantidad finita de elementos que consta de un “Nodo Raíz” y del cual sólo pueden partir máximo  dos nodos más. “Nodo Izquierdo” y “Nodo Derecho”.

Prácticamente, cada nodo consta de los siguientes elementos principales:

• Info. Es el espacio que contiene la información en nuestra estructura del Nodo.
• Dos áreas de enlace. Nosotros tenemos en cada nodo dos áreas destinadas a lo que son los apuntadores que nos servirán en el momento que requiramos accesar a un nodo que le siga.

Por ejemplo, en la siguiente imagen podemos decir que 14 pertenece a info, mientras las flechas asimilan lo que serían nuestros punteros para el acceso a los nodos izquierdo y derecho.

Ejemplo de árbol binario

La forma, como pueden ver, de acomodar elementos es la siguiente (por lo común):

Si tenemos dos elementos que saldrán del “Nodo Raiz”, el elemento menor (dependiendo del valor del “Nodo Raíz”) se colocara en el “Nodo Izquierdo”, mientras el elemento mayor, se colocará en el “Nodo Derecho”.

Al igual que en listas, en esta estructura requerimos del uso de punteros para el acceso a los diferentes nodos de nuestro árbol.

Listas.

Pasando a una pequeña definición de listas, tenemos que también son estructuras dinámicas de datos, la diferencia con los árboles binarios es que cada nodo al crearse, se va haciendo de manera continua.

Como pudieron apreciar, en los árboles binarios, se percibe una jerarquía y una organización de elementos. En las listas no es así.

Podemos tener una lista linealmente enlazada, en la cual solo se puede accesar al nodo que sigue. Es decir, sólo se puede ir hacia adelante.

Lista Enlazada Simple

Al igual que en los árboles binarios, en listas contamos con lo que es nuestra parte info donde tendremos nuestros datos, y con la parte de enlace que funciona con los apuntadores y así poder tener acceso a lo que son los nodos de nuestra lista, pero como se comentó antes, una vez pasado al siguiente nodo, no hay vuelta de regreso.

Es por esta situación, que cuando a veces se requiere volver al nodo anterior, también podemos contar con las listas doblemente enlazadas.

En las en las listas enlazadas simples únicamente contamos con una sección de enlace hacia adelante. En las listas doblemente enlazadas contamos con el área que nos mueve hacia adelante y otra que nos permite el acceso hacía atrás.

De hecho, mi programa de listas maneja listas doblemente enlazadas para poder hacer uso de las funciones presentes en el menú de dicho programa.

Lista Doblemente Enlazada

Ahora bien, podemos contar con las listas circulares. Como se han podido percatar, llega un momento en el que el último elemento sólo llega a un valor NULL.

Con las listas circulares, al momento de llegar a lo que debería de ser este valor NULL, en realidad tenemos que el área que le corresponde el acceso al siguiente nodo, nos manda a lo que es el inicio de la lista.

Lista Enlazada Circular

No podemos limitarnos a esto, podemos hacer combinaciones de los tipos de listas con los que contamos dependiendo de nuestra necesidad.

Desventaja de las listas en contra de los árboles binarios.

El programa que muestro sobre listas comenzó simplemente como una base de datos que se registra y muestra información.

Este proyecto realizado el semestre pasado en compañía de otro compañero se extendió. De repente decidimos incrustar funciones para buscar, eliminar y modificar los registros que tuviéramos en nuestra lista.

En conclusión todo se basaba más que nada en la función que es de búsqueda.

Sin embargo, al finalizar el proyecto, nos dimos cuenta de la ineficiencia de nuestro código, pues al momento de buscar, no tenemos otra opción más que ir comparando el dato de la lista nodo por nodo hasta encontrar el dato buscado, y si es que se encuentra en la lista. Piensen como sería teniendo cientos de registros.

Es aquí donde entraba el papel de los árboles binarios.

Como se apreció antes, los nodos en un árbol están más jerarquizados, pues para hacer la búsqueda de nodos, nos hubiera sido más útil, ya que tenemos la opción de, antes de ir a algún nodo, preguntar si el elemento del nodo al que vamos a accesar es mayor o menos al valor del dato que buscamos. Esto nos ayudará a definir si entramos o no a esa rama.

De esta manera, aún teniendo miles de registros, el proceso de búsqueda es mucho más eficiente que en una lista.

Nosotros incrustamos una serie de instrucciones para que al momento de agregar registros, se ordenen ascendentemente dependiendo de la variable ID. Sin embargo, aun y con todo esto, no llegamos a la eficiencia de una búsqueda dentro de un árbol binario.

Conclusión.

Antes de realizar algún código con estructuras dinámicas, hay que pensar que es lo que vamos a hacer para así poder definir claramente que nos puede ser de utilidad.

Cualquier comentario es bienvenido.

Saludos a todos.