Download Arboles MultiCaminos

Arboles MultiCaminos
Ana Lilia Laureano Cruces
UAM-A
Caracteristicas y
propiedades de los árboles
Todo árbol que no es vacío, tiene un
único nodo raíz
Un nodo X es descendiente directo
de un nodo Y, si el nodo X, es
apuntado por el nodo Y. X es hijo de
Y.
Un nodo X es antecesor directo de un
nodo Y, si el nodo X apunta al nodo
Y. X es padre de Y.
Todos los nodos descendientes directos de
un nodo (padre) son hermanos.
Todo nodo sin ramificaciones se le conoce
como terminal u hoja.
Todo nodo que no cumple la característica
anterior se le conoce como interior.
Grado es el número de descendientes
directos de un determinado nodo. Grado
del árbol es máximo grado de todos los
nodos del árbol.
Nivel es el número de arcos que
deben ser reconocidos para llegar a
un determinado nodo. Por definición
la raíz tiene nivel I.
Altura del árbol es el máximo número
de niveles de todos los nodos del
árbol
Las variantes de árboles binarios
fueron desarrollados para funcionar
en:
Memoria principal
Volumen de información:
Necesario almacenarlos en memoria
secundaria
Organizados en archivo
Tiempo de acceso de memoria
principal es de microsegundos
Tiempo de acceso a memoria
secundaria para accesar una página
(contiene varios registros) es de
milisegundos.
Ejemplo; alamacenar un
árbol binario en disco
El tiempo promedio para localizar
alguno de los nodos es de logd n
accesos a disco, donde:
n: número de nodos del árbol
d: el orden del mismo = 2.
Si el árbol contiene 1,000,000 de
elementos. Se necesitarían
aproximadamente 20 accesos a
disco.
En el caso de que el árbol este
organizado en páginas, donde:
Cada página contiene 100 elementos
como mínimo.
Se necesitan como máximo 3 accesos a
disco. (Log 100 1,000,000).
Los accesos disminuyen de forma
considerable.
Arboles - B
Son una generalización de los
árboles balanceados
Representan una búsqueda externa,
utilizando árboles multicaminos.
Bayer y McCreight en 1970.
Descripción
Cada nodo (página) de orden d:
Contiene 2d claves como máximoy
d claves como mínimo
Con la anterior descripción se
garantiza que cada página este llena
como mínimo hasta la mitad.
Arbol -B de orden 2
Respecto al número de
descendientes cada página de un
árbol -B de orden d tiene 2d+1 hijos
como máximo y d+1 hijos como
mínimo.
Excepto la página raiz que puede
tener como mínimo 1 clave y por
consiguiente solamente 2 hijos.
Las páginas son páginas en general
son almacenadas en dispositivos de
almacenamiento secundario, a
excepción de la página raíz a quien
conviene tenerla en memoria principal
Arbol -B de orden d
Con d claves y d+1 hijos
C1
C2
C3
C3
C4
……….
Cn Cd
Definición de un Arbol -B
Cada página excepto la raíz, contiene
entre d y 2d elementos (d es el grado del
árbol).
Cada página, excepto la página raíz y las
páginas hoja, tiene entre d+1 y 2d+1
descendientes.
Se utiliza m para expresar el número de
elementos por página.
La página raíz cuenta con al menos 2
descendientes.
Las páginas hojas están todas al mismo
nivel.
66
29 55
15 19 22 26
35 41 58 62
75 87 94
69 73 77 81
89 93
96 98 99
1.
2.
3.
4.
5.
Orden del árbol: 2
Altura del árbol: 3
Todas las páginas contienen: 2(d),3(d+1) o 4(2d+1) elementos;
excepto la raíz (1)
Los elementos dentro del árbol se encuentran ordenados
en forma creciente (izq. a der.)
Todas las hojas están al mismo nivel
Inserción en un Arbol-B
Todas las hojas están al mismo nivel
Cualquier camino desde la raíz hasta a
alguna de las hojas tiene la misma
longitud.
Crecen de abajo hacia arriba (desde
las hojas hacia la raíz).
Busqueda en árboles -B
1. Debe tenerse en memoria la
página sobre la cual vamos a trabajar.
SI pag ≠ NIL
ENTONCES
– Se avanza hacia el paso 2
SI_NO
– Se avanza hacia el paso 3
FIN_SI
2. Debe verificarse si la clave buscada se
encuentra en dicha página. Si m es
pequeña se utiliza búsqueda secuencial,
de otra forma se puede utilizar búsqueda
binaria.
SI la clave Se encuentra en la Pag.
ENTONCES
exito = true
SI_NO
Deben distinguirse los siguientes casos *
FIN_SI
Casos *
CASO (x)
< CL1:
Debe localizarse Pag. 0
CLi< AND > CLm:
Debe localizarse Pag. i
> CLm:
Debe localizarse Pag. m
FIN_CASO
Regresar al paso 1
3. FRACASO, la página que se desea
localizar es igual a NIL y por lo tanto
la clave no se encuentra en el árbol.
Arboles B +
Se han convertido en la técnica más
utilizada para la organización de
archivos indizados. La principal
característica de estos árboes es que
todas las claves se encuentran en las
hojas y por lo tanto cualquier camino
desde la raíz hasta alguna de las
claves tienen la misma longitud.
Arbol B + de orden 2
Respecto al número de
descendientes cada página de un
árbol -B de orden d tiene 2d+1 hijos
como máximo y d+1 hijos como
mínimo.
55 77
37 48
55 61 73
77 80 87 92
Es de notar que los árboles B+
ocupan un poco más de espacio que
los érboles -B, y esto ocurre al existir
duplicidad en algunas claves. Sin
embargo, esto es acpetable si el
archivo se modifica frecuentemente,
puesto que se evita la operación de
reorganización del árbol que es tan
costosa en los árboles -B.
Definición del árbol B+
1. Cada página excepto la raíz, contiene entre d y
2d elementos
2. Cada página excepto la raíz, contiene entre d+1
y 2d+1 descendientes. Se utiliza m para
expresar el número de elementos pro página.
3. La página raíz al menos tiene dos elementos
4. Las páginas hojas están todas al mismo nivel
5. Todas las claves se encuentran en las páginas
hojas
6. Las claves de las páginas raíz e interiores se
utilzan como índices
Búsqueda en árboles B+
El proceso debe contemplar que al
buscar una determinada clave la
misma se encuentra en una página
raíz o interior, en dicho caso no debe
detenerse el proceso, sino que debe
continuarse la búsqueda con la
página apuntada por la rama derecha
de dicha clave.
Inserción en árboles B+
La inserción es similar a la del árbol B. La dificultad se encuentra cuando
se desea insertar en una página llena
(m = 2d). La página:
Se divide en dos, distribuyendose las
m+1 claves de la siguiente forma:
Las d primeras claves en la página de la izq.
Las d+1 en la página de la der.
Una copia de la clave del medio sube a la
página antecesora
Ejemplo…
25
10 15 17 21
25 27 29 31
15 25
10 13
15 17 21
25 27 29 31
Importante notar que el
desbordamiento en una página que
no es hoja no produce duplicidad de
claves. El proceso de propagación
puede llegar hasta la raíz, en cuyo
caso la altura del árbol puede
incrementarse en una unidad.
Fin…