OPERACIONES CON ARBOLES

 

procedimiento PREORDEN (n:nodo;A:arbol);

var c:nodo fvar

escribir(ELEMENTO(n,A))

c:=HIJO_MAS_IZQ(n,A);

mientras c<>� (* vacio *) hacer

PREORDEN(c,A)

c:=HEMANO_DER(c,A)

fmientras

fprocedimiento

 

procedimiento INORDEN (n:nodo;A:arbol)

var c:nodo fvar

c:=HIJO_MAS_IZQ(n,A);

si c=� entonces escribir (ELEMENTO(n,A))

sino INORDEN (c,A);

escribir (ELEMENTO(n,A))

c:=HERMANO_DER(c,A);

mientras c<>� hacer INORDEN(c,A);

c:=HERMANO_DER(c,A)

fmientras

fsi

fprocedimiento

 

funcion HERMANO_DER (n:nodo;A:arbol):nodo

var i,padre:nodo; Arbol

encontrado:booleano <=== implementado con

fvar un VECTOR

padre:=A[n];

i:=n+1; encontrado=falso;

mientras (i<=maxnodos) AND no(encontrado) hacer

si A[i]=padre entonces encontrado:=cierto

sino i:=i+1

fsi

fmientras

si encontrado entonces devolver i

sino devolver � (* vacio *)

fsi

ffuncion

 

REPRESENTACION DE ARBOLES

- VECTORES:

TYPE

nodo=integer

arbol=array [1..maxnodos] de nodo

elem=array [1..maxnodos] de elementos

 

1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	5	5	5	3	3
a	b	c	d	e	f	g	h	i	j

 

- LISTAS DE HOJAS:

TYPE

lista=^nodo

nodo=registro

hijo:entero;

sig:lista

fregistros

arbol=registro

hijos:array [1..maxnodos] de lista

elem:array [1..maxnodos] de elementos

raiz:entero

fregistro

 

- HIJO MAS A LA IZQ - HERMANO DERECHO:

TYPE

nodo=registro

hijo_izq:direccion;

elem:elemento;

hijo_der:direccion;

padre:direccion; (* <--- opcional *)

fregistro

 

Con Punteros.

direccion=^nodo

arbol=direccion (* raiz *)

Con Vectores:

direccion=entero

arbol=direccion (* raiz *)

nodos=array [1..maxnodos] de nodo

- La función CREAI recibe como entradas un elemento y varios arboles y devuelve a la salida un arbol que tiene como raiz el elemento dado y cuyos hijos son las raices de los arboles pasados.

El funcionamiento del algoritmos es el siguiente:

1.- Crear el nodo raiz y rellenarlo

2.- Introducir v en el nodo raiz

3.- Asignarle RAIZ(A[1]) como hijo_izq, es decir, su hijo izquierdo es la raiz del primer arbol dado.

4.- Para cada nodo raiz de A[k] su hermano derecho es A[k+1].

 

CREAI (v,A₁,....,Ai)

 

funcion CREAI (v:elemento; A:array [1..i] de arboles):nodo

var

temp:arbol

i,j:entero

fvar

CREAR (temp);

temp^.elem:=v;

temp^.hijo_izq:=A[1];

temp^.hijo_der:=�;

{ temp^.padre:=�; } (* <--- depende de la implementacion del arbol *)

para j:=1 hasta i-1 hacer

A[j]^.hermano_der:=A[j+1];

{ A[j]^.padre:=temp; } (* <--- dependiendo de la implem. *)

fpara

{A[i]^.padre:=temp }

devolver temp

ffuncion

OPERACIONES CON TABLAS (HASH)

 

Implementación de TABLAS HASH:

TYPE

lista=^nodo;

nodo=registro

elem:elemento;

sig:lista

finregistro

HASH=array [1..maxelems] de nodo;

 

procedimiento AÑADIR(x:elemento;HASH1:HASH);Con Hashing Cerrado

var

i,j:entero; enc:booleano;

fvar

i:=0; enc:=falso;

mientras (i<=m-1) AND no(enc) hacer

j:=h_da(x,i);

si Libre(HASH1[j]) OR (HASH1[j]=x) entonces

