Arboles B

Arboles B

Estos árboles son implementados para manejo de base de datos por su capacidad en manejo de volúmenes grandes de información, teniendo una gran ventaja frente a los árboles AVL. Son árboles de búsqueda donde los nodos pueden entre un rango de elementos, exceptuando la raíz, buscando tener un mínimo de altura haciendo los recorridos de forma más directa

Orden de los árboles B

Las características de los árboles B con referencia al orden son las siguientes:

*Todas las hojas (nodos terminales), están en el nivel inferior

*Un árbol de orden n, indica que cada nodo debe tener entre n y 2n elementos.

*En el caso de la raíz puede tener entre 1 y 2n elementos

*Si un nodo tiene m elementos, quiere decir que debe tener m+1 hijos, a menos que sea una hoja

Inserción de un elemento

Para adicionar un elemento al árbol, se realiza mediante los siguientes pasos:

• Busca la hoja donde se debería agregar el elemento
• Si hay espacio disponible, se agrega el elemento y termina
• Si en el nodo no hay espacio, se deberá crear un nuevo nodo al mismo nivel de la hoja, distribuyendo los 2n+1 elementos de la siguiente forma:
• El nuevo nodo recibe los n elementos más grandes
• El nodo existente queda con los n elementos pequeños
• El elemento medio se inserta en el nodo padre siguiendo la misma lógica. En caso de no haber un nodo padre, se creará uno nuevo que pasará a ser la nueva raíz
• 
  

Eliminación de un elemento

Para eliminar un elemento se realiza los siguientes pasos:

•  Se busca el elemento a eliminar
•  Si el elemento está en una hoja, se elimina y termina
•  Si el elemento no está en una hoja, se busca el sustituto más apropiado de la siguiente forma:*Se ubica el elemento de la hoja que este mas a la derecha del subárbol izquierdo del nodo actual, es decir, el mayor elemento entre los menores
  * El primer elemento de la hoja que este mas izquierda del subárbol derecho del nodo actual, es decir, el menor elemento entre los mayores