ÁRBOLES B
Hecho por: Carlos Andrés González Castro Universidad San Buenaventura - Cali Ingeniería de Sistemas 1105675
Á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.
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.
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.
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
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
EliminaciónO La eliminación de un elemento es
directa si no se requiere corrección para garantizar sus propiedades.
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.
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.
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.
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
Formando un Árbol BO Ahora se quiere insertar los
números 5, 15 y 23.
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.
Gracias
Top Related