enc:=cierto;

si Libre(HASH1[j]) entonces HASH1[j]:=x fsi

sino

i:=i+1;

fsi

fmientras

si no(enc) entonces escribir ('Error Tabla Llena') fsi

fprocedimiento

 

2.3.2 Prueba cuadrática

h_da(x,i)=( h(x)+C1*1+C2*i²) mod m

 

2.3.3 Doble Hashing

h_da(x,i)=( h(x)+i*h'(x) ) mod m

h(x)=x mod m

h'(x)=1 + (x mod m') siendo m'<m

 

2.4 Conclusiones

- Encadenamiento Separado (HASHING ABIERTO) : Las variables se duplican por lo que ocupan mucho espacio, además de tener que gestionar todas esas variables dinámicas. La ventaja es que permite aumentar el tamaño de la HASH y añadir elementos aunque esta esté llena.

- Direccionamiento Abierto (HASHING CERRADO) : Las eliminaciones son complicadas y una vez llena la tabla no se pueden añadir más elementos, pero ocupa poco espacio en memoria.

 

* La estructura de tabla HASH es la más eficiente para resolver el problema de los diccionarios, pues solo emplea las operaciones de AÑADIR, ELIMINAR y PERTENENCIA.

Su principal inconveniente es que se trata de una estructura estática fija y al implementar cualquier otra operación el coste es muy elevado.

 

OPERACIONES CON HEAPS (MONTICULOS)

 

TYPE

HEAP: array [1..maxnodo] of elements

VAR

HEAP1:HEAP;

tam_heap:integer;

 

procedimiento HEAPIFY(HEAP1:Heap;tam_heap,i:entero);

var

izq,der,min:entero

fvar

izq:=HIJO_IZQ(i); (* 2i *)

der:=HIJO_DER(i); (* 2i+1 *)

min:=i;

si (izq<=tam_heap) AND (HEAP1[izq]<HEAP1[i]) entonces

min:=izq

fsi

si (der<=tam_heap) AND (HEAP1[der]<HEAP1[min]) entonces

min:=der

fsi

si min<>i entonces intercambiar(HEAP1[min],HEAP1[i])

�HEAPIFY(HEAP1,tam_heap_min)

fsi

fprocedimiento

procedimiento AÑADIR(HEAP1:HEAP;tam_heap:entero;x:elemento)

var

i:entero

fvar

si tam_heap=maxnodos entonces escribir ('Error Heap lleno.')

sino tam_heap:=tam_heap+1

HEAP1[tam_heap]:=x

i:=tam_heap

mientras (i>1) AND (HEAP1[padre(i)]>x) hacer

intercambiar (HEAP1[padre(i)],HEAP1[i])

i::=PADRE(i)

fmientras

fsi

fprocedimiento

 

Atención: Estudiar las operaciones MINIMO, ELIMINAR_MIN y AÑADIR en la estructura de HEAPS.

 

Con esta representación es sencillo obtener:

Padre(i)=i div 2

Hijo_izq (i)= 2i

Hijo_der (i)= 2i+1

 

Conclusiones:

- Inconvenientes: las operaciones PERTENECE y ELIMINAR las realiza en O(n) ya que debe recorrer todo el HEAP.

- Se trata de una estructura estática en la cual se debe conocer el tamaño del vector que la almacena.

OPERACIONES CON ARBOLES BINARIOS DE BUSQUEDA

 

TYPE

ABB=^nodo

nodo=registro

padre,hijo_izq,hijo_der:^nodo

elem:elemento

fregistro

 

funcion PERTENECE (ABB1:ABB;x:elemento):booleano

var p:^nodo fvar

p:=ABB1;

mientras (p<>NIL) AND (p^.elem<>x) hacer

si x<p^.elem entonces

p:=p^.hijo_izq (* HIJO_IZQ(p) *)

sino p:=p.hijo.der

fsi

fmientras

devolver (p^.elem=x)

ffuncion

 

Esta función tiene un coste O(h), donde h es la altura del arbol binario.

 

OPERACIONES CON ARBOLES 2-3.

 

PERTENECE

1. Se accede a la raiz.

