Árboles B

Fundamentos de Organización de Datos
Árboles B
1
2
Árboles B y B+
Los árboles B son árboles multicamino con

una construcción especial de árboles que
permite mantenerlos balanceados a bajo
costo.
3 Propiedades de un Árbol B de orden M
●Cada nodo del árbol puede contener como máximo M
descendientes directos (hijos) y M-1 elementos.
●La raíz no posee descendientes directos o tiene al menos dos.
●Un nodo con X descendientes directos contiene X-1 elementos.
●Todos los nodos (salvo la raíz) tienen como mínimo [M/2] – 1
elementos y como máximo M-1 elementos.
●Todos los nodos terminales se encuentran al mismo nivel.
Declaración de tipos de datos
4
const M = … ; {orden del árbol}
type
nodo = record
cant_claves: integer;
claves: array[1..M-1] of <tipo_dato>;
hijos: array[1..M] of integer;
end;
arbol = file of nodo; 67
var
arbolB: arbol;
25 40 88 96 105
5 Ejemplo – Árbol B de orden 4
Árbol Inicial
Nodo 0 +40 , +96 , +25 , +67
40
25 96 96
40
Archivo:
cant_claves: 2
0
1
3
25
40 40
96 96
claves: 1 2 3
hijos: -1 -1 -1 -1
1 2 3 4
NRR 0
6 Overflow
➢ Se crea un nuevo nodo.

➢ La primera mitad de las claves se mantiene en el
nodo con overflow.
➢ La segunda mitad de las claves se traslada al
nuevo nodo.
➢ La menor de las claves de la segunda mitad se
promociona al nodo padre.
0
2
7 67
25 40 96 25 40 67 96
izq der
0 1
25 40 96 +67
División de la raíz. Se incrementa la altura del árbol.
Archivo:
claves: 25 40 cc: 2 96 cc: 1 67 cc: 1
1 2 3 1 2 3 1 2 3
hijos: -1 -1 -1 -1 -1 0 1
1 2 3 4 1 2 3 4 1 2 3 4
NRR 0 NRR 1 NRR 2

¡Notar la numeración de los nodos!
2
75 88 96 105
izq der
67
0 1
25 40 96
88 96 105
Overflow en el nodo 1. División del mismo

+88 , +105 , +75 y promoción de la clave 96.
2
75 80 88 91
izq der
67 96
0 1 3
25 40 75 88 91 105
Overflow en el nodo 1. División del mismo

+75 , +91 , +80 y promoción de la clave 88.
¿L/E necesarias para el alta de la
2 clave 80?
67 88 96
88 L2, L1, E1,E4,E2 (cada nodo
se lee a lo sumo 1 vez)
0 1 4 3
25 40 75 80 91 105
+80 Completamos el árbol con las altas de:

+86,+120,+230,+95,+55
Overflow en el nodo 1. División del mismo 70 75 80 86
11
y promoción de la clave 80. izq der
Propagación del overflow a la raíz. División de
la misma y aumento en la altura del árbol. 67 80 88 96
izq der
2 nueva raíz
67 88 96
0 1 4 3
25 40 55 75 80 86 91 95 105 120 230
+86 , +120 , +230 , +95 , +55 . Alta de +70

7
12 88
2 6
67 80 96
0 1 5 4 3
25 40 55 70 75 86 91 95 105 120 230
+70
Bajas 7
13
88
2 6
67 80 96
0 1 5 4 3
25 40 55 70 75 86 91 95 105 120 230
-75
14 Bajas
1. Si la clave a eliminar no está en una hoja, se debe

reemplazar con la menor clave del subárbol
derecho.
2. Si el nodo hoja contiene por lo menos el mínimo
número de claves, luego de la eliminación, no se
requiere ninguna acción adicional.
3. En caso contrario, se debe tratar el underflow
15 Bajas - Underflow
4. Primero se intenta redistribuir con un hermano

adyacente. La redistribución es un proceso mediante el
cual se trata de dejar cada nodo lo más equitativamente
cargado posible.
5. Si la redistribución no es posible, entonces se debe

