¿Para que sirve un árbol binario?
Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada. Recorridos con los conocidos métodos recursivos:
Inorden
Postorden
Preorden
¿Cómo se ingresa la información?
Como dije anteriormente, la información se ingresa de forma ordenada esto se resuelve de forma muy sencilla con estos pasos:
Se toma el dato a ingresar X
Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?
En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
En caso negativo preguntamos: X < Nodo
En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar
En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.
Nos daremos cuenta de que es un proceso RECURSIVO en el cual al final por más grande que sea el árbol el dato a entrar ocupará un lugar, vamos a ejemplificar lo ya mencionado con una imagen:
Si observan con detenimiento la imagen aunque se vea algo “complejo” entenderán bien el funcionamiento.
Vamos a programarlo
Todo lo dicho anteriormente, vamos a programarlo ahora usando POO con java (para que sea más fácil de entender). Comenzamos con la abstracción de la información, tenemos que un árbol binario está compuesto por la raíz y sus nodos hijos, de la misma forma que la misma raíz no es más que otro nodo, partiendo de esto entonces crearemos 2 clases: (Quiero comentar antes de esto que, aunque no soy muy partidario de escribir los nombres de los métodos y clases en español, por cuestiones de entendimiento para muchas personas que lleguen a esta información, los pondré de esa forma).
Arbol
Nodo
Para comenzar con esas clases tenemos, vamos ahora a definirlas: Nodo.java
public class Nodo {
/* Declaraciones de variables */
private int valor;
private Nodo padre;
private Nodo hojaIzquierda;
private Nodo hojaDerecha;
/* Constructor */
public Nodo(int valor) {
this.valor = valor;
}
/* Setters y Getters */
public void setValor(int valor) {
this.valor = valor;
}
public int getValor() {
return valor;
}
public Nodo getPadre() {
return padre;
}
public void setPadre(Nodo padre) {
this.padre = padre;
}
public Nodo getHojaIzquierda() {
return hojaIzquierda;
}
public void setHojaIzquierda(Nodo hojaIzquierda) {
this.hojaIzquierda = hojaIzquierda;
}
public Nodo getHojaDerecha() {
return hojaDerecha;
}
public void setHojaDerecha(Nodo hojaDerecha) {
this.hojaDerecha = hojaDerecha;
}
}
public class Nodo {
/* Declaraciones de variables */
private int valor;
private Nodo padre;
private Nodo hojaIzquierda;
private Nodo hojaDerecha;
/* Constructor */
public Nodo(int valor) {
this.valor = valor;
}
/* Setters y Getters */
public void setValor(int valor) {
this.valor = valor;
}
public int getValor() {
return valor;
}
public Nodo getPadre() {
return padre;
}
public void setPadre(Nodo padre) {
this.padre = padre;
}
public Nodo getHojaIzquierda() {
return hojaIzquierda;
}
public void setHojaIzquierda(Nodo hojaIzquierda) {
this.hojaIzquierda = hojaIzquierda;
}
public Nodo getHojaDerecha() {
return hojaDerecha;
}
public void setHojaDerecha(Nodo hojaDerecha) {
this.hojaDerecha = hojaDerecha;
}
}
Vamos a revisar un poco más de cerca el código. Es una clase muy sencilla, como podemos ver únicamente tiene 4 atributos (variables) fáciles de entender:
valor
hojaIzquierda
hojaDerecha
valor es el dato almacenado del propio nodo, mientras que como recordaremos cada nodo puede tener máximo 2 hijos uno a la izquierda y otro a la derecha, donde todos los nodos a su izquierda son menores a el mismo y todos los nodos a su derecha son mayores a el mismo, pero que comienzan como nulos ya que al crear un nuevo nodo, este no tiene hijos. Hay que tener cuidado con setValor( int valor ) ¿Porque? pues bien, no podemos actualizar el valor al aire ya que perderíamos el orden, por lo que tenemos un contructor:
/* Constructor */
public Nodo(int valor) {
this.valor = valor;
}
/* Constructor */
public Nodo(int valor) {
this.valor = valor;
}
a partir del cual se ingresa el valor del nodo al crear una instancia del mismo:
Nodo nodo = new Nodo( 1 );
1
Nodo nodo = new Nodo( 1 );
Ya tenemos nuestra clase nodo lista, ahora pasemos con la clase Arbol.java que es aún más sencilla ( en definición ) que Nodo: Arbol.java
public class Arbol {
/* Atributos */
private Nodo raiz;
/* Contructories */
public Arbol( int valor ) {
this.raiz = new Nodo( valor );
}
public Arbol( Nodo raiz ) {
this.raiz = raiz;
}
/* Setters y Getters */
public Nodo getRaiz() {
return raiz;
}
public void setRaiz(Nodo raiz) {
this.raiz = raiz;
}
}
public class Arbol {
/* Atributos */
private Nodo raiz;
/* Contructories */
public Arbol( int valor ) {
this.raiz = new Nodo( valor );
}
public Arbol( Nodo raiz ) {
this.raiz = raiz;
}
/* Setters y Getters */
public Nodo getRaiz() {
return raiz;
}
public void setRaiz(Nodo raiz) {
this.raiz = raiz;
}
}
Prácticamente por ahora lo importante es su atributo “raiz” del tipo Nodo, el cual representará a todo nuestro árbol, adicionalmente he creado constructores que pueden ser de ayuda al momento de inicializar el árbol para crear la raíz de paso. pffff que nos hemos alargado con el post, pero aún no terminamos, acabamos apenas de definir entidades faltan todas las funciones del mismo. vamos con ellas. Hay que agregar métodos a nuestra clase de Arbol para poder ingresar nuevos nodos:
addNodo
removeNodo
recorridoPreorden
recorridoInorden
recorridoPostorden
Programando las funciones del árbol
En esta primera parte quiero abarcar al menos hasta el ingreso de nuevos nodos, comencemos entonces. La modificación la haremos en nuestra clase Arbol que es la que llevará estas funciones de control, recordemos nuestro algoritmo de inserción que planteamos anteriormente:
Se toma el dato a ingresar X
Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?
En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
En caso negativo preguntamos: X < Nodo
En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar
En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.
Entonces definamos nuestra función:
private void private void addNodo( Nodo nodo, Nodo raiz ) {
/* 2.- Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ? */
if ( raiz == null ) {
/*
* 3.- En caso afirmativo X pasa a ocupar el lugar del nodo y ya
* hemos ingresado nuestro primer dato.
* ==== EDITO =====
* Muchas gracias a @Espectro por la corrección de esta línea
*/
this.setRaiz(nodo);
}
else {
/* 4.- En caso negativo preguntamos: X < Nodo */
if ( nodo.getValor() <= raiz.getValor() ) {
/*
* 5.- En caso de ser menor pasamos al Nodo de la IZQUIERDA del
* que acabamos de preguntar y repetimos desde el paso 2
* partiendo del Nodo al que acabamos de visitar
*/
if (raiz.getHojaIzquierda() == null) {
raiz.setHojaIzquierda(nodo);
}
else {
addNodo( nodo , raiz.getHojaIzquierda() );
}
}
else {
/*
* 6.- En caso de ser mayor pasamos al Nodo de la DERECHA y tal
* cual hicimos con el caso anterior repetimos desde el paso 2
* partiendo de este nuevo Nodo.
*/
if (raiz.getHojaDerecha() == null) {
raiz.setHojaDerecha(nodo);
}
else {
addNodo( nodo, raiz.getHojaDerecha() );
}
}
}
}
public void addNodo( Nodo nodo ) {
this.addNodo( nodo , this.raiz );
}
private void private void addNodo( Nodo nodo, Nodo raiz ) {
/* 2.- Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ? */
if ( raiz == null ) {
/*
* 3.- En caso afirmativo X pasa a ocupar el lugar del nodo y ya
* hemos ingresado nuestro primer dato.
* ==== EDITO =====
* Muchas gracias a @Espectro por la corrección de esta línea
*/
this.setRaiz(nodo);
}
else {
/* 4.- En caso negativo preguntamos: X < Nodo */
if ( nodo.getValor() <= raiz.getValor() ) {
/*
* 5.- En caso de ser menor pasamos al Nodo de la IZQUIERDA del
* que acabamos de preguntar y repetimos desde el paso 2
* partiendo del Nodo al que acabamos de visitar
*/
if (raiz.getHojaIzquierda() == null) {
raiz.setHojaIzquierda(nodo);
}
else {
addNodo( nodo , raiz.getHojaIzquierda() );
}
}
else {
/*
* 6.- En caso de ser mayor pasamos al Nodo de la DERECHA y tal
* cual hicimos con el caso anterior repetimos desde el paso 2
* partiendo de este nuevo Nodo.
*/
if (raiz.getHojaDerecha() == null) {
raiz.setHojaDerecha(nodo);
}
else {
addNodo( nodo, raiz.getHojaDerecha() );
}
}
}
}
public void addNodo( Nodo nodo ) {
this.addNodo( nodo , this.raiz );
}
Podemos ver que he agregado 2 funciones para insertar un nuevo nodo, pero solo 1 de ellas es vista desde fuera, la que nosotros llamaremos, esto es porque la función que usamos realmente para insertar (llamada dentro del método que vemos desde fuera de la clase [el método público, para quien ande perdido]) necesita una referencia de la “raíz” a partir de que nodo va a hacer las comprobaciones, para que al usar la recursividad esta raíz pueda ir cambiando (de acuerdo al algoritmo) y seguir probando y comparando nodos. Hasta ahora hemos comprendido el funcionamiento de los árboles binarios, hemos definido las clases a usar y ya comenzamos con las funciones básicas del mismo, en la próxima entrada veremos como hacer la eliminación de un nodo para así continuar hasta terminar este tema (que tanto dolor de cabeza le da a algunas personas) tan interesante.
lunes, 18 de diciembre de 2017
recursividad
Las funciones recursivas son aquellas que se invocan a si mismas en algún momento de su ejecución. En análisis de Algoritmos las técnicas recursivas se usan mucho para la solución de Problemas. Esta forma en analisis de Algoritmos es llamada Divide y Venceras. Para poder resolver un problema de forma recursiva es necesario saber alguna solucion no recursiva para alguno de los casos mas sencillos. "Usamos la solucion más simple para resolver un problema más complejo." Así, todo método recursivo debe tener al menos una sentencia que devuelva un resultado (la solución del caso más sencillo) y las sentencias necesarias para acercarse en cada invocación a ese caso. La recursión permite programar algoritmos aparentemente complicados con un código simple y claro, ahorrando trabajo al programador. A simple vista parece la solución perfecta para muchos problemas, pero hay que tener en cuenta que en ocasiones ralentizará el programa en exceso. Por ejemplo, la función factorial en forma recursiva:
-------------------1-----------------------
public class Factoriales
{
static int factorial(int numero){
if ( numero <= 1 ) { return 1; } else { return numero*factorial(numero-1); } } public static void main(String args[]){ System.out.println(factorial(5)); } } La misma función en forma iterativa: public class Factoriales{ static int factorial(int numero){ int resultado = 1; while(numero > 0){
resultado = resultado*numero;
número--; } }
public static void main(String args[]){
System.out.println(factorial(5));
}
}
Como puede observarse, la función iterativa sólo recorre un bucle while, mientras que la recursiva invoca un método nuevo hasta que número vale 1 (Esto requiere un trabajo considerablemente mayor por parte del ordenador). La recursión es por lo tanto una potente herramienta en programación, pero hay que saber diferenciar cuando es útil y cuando no. Recursión mutua Este en un ejemplo de recursión mutua. Se trata de un programa que devolverá true o false si el parámetro número es respectivamente, impar o par (en el caso de que invoquemos la función impar(número)).
public class Paridad{
public static boolean impar (int numero){
if (numero==0) return false; }
else return par(numero-1);
} public static boolean par (int numero){
if (numero==0) return true;
else return impar(numero-1);
}
}
-------------------1-----------------------
public class Factoriales
{
static int factorial(int numero){
if ( numero <= 1 ) { return 1; } else { return numero*factorial(numero-1); } } public static void main(String args[]){ System.out.println(factorial(5)); } } La misma función en forma iterativa: public class Factoriales{ static int factorial(int numero){ int resultado = 1; while(numero > 0){
resultado = resultado*numero;
número--; } }
public static void main(String args[]){
System.out.println(factorial(5));
}
}
Como puede observarse, la función iterativa sólo recorre un bucle while, mientras que la recursiva invoca un método nuevo hasta que número vale 1 (Esto requiere un trabajo considerablemente mayor por parte del ordenador). La recursión es por lo tanto una potente herramienta en programación, pero hay que saber diferenciar cuando es útil y cuando no. Recursión mutua Este en un ejemplo de recursión mutua. Se trata de un programa que devolverá true o false si el parámetro número es respectivamente, impar o par (en el caso de que invoquemos la función impar(número)).
public class Paridad{
public static boolean impar (int numero){
if (numero==0) return false; }
else return par(numero-1);
} public static boolean par (int numero){
if (numero==0) return true;
else return impar(numero-1);
}
}
lista dobles
El primer y el último nodo de una lista doblemente enlazada son accesibles inmediatamente (o sea, accesibles sin necesidad de recorrer la lista, y usualmente llamados cabeza y cola) y esto permite recorrerla desde el inicio o el final de la lista, respectivamente. Cualquier nodo de la lista doblemente enlazada, una vez obtenido, puede ser usado para empezar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o el final), desde el nodo dado.
Los enlaces de un nodo de una lista doblemente enlazada son frecuentemente llamados anterior y siguiente o antecesor y sucesor. Las referencias guardadas en los enlaces son usualmente implementadas como punteros,pero también podrían ser índices de un array donde están los nodos.
Algoritmos Básicos[editar]
lista doblemente enlazada[editar]
record NodoDoblementeEnlazado {
siguiente // Una referencia al nodo siguiente
anterior // Una referencia al nodo anterior
dato // dato o referencia al dato
}
record ListaDoblementeEnlazada {
NodoDoblementeEnlazado primerNodo // referencia al primer nodo de la lista
NodoDoblementeEnlazado ultimoNodo // referencia al último nodo de la lista
}
Recorriendo la lista[editar]
Recorrer una lista doblemente enlazada puede ser en cualquier dirección. De hecho, la dirección del recorrido puede cambiar muchas veces, si se desea. Recorrido es frecuentemente llamado iteración.
Hacia adelante
nodo := lista.primerNodo
while nodo ≠ null
nodo := nodo.siguiente
Hacia atrás
nodo := lista.ultimoNodo
while nodo ≠ null
nodo := nodo.anterior
Insertando un nodo[editar]
Estas funciones insertan un nodo ya sea adelante o atrás de un nodo dado:
function InsertaAdelante(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo
nuevoNodo.siguiente := nodo.siguiente
if nodo.siguiente == null
lista.ultimoNodo := nuevoNodo
else
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
function InsertaAtras(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo.anterior
nuevoNodo.siguiente := nodo
if nodo.anterior == null
lista.primerNodo := nuevoNodo
else
nodo.anterior.siguiente := nuevoNodo
nodo.anterior := nuevoNodo
También necesitamos una función para insertar un nodo al principio de una lista posiblemente vacía:
function InsertaAlPrincipio(Lista lista, Nodo nuevoNodo)
if lista.primerNodo == null
lista.primerNodo := nuevoNodo
lista.ultimoNodo := nuevoNodo
nuevoNodo.anterior := null
nuevoNodo.siguiente := null
else
InsertaAtras(lista, lista.primerNodo , nuevoNodo)
La siguiente función inserta al final:
function InsertaAlFinal(Lista lista, Nodo nuevoNodo)
if lista.ultimoNodo == null
InsertaAlPrincipio(lista, nuevoNodo)
else
InsertatAdelante(lista, lista.ultimoNodo, nuevoNodo)
Borrando un Nodo[editar]
Eliminar un nodo es más fácil que insertar, pero requiere un manejo especial si el nodo a eliminar es el primerNodo o el ultimoNodo:
function Elimina(Lista lista, Nodo nodo)
if nodo.anterior == null
lista.primerNodo := nodo.siguiente
else
nodo.anterior.siguiente := nodo.siguiente
if nodo.siguiente== null
lista.ultimoNodo := nodo.anterior
else
nodo.siguiente.anterior := nodo.anterior
destroy nodo
Una sutil consecuencia del procedimiento de arriba es que eliminando el último nodo de una lista asigna a primerNodo y a ultimoNodo a null, y de esta forma maneja correctamente eliminar el último nodo de una lista de un solo elemento. Tampoco necesitamos separar los métodos "EliminarAtras" o "EliminarAdelante", porque en una lista doblemente enlazada podemos usar "Elimina(nodo.anterior)" o "Elimina(nodo.siguiente)" cuando sea válido. También se asume que está garantizado que el nodo siendo eliminado existe. Si el nodo no existe en la lista, entonces algún manejo de error será requerido.
lista Doblemente Enlazada Circular[editar]
Recorriendo la lista[editar]
Asumir que algunNodo es algún nodo en una lista no vacía, este código recorre la lista empezando por' 'algunNodo:
Hacia delante
nodo := algunNodo
do
nodo := nodo.siguiente
while nodo ≠ algunNodo
Hacia atrás
nodo := algunNodo
do
nodo := nodo.anterior
while nodo ≠ algunNodo
Notar que la condición se ejecuta al final del ciclo. Esto es importante para el caso en que la lista contiene el único nodo algunNodo.
Insertar un Nodo[editar]
Esta simple función inserta un nodo en una lista doblemente enlazada circular delante de un elemento dado:
function InsertaDelante(Nodo nodo, Nodo nuevoNodo)
nuevoNodo.siguiente := nodo.siguiente
nuevoNodo.anterior := nodo
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
Para hacer un "InsertaAtras" podemos hacer simplemente "InsertaDelante(nodo.anterior, nuevoNodo)".
Insertar un elemento en una lista posiblemente vacía requiere una función especial:
function InsertaAlFinal(Lista lista, Nodo nodo)
if lista.ultimoNodo == null
nodo.anterior := nodo
nodo.siguiente := nodo
else
InsertaDelante(lista.ultimoNodo, nodo)
lista.ultimoNodo:= nodo
Para insertar en el principio simplemente hacemos "InsertaDelante(lista.ultimoNodo , nodo)".
Finalmente para eliminar un nodo debemos lidiar con el caso donde la lista es vacía:
function Elimina(Lista lista, Nodo nodo)
if nodo.siguiente == nodo
lista.ultimoNodo := null
else
nodo.siguiente.anterior := nodo.anterior
nodo.anterior.siguiente := nodo.siguiente
if nodo == lista.ultimoNodo
lista.ultimoNodo:= nodo.anterior;
destroy nodo
Los enlaces de un nodo de una lista doblemente enlazada son frecuentemente llamados anterior y siguiente o antecesor y sucesor. Las referencias guardadas en los enlaces son usualmente implementadas como punteros,pero también podrían ser índices de un array donde están los nodos.
Algoritmos Básicos[editar]
lista doblemente enlazada[editar]
record NodoDoblementeEnlazado {
siguiente // Una referencia al nodo siguiente
anterior // Una referencia al nodo anterior
dato // dato o referencia al dato
}
record ListaDoblementeEnlazada {
NodoDoblementeEnlazado primerNodo // referencia al primer nodo de la lista
NodoDoblementeEnlazado ultimoNodo // referencia al último nodo de la lista
}
Recorriendo la lista[editar]
Recorrer una lista doblemente enlazada puede ser en cualquier dirección. De hecho, la dirección del recorrido puede cambiar muchas veces, si se desea. Recorrido es frecuentemente llamado iteración.
Hacia adelante
nodo := lista.primerNodo
while nodo ≠ null
nodo := nodo.siguiente
Hacia atrás
nodo := lista.ultimoNodo
while nodo ≠ null
nodo := nodo.anterior
Insertando un nodo[editar]
Estas funciones insertan un nodo ya sea adelante o atrás de un nodo dado:
function InsertaAdelante(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo
nuevoNodo.siguiente := nodo.siguiente
if nodo.siguiente == null
lista.ultimoNodo := nuevoNodo
else
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
function InsertaAtras(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo.anterior
nuevoNodo.siguiente := nodo
if nodo.anterior == null
lista.primerNodo := nuevoNodo
else
nodo.anterior.siguiente := nuevoNodo
nodo.anterior := nuevoNodo
También necesitamos una función para insertar un nodo al principio de una lista posiblemente vacía:
function InsertaAlPrincipio(Lista lista, Nodo nuevoNodo)
if lista.primerNodo == null
lista.primerNodo := nuevoNodo
lista.ultimoNodo := nuevoNodo
nuevoNodo.anterior := null
nuevoNodo.siguiente := null
else
InsertaAtras(lista, lista.primerNodo , nuevoNodo)
La siguiente función inserta al final:
function InsertaAlFinal(Lista lista, Nodo nuevoNodo)
if lista.ultimoNodo == null
InsertaAlPrincipio(lista, nuevoNodo)
else
InsertatAdelante(lista, lista.ultimoNodo, nuevoNodo)
Borrando un Nodo[editar]
Eliminar un nodo es más fácil que insertar, pero requiere un manejo especial si el nodo a eliminar es el primerNodo o el ultimoNodo:
function Elimina(Lista lista, Nodo nodo)
if nodo.anterior == null
lista.primerNodo := nodo.siguiente
else
nodo.anterior.siguiente := nodo.siguiente
if nodo.siguiente== null
lista.ultimoNodo := nodo.anterior
else
nodo.siguiente.anterior := nodo.anterior
destroy nodo
Una sutil consecuencia del procedimiento de arriba es que eliminando el último nodo de una lista asigna a primerNodo y a ultimoNodo a null, y de esta forma maneja correctamente eliminar el último nodo de una lista de un solo elemento. Tampoco necesitamos separar los métodos "EliminarAtras" o "EliminarAdelante", porque en una lista doblemente enlazada podemos usar "Elimina(nodo.anterior)" o "Elimina(nodo.siguiente)" cuando sea válido. También se asume que está garantizado que el nodo siendo eliminado existe. Si el nodo no existe en la lista, entonces algún manejo de error será requerido.
lista Doblemente Enlazada Circular[editar]
Recorriendo la lista[editar]
Asumir que algunNodo es algún nodo en una lista no vacía, este código recorre la lista empezando por' 'algunNodo:
Hacia delante
nodo := algunNodo
do
nodo := nodo.siguiente
while nodo ≠ algunNodo
Hacia atrás
nodo := algunNodo
do
nodo := nodo.anterior
while nodo ≠ algunNodo
Notar que la condición se ejecuta al final del ciclo. Esto es importante para el caso en que la lista contiene el único nodo algunNodo.
Insertar un Nodo[editar]
Esta simple función inserta un nodo en una lista doblemente enlazada circular delante de un elemento dado:
function InsertaDelante(Nodo nodo, Nodo nuevoNodo)
nuevoNodo.siguiente := nodo.siguiente
nuevoNodo.anterior := nodo
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
Para hacer un "InsertaAtras" podemos hacer simplemente "InsertaDelante(nodo.anterior, nuevoNodo)".
Insertar un elemento en una lista posiblemente vacía requiere una función especial:
function InsertaAlFinal(Lista lista, Nodo nodo)
if lista.ultimoNodo == null
nodo.anterior := nodo
nodo.siguiente := nodo
else
InsertaDelante(lista.ultimoNodo, nodo)
lista.ultimoNodo:= nodo
Para insertar en el principio simplemente hacemos "InsertaDelante(lista.ultimoNodo , nodo)".
Finalmente para eliminar un nodo debemos lidiar con el caso donde la lista es vacía:
function Elimina(Lista lista, Nodo nodo)
if nodo.siguiente == nodo
lista.ultimoNodo := null
else
nodo.siguiente.anterior := nodo.anterior
nodo.anterior.siguiente := nodo.siguiente
if nodo == lista.ultimoNodo
lista.ultimoNodo:= nodo.anterior;
destroy nodo
domingo, 17 de diciembre de 2017
LISTAS ENLAZADAS
Una lista
enlazada o estructura ligada, es una estructura lineal que almacena
una colección de elementos generalmente llamados nodos, en donde cada nodo
puede almacenar datos y ligas a otros nodos. De esta manera los nodos pueden localizarse
en cualquier parte de la memoria, utilizando la referencia que lo relaciona con
otro nodo dentro de la estructura.
Las listas enlazadas
son estructuras dinámicas que se utilizan para almacenar datos que están
cambiando constante mente. A diferencia de los vectores, las estructuras
dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de
añadir o eliminar información.
Las listas
enlazadas permiten almacenar información en posiciones de memoria que no sean
contiguas; y se almacena en los elementos nodos. Estos nodos poseen dos campos
uno para almacenar la información o valor del elemento y
otro para el enlace que determina la posición del siguiente elemento o nodo de
la lista.
Ilustración 1. Estructura de un nodo
Se compone de dos partes: una
que contiene la información en sí y la segunda es un puntero y q su función es apuntar al siguiente nodo que haya.
Listas enlazadas simples
Una lista
enlazada simple es una colección de nodos que tienen una sola dirección y que en
conjunto forman una estructura de datos lineal. Cada nodo es un objeto
compuesto que guarda una referencia a un elemento (dato) y una referencia a
otro nodo (dirección).
La referencia que
guarda un nodo a otro nodo se puede considerar un enlace o
un puntero hacia el segundo nodo y el salto que los relaciona recibe
el nombre de salto de enlace o salto de puntero. El primer nodo
de una lista recibe el nombre de cabeza,
cabecera o primero y el último es llamado final,
cola o último (es el único nodo con la referencia a otro objeto
como nula).
Un nodo de una lista
enlazada simple puede determinar quien se encuentra después de él, pero no
puede determinar quien se encuentra antes, ya que solo cuenta con la dirección
del nodo siguiente pero no del anterior.
Ilustración 2. Se observa un puntero que va a apuntar al
primer elemento que se ingresa y otro puntero que apuntara al último que será
NULO.
Cuando tenemos una
lista de la siguiente manera cada puntero apuntara al nodo siguiente y el
puntero de la última lista como no tiene a donde apuntar entonces apuntara a
NULO.
Para acceder a un
nodo se utiliza la anterior con excepción del primero (no tiene a nadie antes)
al que se tiene que acceder a través de un puntero externo a la lista, entonces
se usa los punteros INICIO que es el que apunta constantemente al primero y el
puntero ultimo q es el q apunta constantemente al último.
|
Ilustración 3.
Esquema de una lista simple enlazada.
|
Listas doblemente enlazadas
Una lista doblemente
ligada es una colección de nodos, en la cual cada uno de ellos tiene dos
apuntadores (fig. 3.1a), uno apuntando a su predecesor (LIGAIZQ) y otro a su
sucesor (LIGADER). Por medio de estos punteros se podrá entonces avanzar o
retroceder a través de la lista, según se tomen las direcciones de uno u otro
puntador. La figura 3.1b) representa una lista doblemente ligada que almacena
apellidos.
Para tener un fácil
acceso a la información de la lista es recomendable usar dos apuntadores, P y
F, que apunten al principio y al final de esta, respectivamente.
Ilustración 4. a)
Estructura de un nodo. b) lista
doblemente ligada.
Listas circulares doblemente enlazadas
Las listas circulares
son estructuras de datos en la que el último nodo apunta al primero lo cual la
convierte en una lista sin fin, cada nodo siempre tiene uno anterior y uno
siguiente, su estructura es muy similar a las listas
simples por lo cual comparten características tanto en su implementación
como en su manejo aunque requiere un mayor entendimiento del manejo de los
punteros.
Tiene las siguientes características:
- No existe ningún nodo que apunte a null.
- La lista no tiene fin ya que al llegar al último nodo empieza de nuevo la lista.
- Se accede a la lista mediante el primer nodo o también llamado inicio de la lista.
- Si no se tiene cuidado al manejar la lista circular se pueden crear bucles infinitos.
- No tiene acceso aleatorio es decir para acceder a un valor se debe recorrer toda la lista.
Ilustración 5. Estructura de una
lista circular.
Suscribirse a:
Comentarios (Atom)