2. Se compara el elemento con las claves del nodo:

2.1. Si x<clave₁ pasamos al nodo del primer subarbol.

2.2. Si clave₁<x<clave₂ pasamos al segundo subarbol.

2.3. Si x>clave₂ pasamos al tercer subarbol.

3. Repetición del punto 2 hasta que:

4.1. x=clave -----> devuelve CIERTO

4.2. x>elemento que está en la hoja -----> devuelve FALSO

 

MINIMO Y MAXIMO

Para obtener el MINIMO iremos al primer subarbol del nodo, sucesivamente hasta llegar a la hoja, que será el mínimo del arbol.

Para obtener el MAXIMO iremos al subarbol más a la derecha hasta llegar a la hoja, que será el máximo del arbol.

 

AÑADIR

a) Localizar el nodo interno del que va a "colgar" el elemento a añadir, si encontramos el elemento en la busqueda del nodo no habrá que añadirlo).

b) Inserción del elemento.

b.1) Si el nodo interno tiene 2 hijos introducimos el elemento en el tercer hijo y actualizamos las claves del nodo interno (las demas claves del arbol no se ven afectadas).

b.2) Si el nodo interno tiene 3 hijos dividimos ese nodo en otros dos nodos con 2 hijos cada uno (al haber añadido el elemento) y actualizamos las claves del padre del nodo dividido. Si el padre del nodo interno ya tenía 3 hijos debemos aplicar el paso b.2) en forma recursiva hasta solucionar el problema. NOTA: Si es necesario se ampliará un nivel el arbol y se añadirá otra raiz.

ELIMINAR

a) localizar el nodo interno del que "cuelga" el elemento a eliminar. [Coste de esta operación pertenece a O(log n)]

b) Eliminar elemento:

b.1) Si el nodo tiene 3 hijos se elimina la hoja y se modifican las claves del nodo interno. [Coste pertenece a O(1)]

b.2.1) Si el nodo tiene 2 hijos:

+ borra la hoja que contiene el elemento.

+ busca un hermano adyacente que tenga 3 hojas y trae la menor a este nodo (con lo cual ambos pasan a tener 2 hojas ). Luego se actualizan las claves del nodo, el hermano y el padre.

b.2.2) Si no existe ese hermano con 3 hojas se fusiona el nodo interno con el hermano adyacente y se actualizan las claves del hermano y del padre. Este paso se repite hasta hallar un hermano con 2 hijos. [ Coste de la operación pertenece a O(log n)]

 

REPRESENTACION DE ARBOLES 2-3

Se representará mediante una estructura enlazada, que incluirá un registro de dos tipos, dependiendo de si se trata de un nodo interno o de una hoja, es decir, trabajaremos con registros de campos variables.

Si se trata de un nodo interno el registro tendrá 2 campos para las claves y 3 campo apuntando a los hijos.

Si se trata de una hoja el registro tendrá un solo campo que contendrá al elemento. El paso de un nodo a otro será mediante punteros.

Esta estructura asegura que todas las operaciones se realizarán con un coste perteneciente a O(log n), el inconveniente es que en cada operación de AÑADIR y ELIMINAR hay que volver a equilibrar el arbol 2-3.

OPERACIONES CON B-ARBOLES

 

G M P X

 

 

A C D E

J K

N O

R S T U V

Y Z

 

- Cada nodo i tine n_i claves, que son los elementos del nodo y si se trata de un nodo interno tiene ademas n_i+1 hijos apuntados con punteros.

- Todas las hojas están a igual distancia de la raiz.

- Las claves de un nodo separan los rangos de las claves �de cada uno de los subarboles.

- El número de claves (y de hijos-1) que puede tener un nodo está comprendido entre t-1 y �2t-1, siendo t=grado mínimo del arbol. A excepción de la raiz que puede tener un mínimo de 1 clave.

En el ejemplo tendríamos:

t=3 t-1=2 2t-1=5

Cada nodo puede tener como mínimo 2 claves y 3 hijos y como máximo 5 claves y 6 hijos, lo cual se cumplía en el ejemplo.

 

PERTENECE

Coste perteneciente a O(t • log_t n).

a) Tomamos el elemento.