fusionar con el hermano adyacente.
Políticas para la resolución de underflow:
1. Política izquierda: se intenta redistribuir con el hermano adyacente izquierdo, si no es
posible, se fusiona con hermano adyacente izquierdo.
2. Política derecha: se intenta redistribuir con el hermano adyacente derecho, si no es posible,
se fusiona con hermano adyacente derecho.
3. Política izquierda o derecha: se intenta redistribuir con el hermano adyacente izquierdo, si
no es posible, se intenta con el hermano adyacente derecho, si tampoco es posible, se
fusiona con hermano adyacente izquierdo.
4. Política derecha o izquierda: se intenta redistribuir con el hermano adyacente derecho, si
no es posible, se intenta con el hermano adyacente izquierdo, si tampoco es posible, se
fusiona con hermano adyacente derecho.
Políticas para la resolución de underflow:
Casos especiales: en cualquier política si se tratase de un nodo hoja de un

extremo del árbol debe intentarse redistribuir con el hermano adyacente que el
mismo posea.
Aclaración:
- En caso de underflow lo primero que se intenta SIEMPRE es redistribuir si el
hermano adyacente se encuentra en condiciones de hacer la redistribución y no
se produce underflow en el.
7
18 88 -75 , -88
-88 L/E: L7, L6,L4, E4,E7
2 6
67 80 96
0 1 5 4 3
25 40 55 70
70 75 86 91 95 105 120 230
Eliminación de la clave 75 en el nodo 1.
Baja del 88, se reemplaza la clave por la menor clave del subárbol derecho.
No se genera underflow en la hoja
Ejemplo política derecha o izquierda
19 7
91
2 6
67 80 96
0 1 5 4 3
25 40 55 70 86 95 105 120 230
-88 , -70
20
Baja de la clave 70 - política derecha o izquierda
La eliminación de la clave 70 en el nodo 1 produce

underflow.
Se intenta redistribuir con el hermano derecho. No es
posible ya que el nodo contiene la cantidad mínima de
claves.
Se intenta redistribuir con el hermano izquierdo. La
operación es posible y se rebalancea la carga entre los
nodos 1 y 0.
Ejemplo - política derecha o izquierda
21
7
91 25 40 55 67
izq der
2 6
67 80
55 96
0 1 5 4 3
25 40 55 70
67 86 95 105 230
120 120 230
-70 , -105 , -86

22 7
-86, no se puede balancear
91 con adyacente entonces se
fusiona el nodo en underflow
con su adyacente
2 6
55 80 96
0 0 1 1 5 4 4 3
25 40
25 40 67 67 80 86 9595 120 230
-86 , -230 , -95

23
● -95, no se puede balancear con
adyacente entonces se fusiona el
2 nodo 4 y el nodo 3
● Se propaga el underflow al nodo 6
55 91 ● Como el nodo 6 no puede
balancear con adyacente (nodo 2)
se fusionan y disminuye en 1 la
altura del árbol
0 1 4
25 40 67 80 96 120
-95
Ej: Redistribución en nodo interno
24
7
116
83
2 6
35 83 116
160
0 1 1 5 5 4 4 3
13
13 22
22 39 40
39 40 89 96 89
101 96
134101 160199
199
-134

Árboles B

Cargado por

Copyright:

Formatos disponibles

Árboles B

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Árboles B

Cargado por

Copyright:

Formatos disponibles

Fundamentos de Organización de Datos

Los árboles B son árboles multicamino con

➢ Se crea un nuevo nodo.

NRR 0 NRR 1 NRR 2

Overflow en el nodo 1. División del mismo

Overflow en el nodo 1. División del mismo

+80 Completamos el árbol con las altas de:

25 40 55 75 80 86 91 95 105 120 230

+86 , +120 , +230 , +95 , +55 . Alta de +70

25 40 55 70 75 86 91 95 105 120 230

25 40 55 70 75 86 91 95 105 120 230

1. Si la clave a eliminar no está en una hoja, se debe

4. Primero se intenta redistribuir con un hermano

5. Si la redistribución no es posible, entonces se debe

Casos especiales: en cualquier política si se tratase de un nodo hoja de un

25 40 55 70 86 95 105 120 230

La eliminación de la clave 70 en el nodo 1 produce

-70 , -105 , -86

-86 , -230 , -95

También podría gustarte