final public String toString()
{
return nombre + " de area " + area();
}
}
// Clases derivadas
public class Circulo extends Figura
{
static final private double PI = 3.141592653;
private double radio;
public Circulo( double r )
{
super( "circulo" );
radio = r;
}
public double area()
{
return PI*radio*radio;
}
}
public class Rectangulo extends Figura
{
private double largo;
private double ancho;
public Rectangulo( double l, double a )
{
super( "rectangulo" );
largo = l;
ancho = a;
}
public double area()
{
return largo*ancho;
}
}
public class Cuadrado extends Rectangulo
{
public Cuadrado( double lado )
{
super( lado, lado );
}
}
Herencia múltiple
En algunos lenguajes, una clase puede heredar de más de una clase base. En Java esto no se permite, lo cual evita los conflictos que se podrían producir al heredarse definiciones incompatibles de métodos y variables.
Interfaz
Una interfaz es un mecanismo que permite lograr algunos de los efectos de la herencia múltiple, sin sus problemas.
Una interfaz es una clase que sólo tiene métodos públicos abstractos y campos públicos estáticos finales.
Se dice que una clase implementa a la interfaz si provee definiciones para todos los métodos abstractos de la interfaz.
Una clase puede extender sólo a una clase base, pero puede implementar muchas interfaces.
Ejemplo:
package Definiciones;
public interface Comparable
{
public int Compare( Comparable b );
}
final public class Entero implements Comparable
{
private int valor;
public Entero( int x )
{
valor = x;
}
public String toString()
{
return Integer.toString( valor );
}
public int valorEntero()
{
return valor;
}
public int Compare( Comparable b )
{
return valor – ((Entero) b).valor;
}
}
Uso de interfaces para implementar componentes genéricas
Ejemplo: Ordenación por inserción que ordena objetos de cualquier tipo.
package Ordenacion;
import Definiciones.*;
public static void insercion( Comparable[] a )
{
for( int k=0; k
{
int j;
Comparable t = a[k];
for( j=k; j>0 &&
t.Compare(a[j-1])<0; –j)
a[j] = a[j-1];
a[j] = t;
}
}
Ejemplo de uso: Ordenar enteros entregados como argumentos.
import Definiciones.*;
public class PruebaOrdenacion
{
public static void main( String[] args )
{
Entero[] a = new Entero[args.length];
for( int i=0; i
a[i] = new Entero( Integer.parseInt(args[i]) );
Ordenacion.insercion( a );
for( int i=0; i
System.out.println( a[i] );
}
}
Estructuras de datos básicas
Toda la información que se maneja dentro de un computador se encuentra almacenada en su memoria, que en términos simples es una secuencia de caracteres (bytes) en donde se encuentran las instrucciones y datos a los que se accede directamente a través del procesador del computador.
Los sistemas o métodos de organización de datos que permiten un almacenamiento eficiente de la información en la memoria del computador son conocidos como estructuras de datos. Estos métodos de organización constituyen las piezas básicas para la construcción de algoritmos complejos, y permiten implementarlos de manera eficiente.
En el presente capítulo se presentan las estructuras de datos básicas como son arreglos, listas enlazadas y árboles, con las cuales se implementarán posteriormente los tipos de datos abstractos.
Arreglos
Un arreglo es una secuencia contigua de un número fijo de elementos homogéneos. En la siguiente figura se muestra un arreglo de enteros con 10 elementos:
En Java un arreglo se define como:
tipo[] nombre = new tipo[n_elem];
donde tipo corresponde al tipo de los elementos que contendrá el arreglo (enteros, reales, caracteres, etc..), nombre corresponde al nombre con el cual se denominará el arreglo, y n_elem corresponde al número de elementos que tendrá el arreglo. Para el caso del ejemplo presentado, la declaración del arreglo de enteros es:
int[] arreglo = new int[10];
Para acceder a un elemento del arreglo se utiliza un índice que identifica a cada elemento de manera única. Los índices en Java son números enteros correlativos y comienzan desde cero, por lo tanto, si el arreglo contiene n_elem elementos el índice del último elemento del arreglo es n_elem-1. El siguiente código muestra como se puede inicializar el arreglo del ejemplo, luego de ser declarado:
arreglo[0]=80; //el primer indice de los arreglos en Java es 0
arreglo[1]=45;
arreglo[2]=2;
arreglo[3]=21;
arreglo[4]=92;
arreglo[5]=17;
arreglo[6]=5;
arreglo[7]=65;
arreglo[8]=14;
arreglo[9]=34; //el ultimo indice del arreglo es 10-1 = 9
También se puede declarar e inicializar el arreglo en una sola línea:
int[] arreglo={80, 45, 2, 21, 92, 17, 5, 65, 14, 34};
Una ventaja que tienen los arreglos es que el costo de acceso de un elemento del arreglo es constante, es decir no hay diferencias de costo entre accesar el primer, el último o cualquier elemento del arreglo, lo cual es muy eficiente. La desventaja es que es necesario definir a priori el tamaño del arreglo, lo cual puede generar mucha pérdida de espacio en memoria si se definen arreglos muy grandes para contener conjuntos pequeños de elementos (Nota: en Java es posible hacer crecer el tamaño de un arreglo de manera dinámica).
Punteros y variables de referencia
Un puntero es una variable que almacena la dirección de memoria de otra variable, es decir, almacena el valor del lugar físico en la memoria en donde se encuentra almacenada dicha variable. Si se imagina que la memoria del computador es un gran arreglo de bytes, la dirección de memoria correspondería al índice de los casilleros de dicho arreglo, que es precisamente lo que se almacena en el puntero.
En algunos lenguajes de programación, por ejemplo C, es posible declarar explícitamente punteros para distintos tipos de variables, e incluso es posible realizar aritmética de punteros para realizar operaciones de manera muy eficiente, a cambio de "oscurecer" el código del programa y con una alta probabilidad de cometer errores de programación díficiles de detectar.
En Java no se puede declarar punteros de manera explícita ni tampoco realizar aritmética de punteros. Por lo tanto es imposible en Java tener un puntero a cualquiera de los tipos primitivos: enteros, reales, caracteres y booleanos. Los strings y arreglos no son tipos primitivos en Java.
Una variable de referencia, o simplemente una referencia, es una variable que almacena la dirección de memoria en donde se ubica un objeto. Nótese que si bien la definición es prácticamente idéntica a la de puntero, la diferencia radica en que una referencia sólo puede apuntar a objetos residentes en memoria, lo cual excluye a los tipos primitivos. A partir de esta definición se puede concluir que toda variable en Java, que no sea de tipo primitivo, es una referencia.
Por ejemplo, todas las clases en Java heredan de la clase Object. Una instancia de ésta clase se declara como:
Object aux=new Object();
La variable aux es una referencia a un objeto de la clase Object que permite saber la ubicación de dicho objeto dentro de la memoria, información suficiente para poder operar con él. Intuitivamente, la referencia es como una "flecha" que nos indica la posición del objeto que apunta:
Listas enlazadas
Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:
class NodoLista
{
Object elemento;
NodoLista siguiente;
}
La referencia contenida en el nodo de una lista se denomina siguiente, pues indica en dónde se encuentra el siguiente elemento de la lista. El último elemento de la lista no tiene nodo siguiente, por lo que se dice que la referencia siguiente del último elemento es null (nula).
La siguiente figura muestra un ejemplo de una lista enlazada cuyos elementos son strings:
La referencia lista indica la posición del primer elemento de la lista y permite acceder a todos los elementos de ésta: basta con seguir las referencias al nodo siguiente para recorrer la lista.
NodoLista aux=lista;
aux=aux.siguiente;
Siguiendo con el ejemplo anterior, para insertar un nuevo nodo justo delante del nodo referenciado por aux se deben modificar las referencias siguiente del nodo aux y del nodo a insertar.
NodoLista nuevo=new NodoLista(…);
//"nuevo" es la referencia del nodo a insertar en la lista
nuevo.siguiente=aux.siguiente;
aux.siguiente=nuevo;
//Notese que no es lo mismo realizar los cambios de referencia
//en un orden distinto al presentado, puesto que en ese caso
//se "pierde" la lista desde el nodo siguiente a aux
El procedimiento presentado a continuación es un ejemplo de cómo se programa el recorrido de una lista enlazada. Se supondrá que los objetos almacenados en cada nodo son strings:
void recorrido(NodoLista lista)
{
NodoLista aux=lista;
while (aux!=null)
{
System.out.println(aux.elemento);
aux=aux.siguiente;
}
}
Para invertir el orden de la lista, es decir, que el último elemento de la lista ahora sea el primero, que el penúltimo elemento de la lista ahora sea el segundo, etc…, modificando sólo las referencias y no el contenido de los nodos, es necesario realizar una sola pasada por la lista, y en cada nodo visitado se modifica la referencia siguiente para que apunte al nodo anterior. Es necesario mantener referencias auxiliares para acordarse en donde se encuentra el nodo anterior y el resto de la lista que aún no ha sido modificada:
void invertir(NodoLista lista)
{
NodoLista siguiente=lista;
NodoLista anterior=null;
while(lista!=null)
{
siguiente=lista.siguiente;
lista.siguiente=anterior;
anterior=lista;
lista=siguiente;
}
}
La implementación vista de los nodos también se conoce como lista de enlace simple, dado que sólo contiene una referencia al nodo siguiente y por lo tanto sólo puede recorrerse en un solo sentido. En una lista de doble enlace se agrega una segunda referencia al nodo previo, lo que permite recorrer la lista en ambos sentidos, y en general se implementa con una referencia al primer elemento y otra referencia al último elemento.
Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.
En muchas aplicaciones que utilizan listas enlazadas es útil contar con un nodo cabecera, tambien conocido como dummy o header, que es un nodo "falso", ya que no contiene información relevante, y su referencia siguiente apunta al primer elemento de la lista. Al utilizar un nodo cabecera siempre es posible definir un nodo previo a cualquier nodo de la lista, definiendo que el previo al primer elemento es la cabecera.
Si se utiliza un nodo cabecera en una lista de doble enlace ya no es necesario contar con las referencias primero y último, puesto que el nodo cabecera tiene ambas referencias: su referencia siguiente es el primer elemento de la lista, y su referencia anterior es el último elemento de la lista. De esta forma la lista de doble enlace queda circular de una manera natural.
Árboles
Un árbol se define como una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol esta vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como subárboles. Las raíces de los subárboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus subárboles. Una visión gráfica de esta definición recursiva se muestra en la siguiente figura:
Los nodos que no poseen hijos se denominan hojas. Dos nodos que tienen el padre en común se denominan hermanos.
Un camino entre un nodo n1 y un nodo nk está definido como la secuencia de nodos n1, n2, …, nk tal que ni es padre de ni+1, 1 <= i < k. El largo del camino es el número de referencias que componen el camino, que para el ejemplo son k-1. Existe un camino desde cada nodo del árbol a sí mismo y es de largo 0. Nótese que en un árbol existe un único camino desde la raíz hasta cualquier otro nodo del árbol. A partir del concepto de camino se definen los conceptos de ancestro y descendiente: un nodo n es ancestro de un nodo m si existe un camino desde n a m; un nodo n es descendiente de un nodo m si existe un camino desde m a n.
Se define la profundidad del nodo nk como el largo del camino entre la raíz del arbol y el nodo nk. Esto implica que la profundidad de la raíz es siempre 0. La altura de un nodo nk es el máximo largo de camino desde nk hasta alguna hoja. Esto implica que la altura de toda hoja es 0. La altura de un árbol es igual a la altura de la raíz, y tiene el mismo valor que la profundidad de la hoja más profunda. La altura de un árbol vacío se define como -1.
La siguiente figura muestra un ejemplo de los conceptos previamente descritos:
A es la raíz del árbol.
A es padre de B, C y D.
E y F son hermanos, puesto que ambos son hijos de B.
E, J, K, L, C, P, Q, H, N y O son las hojas del árbol.
El camino desde A a J es único, lo conforman los nodos A-B-F-J y es de largo 3.
D es ancestro de P, y por lo tanto P es descendiente de D.
L no es descendiente de C, puesto que no existe un camino desde C a L.
La profundidad de C es 1, de F es 2 y de Q es 4.
La altura de C es 0, de F es 1 y de D es 3.
La altura del árbol es 4 (largo del camino entre la raíz A y la hoja más profunda, P o Q).
Un árbol binario es un árbol en donde cada nodo posee 2 referencias a subárboles (ni más, ni menos). En general, dichas referencias se denominan izquierda y derecha, y consecuentemente se define el subárbol izquierdo y subárbol derecho del arbol.
En este caso, la implementacion del nodo de un árbol binario es como sigue:
class NodoArbolBinario
{
Object elemento;
NodoArbolBinario izq;
NodoArbolBinario der;
}
Los nodos en sí que conforman un árbol binario se denominan nodos internos, y todas las referencias que son null se denominan nodos externos.
Propiedades de los árboles binarios
Propiedad 1:
Si se define i = número de nodos internos, e = número de nodos externos, entonces se tiene que:
e = i+1
Demostración: inducción sobre i (ejercicio).
Propiedad 2:
Sea n = número de nodos internos. Se define:
In = suma del largo de los caminos desde la raíz a cada nodo interno (largo de caminos internos).
En = suma del largo de los caminos desde la raíz a cada nodo externo (largo de caminos externos).
Se tiene que:
En = In+2n
Demostración: inducción sobre n (ejercicio).
Propiedad 3:
¿Cuántos árboles binarios distintos se pueden construir con n nodos internos?
n | bn |
0 | 1 |
1 | 1 |
2 | 2 |
3 | 5 |
¿bn?
Por ejemplo: b4 = b0*b3 + b1*b2 + b2*b1 + b3*b0 = 5 + 2 + 2 + 5 = 14.
Este tipo de ecuaciones se puede resolver y la solución es la siguiente:
La serie de numeros que genera bn se conoce como números de Catalan. Asintóticamente:
Ejemplo: árboles de expresiones matemáticas
La siguiente figura muestra un ejemplo de un árbol de expresiones matemáticas. En un árbol de expresiones las hojas corresponden a los operandos de la expresión (variables o constantes), mientras que los nodos restantes contienen operadores. Dado que los operadores matemáticos son binarios (o unarios como en el caso del operador signo -), un árbol de expresiones resulta ser un árbol binario.
Un árbol de expresiones se puede evaluar de la siguiente forma:
Si la raíz del árbol es una constante o una variable se retorna el valor de ésta.
Si la raíz resulta ser un operador, entonces recursivamente se evalúan los subárboles izquierdo y derecho, y se retorna el valor que resulta al operar los valores obtenidos de las evaluaciones de los subárboles con el operador respectivo.
Recorridos de árboles binarios
Existen tres formas principales para recorrer un árbol binario en forma recursiva. Estas son:
Preorden: raíz – subárbol izquierdo – subárbol derecho.
Inorden: subárbol izquierdo – raiz – subárbol derecho.
Postorden: subárbol izquierdo – subárbol derecho – raíz.
Por ejemplo, al recorrer el árbol de expresiones anterior en preorden se obtiene: * + a b – c d
Al recorrer el árbol en inorden se obtiene: a + b * c – d
Al recorrer el árbol en postorden se obtiene: a b + c d – *
La expresión que se obtiene con el recorrido en postorden se conoce como notación polaca.
En un árbol general cada nodo puede poseer un número indeterminado de hijos. La implementación de los nodos en este caso se realiza de la siguiente manera: como no se sabe de antemano cuantos hijos tiene un nodo en particular se utilizan dos referencias, una a su primer hijo y otra a su hermano más cercano. La raíz del árbol necesariamente tiene la referencia a su hermano como null.
class NodoArbolGeneral
{
Object elemento;
NodoArbolGeneral hijo;
NodoArbolGeneral hermano;
}
Nótese que todo árbol general puede representarse como un árbol binario, con la salvedad que el hijo derecho de la raíz es siempre null. Si se permite que la raíz del árbol tenga hermanos, lo que se conoce como bosque, entonces se tiene que el conjunto de los bosques generales es isomorfo al conjunto de los árboles binarios. En efecto, las propiedades vistas en los árboles binarios se siguen cumpliendo en los árboles generales.
Un Tipo de dato abstracto (en adelante TDA) es un conjunto de datos u objetos al cual se le asocian operaciones. El TDA provee de una interfaz con la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera en como estén implementadas dichas operaciones. Esto quiere decir que un mismo TDA puede ser implementado utilizando distintas estructuras de datos y proveer la misma funcionalidad.
El paradigma de orientación a objetos permite el encapsulamiento de los datos y las operaciones mediante la definición de clases e interfaces, lo cual permite ocultar la manera en cómo ha sido implementado el TDA y solo permite el acceso a los datos a través de las operaciones provistas por la interfaz.
En este capítulo se estudiarán TDA básicos como lo son las listas, pilas y colas, y se mostrarán algunos usos prácticos de estos TDA.
TDA lista
Una lista se define como una serie de N elementos E1, E2, …, EN, ordenados de manera consecutiva, es decir, el elemento Ek (que se denomina elemento k-ésimo) es previo al elemento Ek+1. Si la lista contiene 0 elementos se denomina como lista vacía.
Las operaciones que se pueden realizar en la lista son: insertar un elemento en la posición k, borrar el k-ésimo elemento, buscar un elemento dentro de la lista y preguntar si la lista esta vacía.
Una manera simple de implementar una lista es utilizando un arreglo. Sin embargo, las operaciones de inserción y borrado de elementos en arreglos son ineficientes, puesto que para insertar un elemento en la parte media del arreglo es necesario mover todos los elementos que se encuentren delante de él, para hacer espacio, y al borrar un elemento es necesario mover todos los elementos para ocupar el espacio desocupado. Una implementación más eficiente del TDA se logra utilizando listas enlazadas.
A continuación se presenta una implementación en Java del TDA utilizando listas enlazadas y sus operaciones asociadas:
estaVacia(): devuelve verdadero si la lista esta vacía, falso en caso contrario.
insertar(x, k): inserta el elemento x en la k-ésima posición de la lista.
buscar(x): devuelve la posición en la lista del elemento x.
buscarK(k): devuelve el k-ésimo elemento de la lista.
eliminar(x): elimina de la lista el elemento x.
En la implementación con listas enlazadas es necesario tener en cuenta algunos detalles importantes: si solamente se dispone de la referencia al primer elemento, el añadir o remover en la primera posición es un caso especial, puesto que la referencia a la lista enlazada debe modificarse según la operación realizada. Además, para eliminar un elemento en particular es necesario conocer el elemento que lo antecede, y en este caso, ¿qué pasa con el primer elemento, que no tiene un predecesor?
Para solucionar estos inconvenientes se utiliza la implementación de lista enlazada con nodo cabecera. Con esto, todos los elementos de la lista tendrán un elemento previo, puesto que el previo del primer elemento es la cabecera. Una lista vacía corresponde, en este caso, a una cabecera cuya referencia siguiente es null.
Los archivos NodoLista.java, IteradorLista.java y Lista.java contienen una implementación completa del TDA lista. La clase NodoLista implementa los nodos de la lista enlazada, la clase Lista implementa las operaciones de la lista propiamente tal, y la clase IteradorLista implementa objetos que permiten recorrer la lista y posee la siguiente interfaz:
avanzar(): avanza el iterador al siguiente nodo de la lista.
obtener(): retorna el elemento del nodo en donde se encuentra el iterador.
Costo de las operaciones en tiempo:
Insertar/eliminar elemento en k-ésima posición: O(k) (¿Se puede hacer en O(1)?).
Buscar elemento x: O(N) (promedio).
TDA pila
Una pila (stack o pushdown en inglés) es una lista de elementos de la cual sólo se puede extraer el último elemento insertado. La posición en donde se encuentra dicho elemento se denomina tope de la pila. También se conoce a las pilas como listas LIFO (LAST IN – FIRST OUT: el último que entra es el primero que sale).
La interfaz de este TDA provee las siguientes operaciones:
apilar(x): inserta el elemento x en el tope de la pila (push en inglés).
desapilar(): retorna el elemento que se encuentre en el tope de la pila y lo elimina de ésta (pop en inglés).
tope(): retorna el elemento que se encuentre en el tope de la pila, pero sin eliminarlo de ésta (top en inglés).
estaVacia(): retorna verdadero si la pila no contiene elementos, falso en caso contrario (isEmpty en inglés).
Nota: algunos autores definen desapilar como sacar el elemento del tope de la pila sin retornarlo.
Implementación del TDA pila
A continuación se muestran dos maneras de implementar una pila: utilizando un arreglo y utilizando una lista enlazada. En ambos casos el costo de las operaciones es de O(1).
Implementación utilizando arreglos
Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo de dato que se almacenará en la pila. Una variable de instancia indicará la posición del tope de la pila, lo cual permitirá realizar las operaciones de inserción y borrado, y también permitirá saber si la pila esta vacía, definiendo que dicha variable vale -1 cuando no hay elementos en el arreglo.
class PilaArreglo
{
private Object[] arreglo;
private int tope;
private int MAX_ELEM=100; // maximo numero de elementos en la pila
public PilaArreglo()
{
arreglo=new Object[MAX_ELEM];
tope=-1; // inicialmente la pila esta vacía
}
public void apilar(Object x)
{
if (tope+1
{
tope++;
arreglo[tope]=x;
}
}
public Object desapilar()
{
if (!estaVacia()) // si esta vacia se produce UNDERFLOW
{
Object x=arreglo[tope];
tope–;
return x;
}
}
public Object tope()
{
if (!estaVacia()) // si esta vacia es un error
{
Object x=arreglo[tope];
return x;
}
}
public boolean estaVacia()
{
if (tope==-1)
{
return true;
}
else
{
return false;
}
}
}
El inconveniente de esta implementación es que es necesario fijar de antemano el número máximo de elementos que puede contener la pila, MAX_ELEM, y por lo tanto al apilar un elemento es necesario controlar que no se inserte un elemento si la pila esta llena. Sin embargo, en Java es posible solucionar este problema creando un nuevo arreglo más grande que el anterior, el doble por ejemplo, y copiando los elementos de un arreglo a otro:
public void apilar(Object x)
{
if (tope+1
{
tope++;
arreglo[tope]=x;
}
else
{
MAX_ELEM=MAX_ELEM*2;
Object[] nuevo_arreglo=new Object[MAX_ELEM];
for (int i=0; i
{
nuevo_arreglo[i]=arreglo[i];
}
tope++;
nuevo_arreglo[tope]=x;
arreglo=nuevo_arreglo;
}
}
Implementación utilizando listas enlazadas
En este caso no existe el problema de tener que fijar el tamaño máximo de la pila (aunque siempre se está acotado por la cantidad de memoria disponible!). La implementación es bastante simple: los elementos siempre se insertan al principio de la lista (apilar) y siempre se extrae el primer elemento de la lista (desapilar y tope), por lo que basta con tener una referencia al principio de la lista enlazada. Si dicha referencia es null, entonces la pila esta vacía.
class PilaLista
{
private NodoLista lista;
public PilaLista()
{
lista=null;
}
public void apilar(Object x)
{
lista=new NodoLista(x, lista);
}
public Object desapilar() // si esta vacia se produce UNDERFLOW
{
if (!estaVacia())
{
Object x=lista.elemento;
lista=lista.siguiente;
return x;
}
}
public Object tope()
{
if (!estaVacia()) // si esta vacia es un error
{
Object x=lista.elemento;
return x;
}
}
public boolean estaVacia()
{
return lista==null;
}
}
Dependiendo de la aplicación que se le de a la pila es necesario definir que acción realizar en caso de que ocurra overflow (rebalse de la pila) o underflow (intentar desapilar cuando la pila esta vacía). Java posee un mecanismo denominado excepciones, que permite realizar acciones cuando se producen ciertos eventos específicos (como por ejemplo overflow o underflow en una pila).
En ambas implementaciones el costo de las operaciones que provee el TDA tienen costo O(1).
Ejemplo de uso: eliminación de recursividad
Suponga que una función F realiza un llamado recursivo dentro de su código, lo que se ilustra en la siguiente figura:
Si la llamada recursiva es lo último que hace la función F, entonces dicha llamada se puede substituir por un ciclo while. Este caso es conocido como tail recursion y en lo posible hay que evitarlo en la programación, ya que cada llamada recursiva ocupa espacio en la memoria del computador, y en el caso del tail recursion es muy simple eliminarla. Por ejemplo:
void imprimir(int[] a, int j) // versión recursiva
{
if (j
{
System.out.println(a[j]);
imprimir(a, j+1); // tail recursion
}
}
void imprimir(int[] a, int j) // versión iterativa
{
while (j
{
System.out.println(a[j]);
j=j+1;
}
}
En el caso general, cuando el llamado recursivo se realiza en medio de la función F, la recursión se puede eliminar utilizando una pila.
Por ejemplo: recorrido en preorden de un arbol binario.
// "raiz" es la referencia a la raiz del arbol
// llamado inicial: preorden(raiz)
// version recursiva
void preorden(Nodo nodo)
{
if (nodo!=null)
{
System.out.print(nodo.elemento);
preorden(nodo.izq);
preorden(nodo.der);
}
}
// primera version iterativa
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
if (aux!=null)
{
System.out.print(aux.elemento);
// primero se apila el nodo derecho y luego el izquierdo
// para mantener el orden correcto del recorrido
// al desapilar los nodos
pila.apilar(aux.der);
pila.apilar(aux.izq);
}
}
}
// segunda version iterativa
// dado que siempre el ultimo nodo apilado dentro del bloque if es
// aux.izq podemos asignarlo directamente a aux hasta que éste sea
// null, es decir, el bloque if se convierte en un bloque while
// y se cambia el segundo apilar por una asignacion de la referencia
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
while (aux!=null)
{
System.out.print(aux.elemento);
pila.apilar(aux.der);
aux=aux.izq;
}
}
}
Si bien los programas no recursivos son más eficientes que los recursivos, la eliminación de recursividad (excepto en el caso de tail recursion) le quita claridad al código del programa. Por lo tanto:
A menudo es conveniente eliminar el tail recursion.
Un método recursivo es menos eficiente que uno no recursivo, pero sólo en pocas oportunidades vale la pena eliminar la recursión.
TDA cola
Una cola (queue en inglés) es una lista de elementos en donde siempre se insertan nuevos elementos al final de la lista y se extraen elementos desde el inicio de la lista. También se conoce a las colas como listas FIFO (FIRST IN – FIRST OUT: el primero que entra es el primero que sale).
Las operaciones básicas en una cola son:
encolar(x): inserta el elemento x al final de la cola (enqueue en inglés).
sacar(): retorna el elemento que se ubica al inicio de la cola (dequeue en inglés).
estaVacia(): retorna verdadero si la cola esta vacía, falso en caso contrario.
Al igual que con el TDA pila, una cola se puede implementar tanto con arreglos como con listas enlazadas. A continuación se verá la implementación usando un arreglo.
Las variables de instancia necesarias en la implementación son:
primero: indica el índice de la posición del primer elemento de la cola, es decir, la posición el elemento a retornar cuando se invoque sacar.
ultimo: indica el índice de la posición de último elemento de la cola. Si se invoca encolar, el elemento debe ser insertado en el casillero siguiente al que indica la variable.
numElem: indica cuántos elementos posee la cola. Definiendo MAX_ELEM como el tamaño máximo del arreglo, y por lo tanto de la cola, entonces la cola esta vacía si numElem==0 y está llena si numElem==MAX_ELEM.
Un detalle faltante es el siguiente: ¿qué pasa si la variable ultimo sobrepasa el rango de índices del arreglo? Esto se soluciona definiendo que si después de insertar un elemento el índice ultimo == MAX_ELEM, entonces se asigna ultimo = 0 , y los siguientes elementos serán insertados al comienzo del arreglo. Esto no produce ningún efecto en la lógica de las operaciones del TDA, pues siempre se saca el elemento referenciado por el índice primero, aunque en valor absoluto primero > ultimo. Este enfoque es conocido como implementación con arreglo circular, y la forma más fácil de implementarlo es haciendo la aritmética de subíndices módulo MAX_ELEM.
class ColaArreglo
{
private Object[] arreglo;
private int primero, ultimo, numElem;
private int MAX_ELEM=100; // maximo numero de elementos en la cola
public ColaArreglo()
{
arreglo=new Object[MAX_ELEM];
primero=0;
ultimo=MAX_ELEM-1;
numElem=0;
}
public void encolar(Object x)
{
if (numElem
{
ultimo=(ultimo+1)%MAX_ELEM;
arreglo[ultimo]=x;
numElem++;
}
}
public Object sacar()
{
if (!estaVacia()) // si esta vacia se produce UNDERFLOW
{
Object x=arreglo[primero];
primero=(primero+1)%MAX_ELEM;
numElem–;
return x;
}
}
public boolean estaVacia()
{
return numElem==0;
}
}
Nuevamente en este caso, dependiendo de la aplicación, se debe definir qué hacer en caso de producirse OVERFLOW o UNDERFLOW.
Con esta implementación, todas las operaciones del TDA cola tienen costo O(1).
TDA Cola de Prioridad
Una cola de prioridad es un tipo de datos abstracto que almacena un conjunto de datos que poseen una llave perteneciente a algún conjunto ordenado, y permite insertar nuevos elementos y extraer el máximo (o el mínimo, en caso de que la estructura se organice con un criterio de orden inverso).
Es frecuente interpretar los valores de las llaves como prioridades, con lo cual la estructura permite insertar elementos de prioridad cualquiera, y extraer el de mejor prioridad.
Dos formas simples de implementar colas de prioridad son:
Una lista ordenada:
Inserción: O(n)
Extracción de máximo: O(1)
Una lista desordenada:
Inserción: O(1)
Extracción de máximo: O(n)
Heaps
Un heap es un árbol binario de una forma especial, que permite su almacenamiento en un arreglo sin usar punteros.
Un heap tiene todos sus niveles llenos, excepto posiblemente el de más abajo, y en este último los nodos están lo más a la izquierda posible.
Ejemplo:
La numeración por niveles (indicada bajo cada nodo) son los subíndices en donde cada elemento sería almacenado en el arreglo. En el caso del ejemplo, el arreglo sería:
La característica que permite que un heap se pueda almacenar sin punteros es que, si se utiliza la numeración por niveles indicada, entonces la relación entre padres e hijos es:
Hijos del nodo j = {2*j, 2*j+1} Padre del nodo k = floor(k/2)
Un heap puede utilizarse para implementar una cola de prioridad almacenando los datos de modo que las llaves estén siempre ordenadas de arriba a abajo (a diferencia de un árbol de búsqueda binaria, que ordena sus llaves de izquierda a derecha). En otras palabras, el padre debe tener siempre mayor prioridad que sus hijos (ver ejemplo).
Implementación de las operaciones básicas
Inserción:
La inserción se realiza agregando el nuevo elemento en la primera posición libre del heap, esto es, el próximo nodo que debería aparecer en el recorrido por niveles o, equivalentemente, un casillero que se agrega al final del arreglo.
Después de agregar este elemento, la forma del heap se preserva, pero la restricción de orden no tiene por qué cumplirse. Para resolver este problema, si el nuevo elemento es mayor que su padre, se intercambia con él, y ese proceso se repite mientras sea necesario. Una forma de describir esto es diciendo que el nuevo elemento "trepa" en el árbol hasta alcanzar el nivel correcto según su prioridad.
El siguiente trozo de programa muestra el proceso de inserción de un nuevo elemento x:
a[++n]=x;
for(j=n; j>1 && a[j]>a[j/2]; j/=2)
{ # intercambiamos con el padre
t=a[j];
a[j]=a[j/2];
a[j/2]=t;
}
El proceso de inserción, en el peor caso, toma un tiempo proporcional a la altura del árbol, esto es, O(log n).
Extracción del máximo
El máximo evidentemente está en la raíz del árbol (casillero 1 del arreglo). Al sacarlo de ahí, podemos imaginar que ese lugar queda vacante. Para llenarlo, tomamos al último elemento del heap y lo trasladamos al lugar vacante. En caso de que no esté bien ahí de acuerdo a su prioridad (¡que es lo más probable!), lo hacemos descender intercambiándolo siempre con el mayor de sus hijos. Decimos que este elemento "se hunde" hasta su nivel de prioridad.
El siguiente trozo de programa implementa este algoritmo:
m=a[1]; # La variable m lleva el máximo
a[1]=a[n–]; # Movemos el último a la raíz y achicamos el heap
j=1;
while(2*j
{
k=2*j; # el hijo izquierdo
if(k+1<=n && a[k+1]>a[k])
k=k+1; # el hijo derecho es el mayor
if(a[j]>a[k])
break; # es mayor que ambos hijos
t=a[j];
a[j]=a[k];
a[k]=t;
j=k; # lo intercambiamos con el mayor hijo
}
Este algoritmo también demora un tiempo proporcional a la altura del árbol en el peor caso, esto es, O(log n).
Dado un conjunto de elementos {X1, X2, …, XN}, todos distintos entre sí, se desea almacenarlos en una estructura de datos que permita la implementación eficiente de las operaciones:
búsqueda(X): dado un elemento X, conocido como llave de búsqueda, encontrarlo dentro del conjunto o decir que no está.
inserción(X): agregar un nuevo elemento X al conjunto.
eliminación(X): eliminar el elemento X del conjunto.
Estas operaciones describen al TDA diccionario. En el presente capítulo se verán distintas implementaciones de este TDA y se estudiarán las consideraciones de eficiencia de cada una de dichas implementaciones.
Implementaciones sencillas
Una manera simple de implementar el TDA diccionario es utilizando una lista, la cual permite implementar la inserción de nuevos elementos de manera muy eficiente, definiendo que siempre se realiza al comienzo de la lista. El problema que tiene esta implementación es que las operaciones de búsqueda y eliminación son ineficientes, puesto que como en la lista los elementos están desordenados es necesario realizar una búsqueda secuencial. Por lo tanto, los costos asociados a cada operación son:
búsqueda: O(n) (búsqueda secuencial).
inserción: O(1) (insertando siempre al comienzo de la lista).
eliminación: O(n) (búsqueda + O(1)).
Otra manera sencilla de implementar el TDA es utilizando un arreglo ordenado. En este caso, la operación de inserción y eliminación son ineficientes, puesto que para mantener el orden dentro del arreglo es necesario "correr" los elementos para dejar espacio al insertar un nuevo elemento. Sin embargo, la ventaja que tiene mantener el orden es que es posible realizar una búsqueda binaria para encontrar el elemento buscado.
Suponga que se dispone del arreglo a, de tamaño n, en donde se tiene almacenado el conjunto de elementos ordenados de menor a mayor. Para buscar un elemento x dentro del arreglo se debe:
Buscar el índice de la posición media del arreglo en donde se busca el elemento, que se denotará m. Inicialmente, m = n/2.
Si a[m] = x se encontró el elemento (fin de la búsqueda), en caso contrario se sigue buscando en el lado derecho o izquierdo del arreglo dependiendo si a[m] < x o a[m] > x respectivamente.
Costo de la búsqueda binaria:
T(n) = 1 + T(n/2) (aproximadamente)T(n) = 2 + T(n/4)T(n) = 3 + T(n/8)…T(n) = k + T(n/2k) para todo k>=0Escogiendo k = log2n:=> T(n) = log2n + T(1) = 1 + log2n = O(log n).
Programación de la búsqueda binaria
La variable i representa el primer casillero del arreglo en donde es posible que se encuentre el elemento x, la variable j representa el último casillero del arreglo hasta donde x puede pertenecer, con j >= i.
Inicialmente: i = 0 y j = n-1.
En cada iteración:
Si el conjunto es vacío (j-i < 0), o sea si j < i, entonces el elemento x no está en el conjunto (búsqueda infructuosa).
En caso contrario, m = (i+j)/2. Si x = a[m], el elemento fue encontrado (búsqueda exitosa). Si x < a[m] se modifica j = m-1, sino se modifica i = m+1 y se sigue iterando.
Implementación:
public int busquedaBinaria(int []a, int x)
{
int i=0, j=a.length-1;
while (i<=j) {
int m=(i+j)/2;
if (x==a[m])
{
return m;
}
else if (x
{
j=m-1;
}
else
{
i=m+1;
}
} return NO_ENCONTRADO; // NO_ENCONTRADO se define como -1
}
Eficiencia de la búsqueda binaria
Si la única operación permitida entre los elementos del conjunto es la comparación, entonces ¿qué tan eficiente es la búsqueda binaria?.
Todo algoritmo de búsqueda basado en comparaciones corresponde a algún árbol de decisión. Cada nodo de dicho árbol corresponde al conjunto de elementos candidatos en donde se encuentra el elemento buscado, y que es consistente con las comparaciones realizadas entre los elementos. Los arcos del árbol corresponden a los resultados de las comparaciones, que en este caso pueden ser mayor que o menor que el elemento buscado, es decir, es un árbol de decisión binario.
El número de comparaciones realizadas por el algoritmo de búsqueda es igual a la altura del árbol de decisión (profundidad de la hoja más profunda).
Lema: sea D un árbol binario de altura h. D tiene a lo más 2h hojas.
Demostración: por inducción. Si h = 0 el árbol tiene un solo nodo que necesariamente es una hoja (no tiene hijos), con lo que se tiene el caso base. En el caso general, se tiene una raíz, que no puede ser una hoja, que posee un subárbol izquierdo y derecho, cada uno con una altura máxima de h-1. Por hipótesis de inducción, los subárboles pueden tener a lo más 2h-1 hojas, dando un total de a lo más 2h hojas entre ambos subárboles. Queda entonces demostrado.
Lema: un árbol binario con H hojas debe tener una profundidad de al menos 
Demostración: directo del lema anterior.
Si n es el número de nodos de elementos del conjunto, el número de respuestas posibles (hojas del árbol de decisión) es de n+1, el lema anterior implica que el costo en el peor caso es mayor o igual que el logaritmo del número de respuestas posibles.
Corolario: cualquier algoritmo de búsqueda mediante comparaciones se demora al menos 
preguntas en el peor caso. Por lo tanto, la búsqueda binaria es óptima.
Búsqueda secuencial con probabilidades de acceso no uniforme
Se tiene un conjunto de elementos X1, X2, …, XN, cuyas probabilidades de acceso son, respectivamente, P1, P2, …, PN. Naturalmente:
El costo esperado de la búsqueda secuencial es:
Este costo es mínimo cuando P1>=P2>=P3…>=PN.
¿Qué pasa si las probabilidades Pk no son conocidas de antemano? En este caso, no es posible ordenar a priori los elementos según su probabilidad de acceso de mayor a menor.
Métodos auto-organizantes
Idea: cada vez que se accesa un elemento Xk se modifica la lista para que los accesos futuros a Xk sean más eficientes. Algunas políticas de modificación de la lista son:
TR (transpose): se intercambia de posición Xk con Xk-1 (siempre que k>1).
MTF (move-to-front): se mueve el elemento Xk al principio de la lista.
Se puede demostrar que Costooptimo<=CostoTR<=CostoMTF<=2Costooptimo.
Arboles de búsqueda binaria
Un árbol de búsqueda binaria, en adelante ABB, es un árbol binario en donde todos los nodos cumplen la siguiente propiedad (sin perder generalidad se asumirá que los elementos almacenados son números enteros): si el valor del elemento almacenado en un nodo N es X, entonces todos los valores almacenados en el subárbol izquierdo de N son menores que X, y los valores almacenados en el subárbol derecho de N son mayores que X.
Los ABB permiten realizar de manera eficiente las operaciones provistas por el TDA diccionario, como se verá a continuación.
Búsqueda en un ABB
Esta operación retorna una referencia al nodo en donde se encuentra el elemento buscado, X, o null si dicho elemento no se encuentra en el árbol. La estructura del árbol facilita la búsqueda:
Si el árbol esta vacío, entonces el elemento no está y se retorna null.
Si el árbol no esta vacío y el elemento almacenado en la raiz es X, se encontró el elemento y se retorna una referencia a dicho nodo.
Si X es menor que el elemento almacenado en la raiz se sigue buscando recursivamente en el subárbol izquierdo, y si X es mayor que el elemento almacenado en la raíz se sigue buscando recursivamente en el subárbol derecho.
Nótese que el orden en los cuales se realizan los pasos anteriores es crucial para asegurar que la búsqueda en el ABB se lleve a cabo de manera correcta.
Costo de búsqueda en un ABB
Peor caso
Para un árbol dado, el peor caso es igual a la longitud del camino más largo desde la raíz a una hoja, y el peor caso sobre todos los árboles posibles es O(n).
Caso promedio
Supuestos:
Arbol con n nodos.
Probabilidad de acceso a los elementos uniforme.
Costo de búsqueda exitosa:
donde In es el largo de caminos internos.
Costo de búsqueda infructuosa:
donde En es el largo de caminos externos.
Recordando que En=In+2n, se tiene:
Por lo tanto, la ecuación que relaciona los costos de búsqueda exitosa e infructuosa es: (*)
Esto muestra que a medida que se insertan más elementos en el ABB los costos de búsqueda exitosa e infructuosa se van haciendo cada vez más parecidos.
El costo de inserción de un elemento en un ABB es igual al costo de búsqueda infructuosa justo antes de insertarlo más 1. Esto quiere decir que si ya habían k elementos en el árbol y se inserta uno más, el costo esperado de búsqueda para este último es 1+C'k. Por lo tanto:
Esta última ecuación implica que:
Restando ambas ecuaciones se obtiene: (**)
De la ecuación (*) se tiene:
Reemplazando en (**):
Obteniéndose la siguiente ecuación de recurrencia:
Desenrollando la ecuación: (***)
Se define Hn, conocido como números armónicos, como:
Se puede demostrar que:
Reemplazando en (***) y recordando (*) se obtiene:
Por lo tanto, el costo promedio de búsqueda en un ABB es O(log(n)).
Inserción en un ABB
Para insertar un elemento X en un ABB, se realiza una búsqueda infructuosa de este elemento en el árbol, y en el lugar en donde debiera haberse encontrado se inserta. Como se vio en la sección anterior, el costo promedio de inserción en un ABB es O(log(n)).
Eliminación en un ABB
Primero se realiza una búsqueda del elemento a eliminar, digamos X. Si la búsqueda fue infructuosa no se hace nada, en caso contrario hay que considerar los siguientes casos posibles:
Si X es una hoja sin hijos, se puede eliminar inmediatamente.
Si X tiene un solo hijo, entonces se cambia la referencia del padre a X para que ahora referencie al hijo de X.
Si X tiene dos hijos, el caso complicado, se procede de la siguiente forma: se elimina el nodo Y = minimo nodo del subárbol derecho de X, el cual corresponde a uno de los casos fáciles de eliminación, y se reemplaza el valor almacenado en el nodo X por el valor que estaba almacenado en el nodo Y.
Nótese que el árbol sigue cumpliendo las propiedades de un ABB con este método de eliminación.
Si de antemano se sabe que el número de eliminaciones será pequeño, entonces la eliminación se puede substituir por una marca que indique si un nodo fue eliminado o no. Esta estrategia es conocida como eliminación perezosa (lazy deletion).
Arboles AVL
Definición: un árbol balanceado es un árbol que garantiza costos de búsqueda, inserción y eliminación en tiempo O(log(n)) incluso en el peor caso.
Un árbol AVL (Adelson-Velskii y Landis) es una árbol de búsqueda binaria que asegura un costo O(log(n)) en las operaciones de búsqueda, inserción y eliminación, es decir, posee una condición de balance.
La condición de balance es: un árbol es AVL si para todo nodo interno la diferencia de altura de sus 2 árboles hijos es menor o igual que 1.
Por ejemplo: (el número dentro de cada nodo indica su altura)
Problema: para una altura h dada, ¿cuál es el árbol AVL con mínimo número de nodos que alcanza esa altura?. Nótese que en dicho árbol AVL la diferencia de altura de sus hijos en todos los nodos tiene que ser 1 (demostrar por contradicción). Por lo tanto, si Ah representa al árbol AVL de altura h con mínimo número de nodos, entonces sus hijos deben ser Ah-1 y Ah-2.
En la siguiente tabla nh representa el número de nodos externos del árbol AVL con mínimo número de nodos internos.
h | Ah | nh | ||||||||
0 | | 1 | ||||||||
1 | | 2 | ||||||||
2 | | 3 | ||||||||
3 | | 5 | ||||||||
4 | | 8 | ||||||||
5 | | 13 | ||||||||
Por inspección: (Fh representa los números de Fibonacci)
Por lo tanto, la altura de un árbol AVL es Esto implica automáticamente que la búsqueda en un AVL tiene costo de 
en el peor caso.
Inserción en un AVL
La inserción en un AVL se realiza de la misma forma que en un ABB, con la salvedad que hay que modificar la información de la altura de los nodos que se encuentran en el camino entre el nodo insertado y la raíz del árbol. El problema potencial que se puede producir después de una inserción es que el árbol con el nuevo nodo no sea AVL:
En el ejemplo de la figura, la condición de balance se pierde al insertar el número 3 en el árbol, por lo que es necesario restaurar de alguna forma dicha condición. Esto siempre es posible de hacer a través de una modificación simple en el árbol, conocida como rotación.
Suponga que después de la inserción de un elemento X el nodo desbalanceado más profundo en el árbol es N. Esto quiere decir que la diferencia de altura entre los dos hijos de N tiene que ser 2, puesto que antes de la inserción el árbol estaba balanceado. La violación del balance pudo ser ocasionada por alguno de los siguientes casos:
El elemento X fue insertado en el subárbol izquierdo del hijo izquierdo de N.
El elemento X fue insertado en el subárbol derecho del hijo izquierdo de N.
El elemento X fue insertado en el subárbol izquierdo del hijo derecho de N.
El elemento X fue insertado en el subárbol derecho del hijo derecho de N.
Dado que el primer y último caso son simétricos, asi como el segundo y el tercero, sólo hay que preocuparse de dos casos principales: una inserción "hacia afuera" con respecto a N (primer y último caso) o una inserción "hacia adentro" con respecto a N (segundo y tercer caso).
Rotación simple
El desbalance por inserción "hacia afuera" con respecto a N se soluciona con una rotación simple.
La figura muestra la situación antes y después de la rotación simple, y ejemplifica el cuarto caso anteriormente descrito, es decir, el elemento X fue insertado en E, y b corresponde al nodo N. Antes de la inserción, la altura de N es la altura de C+1. Idealmente, para recuperar la condición de balance se necesitaria bajar A en un nivel y subir E en un nivel, lo cual se logra cambiando las referencias derecha de b e izquierda de d, quedando este último como nueva raíz del árbol, N'. Nótese que ahora el nuevo árbol tiene la misma altura que antes de insertar el elemento, C+1, lo cual implica que no puede haber nodos desbalanceados más arriba en el árbol, por lo que es necesaria una sola rotación simple para devolver la condición de balance al árbol. Nótese también que el árbol sigue cumpliendo con la propiedad de ser ABB.
Rotación doble
Claramente un desbalance producido por una inserción "hacia adentro" con respecto a N no es solucionado con una rotación simple, dado que ahora es C quien produce el desbalance y como se vio anteriormente este subárbol mantiene su posición relativa con una rotación simple.
Para el caso de la figura (tercer caso), la altura de N antes de la inserción era G+1. Para recuperar el balance del árbol es necesario subir C y E y bajar A, lo cual se logra realizando dos rotaciones simples: la primera entre d y f, y la segunda entre d, ya rotado, y b, obteniéndose el resultado de la figura. A este proceso de dos rotaciones simples se le conoce como rotación doble, y como la altura del nuevo árbol N' es la misma que antes de la inserción del elemento, ningún elemento hacia arriba del árbol queda desbalanceado, por lo que solo es necesaria una rotación doble para recuperar el balance del árbol después de la inserción. Nótese que el nuevo árbol cumple con la propiedad de ser ABB después de la rotación doble.
Eliminación en un AVL
La eliminación en árbol AVL se realiza de manera análoga a un ABB, pero también es necesario verificar que la condición de balance se mantenga una vez eliminado el elemento. En caso que dicha condición se pierda, será necesario realizar una rotación simple o doble dependiendo del caso, pero es posible que se requiera más de una rotación para reestablecer el balance del árbol.
Arboles 2-3
Los árboles 2-3 son árboles cuyos nodos internos pueden contener hasta 2 elementos (todos los árboles vistos con anterioridad pueden contener sólo un elemento por nodo), y por lo tanto un nodo interno puede tener 2 o 3 hijos, dependiendo de cuántos elementos posea el nodo. De este modo, un nodo de un árbol 2-3 puede tener una de las siguientes formas:
Un árbol 2-3 puede ser simulado utilizando árboles binarios:
Una propiedad de los árboles 2-3 es que todas las hojas están a la misma profundidad, es decir, los árboles 2-3 son árboles perfectamente balanceados. La siguiente figura muestra un ejemplo de un árbol 2-3:
Nótese que se sigue cumpliendo la propiedad de los árboles binarios: nodos internos + 1 = nodos externos. Dado que el árbol 2-3 es perfectamente balanceado, la altura de éste esta acotada por:
Inserción en un árbol 2-3
Para insertar un elemento X en un árbol 2-3 se realiza una búsqueda infructuosa y se inserta dicho elemento en el último nodo visitado durante la búsqueda, lo cual implica manejar dos casos distintos:
Si el nodo donde se inserta X tenía una sola llave (dos hijos), ahora queda con dos llaves (tres hijos).
Si el nodo donde se inserta X tenía dos llaves (tres hijos), queda transitoriamente con tres llaves (cuatro hijos) y se dice que está saturado (overflow).
El problema se resuelve a nivel de X y Z, pero es posible que el nodo que contiene a Y ahora este saturado. En este caso, se repite el mismo prodecimiento anterior un nivel más arriba. Finalmente, si la raíz es el nodo saturado, éste se divide y se crea una nueva raíz un nivel más arriba. Esto implica que los árboles 2-3 crecen "hacia arriba".
Ejemplos de inserción en árboles 2-3:
Eliminación en un árbol 2-3
Sin perder generalidad se supondrá que el elemento a eliminar, Z, se encuentra en el nivel más bajo del árbol. Si esto no es así, entonces el sucesor y el predecesor de Z se encuentran necesariamente en el nivel más bajo (¿por qué?); en este caso basta con borrar uno de ellos y luego escribir su valor sobre el almacenado en Z. La eliminación también presenta dos posibles casos:
El nodo donde se encuentra Z contiene dos elementos. En este caso se elimina Z y el nodo queda con un solo elemento.
El nodo donde se encuentra Z contiene un solo elemento. En este caso al eliminar el elemento Z el nodo queda sin elementos (underflow). Si el nodo hermano posee dos elementos, se le quita uno y se inserta en el nodo con underflow.
Si el nodo hermano contiene solo una llave, se le quita un elemento al padre y se inserta en el nodo con underflow.
| Página siguiente |