¿Qué son los árboles B?
Los árboles reciben su nombre de R. Bayer, quien en 1970 propuso un nuevo tipo de árboles, en los que todas las páginas, excepto una), contienen entre n y 2n nodos, siendo n una constante dada. Como consecuencia de esto se puede deducir que los árboles B no son árboles binarios como sí lo son los binarios de búsqueda o los AVL.
En los árboles B los nodos se agrupan dentro de páginas, por lo que se podría definir a la página como un conjunto de nodos.
Los árboles B deben cumplir las siguientes características en cuanto a estructura:
Toda página tiene como máximo 2n nodos.
Toda página distinta de la raíz tiene como mínimo n nodos. La raíz tiene como mínimo 1 nodo.
Toda página que no sea una hoja tiene m+1 páginas hijas, siendo m el número de nodos de la página.
Todas las páginas hoja están en el último nivel.
Además de estas características, los árboles B tienen que cumplir un cierto orden:
Los nodos dentro de una página mantienen un orden ascendente de izquierda a derecha.
Cada nodo es mayor que los nodos situados a su izquierda.
Cada nodo es mayor que los nodos situados a su derecha.
A continuación se muestran dos árboles, uno de ellos es un árbol B y otro no.
Estructura de un árbol B. Cada hoja tiene 4 nodos
Este es un árbol B correcto, ya que cumple todas las reglas en cuanto a su estructura y al orden.
Estructura de un árbol B incorrecto. Nodo no raíz con menos de n nodos
En cambio, este no es un árbol B, ya que a pesar de mantener el orden, hay una página (que no es la raíz) que tiene menos de n elementos (en este caso menos de 2 elementos). Esta página es la que contiene al elemento 10.
No hay comentarios:
Publicar un comentario