La idea de los árboles -B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten.
Reglas
* Cada nodo del árbol debe tener un mínimo de n valores en todo momento, a excepción de la raíz.
* El número máximo de valores que un nodo puede tener es 2*n
* El árbol siempre esta balanceado.
* Todos los nodos hojas deben aparecer juntas en el último nivel.
Búsqueda
* La búsqueda es similar a la de los árboles binarios, se empieza en la raíz, y se recorre el árbol hacia abajo. Si la clave buscada no esta en la raíz y se llega a una hoja la clave no existe.
Inserción
* Las inserciones se hacen en los nodos hoja.
1- Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2- Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más.
3- De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
A- Se escoge el valor medio entre los elementos del nodo y el nuevo elemento
B- Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador
C- 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ón
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades.
Tipos de eliminación
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.
Eliminación en un nodo interno
Si el valor se encuentra en un nodo interno, se escoge 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.
Reglas
* Cada nodo del árbol debe tener un mínimo de n valores en todo momento, a excepción de la raíz.
* El número máximo de valores que un nodo puede tener es 2*n
* El árbol siempre esta balanceado.
* Todos los nodos hojas deben aparecer juntas en el último nivel.
Búsqueda
* La búsqueda es similar a la de los árboles binarios, se empieza en la raíz, y se recorre el árbol hacia abajo. Si la clave buscada no esta en la raíz y se llega a una hoja la clave no existe.
Inserción
* Las inserciones se hacen en los nodos hoja.
1- Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2- Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más.
3- De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
A- Se escoge el valor medio entre los elementos del nodo y el nuevo elemento
B- Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador
C- 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ón
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades.
Tipos de eliminación
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.
Eliminación en un nodo interno
Si el valor se encuentra en un nodo interno, se escoge 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.
Comentarios
Publicar un comentario