|
|
|
|
Borrado Se distinguen dos casos:
En
cualquier caso, después de la eliminación, debe seguir una comprobación
del número de elementos restantes en la página, pues si m < n se
tiene se estaría violando las Propiedades para el Arbol B de orden n y
entonces, se requiere reorganizar el Arbol. Para analizar el caso 1 (el más sencillo), considérse el Arbol B de orden 2 que se muestra en la Figura 6(a).
Figura 6. (a) Un Arbol B de orden 2 Ahora bien, supongámos que deseamos eliminar del Arbol el elemento con valor 14. El primer procedimiento es Buscar dicho elemento y determinar su posición en el Arbol (se encuentra en una página hoja). Una vez encontrado, procedemos a eliminarlo del Arbol y mover los elementos adyacentes a sus nuevas posiciones. Finalmente se debe realizar una verificación. Si la página en donde fué eliminado dicho elemento cumple con las Propiedades de Arbol B de orden 2, entonces se queda como está. En caso contrario, se debería realizar una combinación de páginas. En nuestro caso sólo debemos eliminarlo y volver a ordenar los elmentos de la página. El Arbol que se obtiene después del borrado del elemento con valor 14 se muestra en la Figura 6(b).
Figura 6. (b) El mismo Arbol B de la Figura 6(a) tras el borrado del elemento 14 El caso 2 lo analizaremos através el ejemplo de la Figura 7(a), en el cual se muestra un Arbol B de orden 2. El elemento que deseamos borrar es el 88, y se encuentra ubicado en una página que no es hoja.
Figura 7. (a) Arbol B de orden 2 Posteriormente se elimina el elemento y se reordenan los elementos restantes de la página A. Finalmente se procede a verificar el cumplimiento de las Propiedades del Arbol B de orden 2. Debido a que la página K queda con un elemento, debe hacerse una combinación entre las páginas J y L, y subir a K el elemento central, es decir el 91. Como se muestra en la Figura 7(b).
Figura 7. (b) Arbol B de la Figura 7(a) tras el borrado del elemento 88 La
reorganización se da tomando un elemeto del padre, quien, a su vez debe
tomar una elemento del hermano. Pero puede ocurrir que ya el hermano haya
alcanzado su tamaño mínimo n, y no tenga, por tanto, posibilidad de
prestar un elemento; entonces las dos páginas hermanas se unen en una sola,
conteniendo las 2n - 1 elementos de las dos hermanas más un elemeto central
proveniente del padre. La combinación de páginas, causadas por
cantidades de elementos en las páginas, menores a las permitidas,
puede prolongarse a los niveles superiores, y en el caso extremo hasta la
raíz, que cuando queda reducida a un tamaño nulo se borra, produciéndose
reducción de la altura del árbol. |
|
|||||||||||||
|
|||||||||||||||
|
|||||||||||||||
|
|||||||||||||||
|
|||||||||||||||
|
|
|
|
|
| Introducción | - | Funcionamiento | - | ¿Qué es un Arbol B? | - | Búsqueda | - | Inserción | |
|
|
| Borrado | - | Costos | - | Casos especiales | - | Conclusión | - | Bibliografía | |
|
|
|
|
| . | |
|
Web diseñado y creado por |
Copyright © 2001 |
Homepage
