MULTIWAY TREES
LUIS MATEO HINCAPIÉ MARTÍNEZ
1038417207
UDEA
2019
Introducción
Cuando buscamos información en un medio externo resulta poco
eficiente estar accediendo varias veces al disco, para
solucionar este problema podemos usar un árbol binario que
contenga un índice en el que tengamos las claves de acceso y
las posiciones en el disco.
Sin embargo hay alternativas más eficaces para realizar este
índice, pues a medida que ingresamos datos al árbol binario
este incrementa de altura rápidamente.
Introducción
Si suponemos que por cada nodo del árbol binario accederemos al disco para
realizar una búsqueda, antes de encontrar el nodo realizaremos lg N accesos.
Para reducir estos accesos podemos dividir el árbol en páginas de 7 nodos. De
esta forma el nuevo árbol de páginas sería un árbol donde la raíz tendria 8
hijos.
Árboles m-way (multiway trees)
Los árboles m-way son árboles multidireccionales que son
versiones generalizadas de árboles binarios donde cada nodo
contiene múltiples elementos. En un árbol m-Way de orden m,
cada nodo contiene un máximo de m - 1 elementos y m hijos.
En otras palabras todos los nodos son del grado <= M (donde
M es su orden).
Si T es un Arbol de Busqueda de M-way y está vacio :
● T tiene el valor de un apuntador nulo
Propiedades
Si T es un Arbol de Busqueda de M-way y no está vacío:
T tiene el valor de un apuntador a un nodo del tipo:
n, A0, (k1, A1), (k2 ,A2) ..., (kn ,An) donde :
● n, igual o menor a M - 1, es el número de claves que tiene el nodo
● ki debe ser menor que ki+1
● Todos los valores de clave del subárbol Ai deben ser menores que el valor de clave ki+1
para i variando de 0 a n-1
● Todos los valores de clave en el subárbol An son mayores que el valor de clave kn
● Los subárboles de T, apuntados por Ai, i variando de 0 a n, son también Arboles de
Busqueda de M-way
Ejemplo
T -----+
|
V (a)
*--------------------------*
| 2, b, (20,c), (40,d) |
*--------------------------*
| | |
| | |
| | |
+-----------------------------------------+ | +-----------------------------------------+
| | |
| | |
V (b) V (c) V (d)
*--------------------------* *--------------------------* *--------------------------*
| 2, 0, (10,¬), (15,¬) | | 2, 0, (25,¬), (30,e) | | 2, 0, (45,¬), (50,¬) |
*--------------------------* *--------------------------* *--------------------------*
|
|
|
+-----------------------------------------+
|
|
V (e)
*------------------------*
| 1, 0, (35,¬) , (¬,¬) |
*------------------------*
Algoritmo
Secuencia de Búsqueda del Registro cuya Clave es de valor 35 en el Árbol de Búsqueda de 3-way
● nodo_padre
● nodo_actual
● mientras ( !nodo_actual.equals(nodo_nulo) )
● {
● // Recupero el Nodo
● // Busco en el Nodo
● // Clave No Hallada
● // Nodo Actual a Nodo Padre
● // Identifico el nodo posible
● // Nodo Posible a Nodo Actual
● // Clave Hallada
● // Recupero Registro
● }
Algoritmo
Secuencia de búsqueda del registro cuya clave es de valor 35 en el Árbol de búsqueda 3-way
Determino Nodo Raiz
Recupero el Nodo (a)
Busco en el Nodo (a)
Determino seguir en (c)
Recupero el Nodo (c)
Busco en el Nodo (c)
Determino seguir en (e)
Recupero el Nodo (e)
Busco en el Nodo (e)
Encuentro la Clave en el Nodo(e)
Recupero el Registro (w)
Observaciones
Los árboles de búsqueda m-way son índices densos, ya que
todas las claves están en el índice
El máximo número de accesos a disco en un árbol de búsqueda
m-way para hallar una clave es igual a la altura del árbol
Minimizar el número de accesos a disco en un árbol de
búsqueda m-way es equivalente a minimizar la altura del
árbol