b) Comparamos con las claves del nodo hasta hallar una mayor que él.

c) Vamos al subarbol apuntado entre esa clave y la anterior.

clave_x-1 < elemento < clave_x

Si elemento=clave_x devuelve CIERTO y sal del algoritmo.

d) Vuelve al paso b) esta vez con el nodo del subarbol elegido.

 

MíNIMO Y MÁXIMO

Coste perteneciente a ( log_t n ).

Mínimo : bajamos por el primer puntero de cada nodo, es decir al hijo izquierdo, hasta llegar a una hoja, cuyo elemento izquierdo es el mínimo del arbol.

Máximo : bajamos por el último puntero de cada nodo, es decir, por el hijo más a la derecha, hasta llegar a una hoja, cuyo elemento más a la derecha es el máximo del arbol.

AÑADIR

 

+ Los elementos se añaden en las hojas, luego primero hay que llegar hasta ellas.

a) Mediante comparación de claves vamos bajando por los subarboles correspondientes, hasta llegar a la hoja.

b) Si durante el camino encontramos un nodo lleno, es decir, con 2t-1 hijos, lo dividimos en dos nodos y pasamos el elemento central a las claves de su padre. De esta forma cada nodo tendré t-1 elementos.

c) Volvemos al paso a).

 

ELIMINAR

 

a) Buscamos el nodo en el cual se halla el elemento:

Si el nodo está en una hoja se elimina directamente.

Si se trata de un nodo interno:

b.1.) Si el hijo izquierdo c_k (derecho c_k+1) tiene al menos t claves: sustituimos el elemento por su predecesor, máximo del subarbol anterior, (o sucesor, minimo del arbol siguiente). Luego borramos su predecesor (o sucesor) de su antigua posición de forma recursiva mediante este mismo procedimiento.

b.2) Si los dos hijos del nodo i, c_k y c_k+1, tienen t-1 claves (que es el mínimo n� de claves): fundimos los dos nodos en uno solo y luego bajamos el elemento a borrar en medio de ese nuevo nodo, con esto el nodo que lo contenía pierde un nodo y un hijo. Luego aplicamos el procedimiento de forma recursiva a partir de c_k.

 

REPRESENTACION DE B-ARBOLES

 

Se utiliza una estructura enlazada, es decir, nodos con punteros:

TYPE

nodo: registro

n: n� de claves;

claves: array [1..2t-1] de elementos

punteros: array [1..2t] de nodo

fregistro;

 

+ El uso de B-Arboles es util cuando el n� de claves de cada nodo es del orden de los elementos que caben en una página de memoria, es decir, cuando hay un puñao de elementos en el arbol.

OPERACIONES CON MF-SETS

 

Partiendo inicialmente de un conjunto conocido y fijo de n elementos, dividido en varios subconjuntos (identificados por el elemento de su raiz), sobre él se realizarán las operaciones de COMBINAR (une dos subconjuntos) y BUSCAR (devuelve el subconj. en el que se encuentra el elemento, es decir, el identificador de dicho subconj.).

La implementación será con nodos con un puntero a su padre.

Inicialmente el conjunto está particionado en n subconjuntos.

Inicio: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

 

OPERACION COMBINAR

A la hora de COMBINAR dos subarboles, la raiz del arbol de menor altura pasa a colgar de la raiz del arbol de mayor altura, esto implica que la altura máxima de cualquier arbol será lg₂ n.

Coste (COMBINAR) (1)

El coste de averiguar la altura del arbol sería lg₂ n, pero eso no será así ya que guardaremos la altura de cada arbol en el nodo raiz.

 

Combinar(1,2): [1] [3] [5] [7] [8] [9] [10]

Combinar(3,4):

Combinar(5,6): [2] [4] [6]

 

Combinar(1,3): [1]

[2] [3]

�

[4]

OPERACION BUSCAR

 

A partir del nodo que contiene al elemento se sube por el arbol hasta llegar a la raiz (a traves del puntero al padre). Devolveremos el valor del elemento que esta en la raiz.

 

Coste (BUSCAR) (lg₂ n)

 

Buscar(4): 1

Buscar(6): 5

etc...