Arboles B

Universidad Mariano Gálvez de Guatemala Programación III

ARBOLES B

Definición: Un árbol B de orden n es aquel árbol de búsqueda que satisface las siguientes propiedades: 1. Cada página contiene máximo 2n llaves y mínimo n llaves, excepto la raíz (que puede contener sólo una). 2. Cada página o bien es una página hoja (no tiene descendientes) o bien tiene m+1 páginas descendientes, siendo m el nº de llaves en esta página. 3. Todas las páginas hoja aparecen al mismo nivel.

Árboles B

Ejemplo de árbol B de orden 2 Satisface las condiciones de árbol de búsqueda. Cada página contiene como máximo 2x2 = 4 llaves, y como mínimo 2 llaves, excepto la raíz que almacena una sola. Todas las páginas de hoja están en el mismo nivel, el nivel 3, y las que no son de hoja tienen m+1 descendientes. Así la raíz con una sola llave (m=1) apunta a dos páginas, y en el segundo nivel, las páginas contienen dos llaves (m=2) y por tanto tienen tres descendientes.

Árboles B

Árboles B

INSERTAR • Buscar el lugar donde insertar la clave, siguiendo el mismo criterio de ABB • Si la página tiene m claves, con m<2n–Insertar de acuerdo al criterio de ABB • En caso contrario– Re-balancear el árbol.

REBALANCE• Dividir la página en dos páginas • Si la clave>=C(m/2), entonces subir un nivel el menor de los mayores de la subpagina y luego hacer: C(m/2) izquierdo apunta subpágina izquierda C(m/2) derecho apunta subpágina derecha. • Si la clave<C(m/2), entonces simétricas

Árboles B

PROCESO ELIMINAR •B.1)Tomar el elemento más a la derecha de la página hoja del Subárbol Izquierdo–El Mayor de los menores •B.2) Tomar el elemento más a la Izquierda de la página hoja del Subárbol Derecho.–El Menor de los mayores

ELIMINAR • A) Si la clave se encuentra en una página hoja, entonces la eliminación es directa •B) En caso contrario:–Intercambiar el elemento con un elemento de una página hoja. •B.1) Subárbol Izquierda o •B.2) Subárbol Derecha

Árboles B

•SUBOCUPACIÓN • La nueva página será: –La página actual –La página adyacente –El elemento entre ellas del Nivel Superior .• Este proceso se realiza en dirección al Nodo Raíz.

ELIMINAR-SUBOCUPACION Si tras el Intercambio de eliminación se produce que una página tenga Menos de n-elementos. Entonces, se produce una subocupación. Por lo tanto, se debe realizar el siguiente proceso:

Árboles B

https://www.cs.usfca.edu/~galles/visualization/BTree.html

•Indicar si esta es la respuesta correcta (si y no, porque) Puede utilizar el simulador:

Árboles B

MEJORAR EL SIGUIENTE CODIGO QUE APARECE EN EL LINK ABAJO DEL VIDEO PUEDE SERVIRLE DE BASE PARA CREAR SU ARBOL B, O PUEDE HACERLO DE NUEVO, AGREGARLE EL METODO DE ELIMINAR QUE EL INGRESO DE LOS DATOS NO ESTE EN EL CODIGO, SI NO QUE SE INGRESEN

https://github.com/csanjuanc/estructuras-de-datos/tree/master/B_Tree

Árboles B