Embed Size (px)
Citation preview
Árbol BEstructura de Datos en memoria secundaria
Introducción Para almacenar muchos datos disco, es
necesario una estructura de datos eficiente. Los accesos al disco son costosos en tiempo
por lo que se debe evitar realizar muchos accesos a los datos.
AVL es la mejor estructura para memoria principal, pero es ineficiente si se utiliza para almacenamiento secundario. Esto se debe a la cantidad de accesos necesarios para efectuar las rotaciones. Otro problema es que se requieren tantos accesos como niveles se recorran en el árbol para efectuar la búsqueda.
Árboles B Bayer y McCreight propusieron en 1970 esta
estructura. Manejan árboles de búsqueda multicamino,
cuyos nodos guardan más de un elemento. Son árboles 100% balanceados en su
estructura, lo cual repercute en búsquedas eficientes y en accesos mínimos a disco.
10 20
5 8
12 18
25 65 92 99
Características del Árbol B Un Árbol B de orden n es aquel que:
Todas las hojas del árbol están en el nivel inferior.
Cada nodo contiene entre nn y 2n2n elementos, excepto el nodo raíz, que puede tener entre 1 y 2n2n elementos.
Si un nodo tiene ‘mm’ elementos, el nodo siempre contendrá m + 1m + 1 hijos si no es un nodo hoja.
Ejemplo.... Para un Árbol B de orden 3:
Cuántos elementos máximo puede guardar cada nodo del árbol?66
¿Cuántos elementos mínimo puede guardar cada nodo del árbol?11 si el la raíz, , 33 cualquier otro nodo..
¿Cuántos hijos máximo puede tener un nodo?77
¿Cuántos hijos mínimo puede tener un nodo?00 si es hoja, 22 si es raíz, 4 cualquier otro nodo.
Más características del Árbol B
Un árbol B de orden nn es aquél en que: Los elementos de un nodo están ordenados
linealmente.
Los elementos están organizados de tal forma que se cumple la regla de la búsqueda: a la izquierda menores, a la derecha mayores.
10 20
5 8
12 18
25 65 92 99
Ejemplo... ¿De qué orden es este árbol B?
10 20
5 8
12 18
25 65 92 99
Este árbol es de orden 2 ya que
puede almacenar hasta 4 elementos
en cada nodo.
Proceso de Inserción Buscar el nodo hoja en donde se debería agregar
el elemento. Si hay espacio disponible en el nodo, agregar el
elemento y terminar. Si el nodo hoja NO tiene capacidad de almacenar el
elemento, se deberá crear un nuevo nodo al mismo nivel de la hoja y distribuir a los 2n+1 elementos de la siguiente forma: El nuevo nodo recibe a los ‘n’ elementos más grandes. El nodo existente se queda con los ‘n’ elementos más
pequeños. El elemento medio se insertará en el nodo padre
siguiendo la misma lógica de inserción. En caso de no haber nodo padre, se creará un nuevo nodo que pasará a ser la nueva raíz.
Ejemplo....10 20
5 8
12 18
25 65 92 99
Agregar el 4
10 20
4 5 8
12 18
25 65 92 99Si hay espacio para el
elemento, éste se agrega en el nodo.
Los elementos están acomodados de menor a
mayor.
Ejemplo...10 20
5 8
12 18
25 65 92 99
Agregar el 56
10 20 65
4 5 8
12 18 25 56
92 99
Cuando el nuevo elemento no cabe en el nodo, se agrega
otro nodo y se reparten los elementos.
Ejemplo...10 20 65
4 5 8
12 18 25 56
70 75 80 85
Agregar el 78
10 20 70
4 5 8
12 18 25 56 65
75 78 80 85
El árbol siempre se resiste a crecer, ya
que trata de distribuir los elementos en los nodos ya existentes.
Ejemplo10206590
4 5 8
1218 25565760
70758085Agregar el 66
10 20 65 90
4 5 8
12 18
25 56 57 60 66 70
80 85
751020
4 5 8
1218
25565760 6670
8085
65
7590
11 22
El árbol crece de abajo hacia arriba. Cuando el árbol aumenta de altura
sólo se agrega una nueva raíz.
9495
9495
9495
Proceso de Eliminación Buscar el elemento a borrar. Si el elemento a borrar está en una nodo
hoja, se borra y termina el proceso. Si el elemento a borrar no se encuentra
en una hoja, al igual que en un ABB, se buscará al sustituto más apropiado. El sustituto será: El último elemento de la hoja más derecha del
subárbol izquierdo del nodo actual (el mayor de los menores).
El primer elemento de la hoja más izquierda del subárbol derecho del nodo actual (el menor de los mayores).
Ejemplo...10 20 65
4 5 8
12 18 25 56
70 75 80 85
Eliminar el 8
10 20 65
4 5
12 18 25 56
70 75 80 85
Cuando el nodo tiene más
elementos que el mínimo, se da de
baja al elemento y termina el proceso.
Ejemplo...10 20 65
4 5 8
12 18 25 56
70 75 80 85
10 20 70
4 5 8
12 18 25 65
75 80 85
Eliminar el 56
Cuando el nodo tiene el mínimo
se toma un elemento de los
hermanos.
Ejemplo...10 20 65
4 5 8
12 18 25 56
70 75
Eliminar el 56
Cuando el nodo tiene el mínimo y los
hermanos también, se une el nodo con uno de sus hermanos y le
libera el nodo sobrante.
10 20
4 5 8
12 18 25 65 70 75
Ejemplo...1020
4 5 8
1218
25565760 6670
8085
65
7590
Eliminar el 65Utilizar el menor de los mayores
1020
4 5 8
1218
2556576070758085
66
90 10206690
4 5 8
1218
25565760
70758085
11 22
9395
9395 9395
Ejemplo...102060
4 5 8 1218
25565758 6670
8085
65
7590
Eliminar el 65Utilizar el menor de los mayores
102060
4 5 8
1218
2556575870758085
66
90
11 221020
4 5 8
1218
2556575870758085
60
6690
93956162
6162
9395
6162
9395
