arbol b
TRANSCRIPT
![Page 1: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/1.jpg)
ÁRBOLES B
Hecho por: Carlos Andrés González Castro Universidad San Buenaventura - Cali Ingeniería de Sistemas 1105675
![Page 2: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/2.jpg)
Árbol BO Es un árbol de búsqueda
multicamino balanceado.
O Surgió por la necesidad de hacer una búsqueda rápida, de cualquier tipo de contenido, sin reorganizar el archivo.
![Page 3: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/3.jpg)
ReglasO Cada nodo del árbol debe tener un
mínimo de n valores en todo momento, a excepción de la raíz.
O El número máximo de valores que un nodo puede tener es 2*n.
O El árbol siempre esta balanceado.O Todos los nodos hojas deben
aparecer juntas en el ultimo nivel.
![Page 4: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/4.jpg)
BúsquedaO La búsqueda es similar a la de los
árboles binarios, se empieza en la raíz, y se recorre el árbol hacia abajo.
O Si la clave buscada no esta en la raíz y se llega a una hoja la clave no existe.
![Page 5: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/5.jpg)
InserciónO Todas las inserciones se hacen en las
hojas.O Si el nodo hoja tiene menos
elementos que el numero máximo se inserta el nuevo elemento, respetando el orden.
O Si la hoja esta llena, el nodo se divide en dos nodos y los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores se colocan en el nuevo nodo derecho
![Page 6: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/6.jpg)
InserciónO El valor separador se debe colocar
en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente
![Page 7: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/7.jpg)
EliminaciónO La eliminación de un elemento es
directa si no se requiere corrección para garantizar sus propiedades.
![Page 8: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/8.jpg)
Tipos de Eliminación
O Eliminación en un nodo hoja: Se busca el valor a eliminar y Si el valor se encuentra en un nodo hoja, se elimina directamente la clave.
![Page 9: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/9.jpg)
Tipos de EliminaciónO Eliminación en un nodo interno:
Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y remplace el elemento a eliminar por el nuevo separador.
![Page 10: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/10.jpg)
Formando un Árbol BO Se quiere mostrar la forma en que va
creciendo un árbol B de orden 2 (n=2).
O El árbol empieza vacío y se quieren insertar 4 números(10,20,30,40).
O Se crea primero el nodo raíz y se le agregan los 4 números.
![Page 11: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/11.jpg)
Formando un Árbol BO Ahora se quiere insertar el numero
25.O Se crean dos nodos hijos y se
reparten así: el numero mediano pasa a la raíz y los números menores que el mediano pasan al nodo hijo izquierdo y los mayores al nodo hijo derecho
![Page 12: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/12.jpg)
Formando un Árbol BO Ahora se quiere insertar los
números 5, 15 y 23.
![Page 13: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/13.jpg)
Formando un Árbol BO Como ahora la raíz tendrá m=2
valores, no podrá seguir teniendo dos hijo: deberá tener m + 1 = 3 hijos.
![Page 14: Arbol B](https://reader033.vdocumento.com/reader033/viewer/2022052622/559132261a28abcb628b45cf/html5/thumbnails/14.jpg)
Gracias