Arboles Multiv A Incompleto

Arboles Multivía
Estructuras de Datos

Borrado en Árboles B
• Solo se eliminan nodos externos.
– Si es nodo interno, se lo intercambia por el
inmediato superior (el nodo externo másizquierdo
del lado derecho).

• Si el nodo se queda con menos valores que el
mínimo, se tienen dos operaciones:
1. Redistribución
2. Unión

Operación 1: Redistribución
• Condición:– Uno de los hermanos tiene al menos uno más que
el mínimo.

• Procedimiento:
1. Baja la clave que separa del hermano.
2. Sube el valor extra del hermano.

Operación 1: Redistribución10

5

7

15

20

18

10

5

7

18

26

30

35

30

35

40

26

20

40

Operación 2: Unión
• Condición:
– Todos los hermanos tienen el mínimo de valores.

• Procedimiento
1. Se unenlos nodos junto con la clave que los
separa que se encuentra en el padre.
2. Se distribuyen los nodos como se realiza en la
inserción.

Operación 2: Unión
10

5

7

18

26

20

265

7

10

20

30

35

30

35

Árboles B +
1. Las claves se encuentran en el índice y las
hojas.
2. Las hojas tienen un puntero a la siguiente
hoja.
10

5

7

10

26

18

20

26

3035

Árboles 2-4
• Árbol B de nivel 4.
10

5

7

18

20

26

65

30

35

77

85

Árboles B*
• Mejor aprovechamiento de la memoria.
– Cada nodo debe estar lleno 2/3 siempre

• Labúsqueda es más rápida que en el árbol B+,
pero la inserción es más costosa.
• La división y fusión de nodos cambian.

Árboles B*
• División por super-ocupación
– Pasar elementos alvecino
– Cuando el vecino también está lleno, los dos
nodos se convierten en tres

• Fusión por sub-ocupación
– Tres nodos se convierten en dos

Árboles R
• Parecido a árboles B
• R es de«Rectángulo»
• Se utilizan para indexar información
multidimensional.
• Agrupa objetos cercanos y los representa con
su rectángulo contenedor más pequeño.

Árboles R

Árboles R