Arboles 3: La Venganza de los Árboles B

Ok, estamos ya en la última parte de árboles, esto si que ha estado siendo pesado, pero no te preocupes ya casi terminamos, así que veamos…

¿Qué hay más allá de los BTS?

Árboles K-arios

A veces lo llaman m-ario o n-ario.

“Un árbol k-ario es todo aquel árbol que tiene grado k, es decir que cada nodo tiene  máximo k hijos”

 

 


Árboles B

“Como los binarios, pero mejorados..(y más difíciles)”

Pero, ¿Porqué existe? ¿Qué no un BTS es lo más eficiente de todo el mundo?

Si, la respuesta es sí, pero el problema es que no vivimos en el mundo perfecto y debido a esto es imposible usar siempre BTS sobretodo por un grave problema, son muchos hijos, eso quiere decir que tendré que buscar varias veces en un lugar muy feo… El disco duro.

hdvsram

Mira, te explico el problema, los discos de almacenamiento son lentos..como que muy lentos, así que un BTS no termina siendo la mejor opción, necesitamos algo parecido pero con más hijos, y ahí están, te presento los Árboles B:

¿Cómo se forma un Árbol B?

Nodo o Páginas

Un nodo en un Árbol B es bastante raro déjame te lo muestro y luego me explico:

CADA Nodo de un Árbol B tiene:

  • K Datos o Claves guardados en el Nodo
  • K+1 Hijos máximo (también se usa la C) (Recuerda que esto es el grado)
b.png

Nodo de un Árbol B

Ok, ok, como te has dado cuenta esto ya no se ve sencillo, me explico ahora si:

  • Todas las claves o datos del nodo deben estar ordenados, osea:

K1 < K2 < K3

  • Entre cada Dato hay un puntero a un hijo, ese hijo tiene que tener datos que son mayores que los datos que están a la izquierda pero datos menos que el dato que esta a la derecha.

 

Se ve mejor con una imagen:

b-2

Los hijos tienen valores entre K1 y K2

 

Cosas Importantes:

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO M/2 de hijos. (Excepto de la raíz)

Un nodo de un Árbol B de grado M (osea con C hijos) cada nodo debe tener como MÍNIMO (M-1)/2 claves. (Excepto de la raíz)

m.png

 

btn1 btn
btn

 

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s