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.