estructura de datos

centercenterChristian Callejas
  
árboles AVL, b y b+
8820090900Christian Callejas
  
árboles AVL, b y b+


áRBOLES AVL
El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la publicación de un artículo en 1962, Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. Los árbolesAVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo).
Insertar en árboles avl
La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibradoy después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.
Proceso de inserción:
1.-Buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)
2.-Insertar el nuevo nodo con factor de equilibrio “equilibrado”
3.-Desandar el camino de búsqueda, verificando elequilibrio de los nodos, y re-equilibrando si es necesario
Borrar en árboles avl
El procedimiento de borrado es el mismo que en el caso de árbol binario de búsqueda. La diferencia se encuentra en el proceso de reequilibrado posterior.árboles b
Los B-árboles surgieron en 1972 creados por R. Bayer y E.McCreight.El problema original comienza con la necesidad de mantener índices en almacenamiento externopara acceso a bases de datos es decir, con el grave problema de la lentitud de estos dispositivos se pretende aprovechar la gran capacidad de almacenamiento para mantener una cantidad de información muy alta organizada de forma que el acceso a una clave sea lo más rápido posible.
insertar en árboles b
Buscamos la hoja donde debiéramos encontrar el valor de la clave de una forma totalmente paralelaa la búsqueda de ésta tal como comentábamos en la sección anterior (si en esta búsqueda encontramos en algún lugar del árbol la clave a insertar, el algoritmo no debe hacer nada más).Si la clave no se encuentra en el árbol habremos llegado a una hoja que es justamente el lugar donde debemos realizar esa inserción.
Situados en un nodo donde realizar la inserción si no está completo, es decir, siel número de claves que existen es menor que el orden menos 1 del árbol, el elemento puede ser insertado y el algoritmo termina. En caso de que el nodo esté completo insertamos la clave en su posición y puesto que no caben en un único nodo dividimos en dos nuevos nodos conteniendo cada uno de ellos la mitad de las claves y tomando una de éstas para insertarla en el padre (se usará la mediana).Siel padre está también completo, habrá que repetir el proceso hasta llegar a la raíz. En caso de que la raíz esté completa, la altura del árbol aumenta en uno creando un nuevo nodo raíz con una única clave.
Podemos realizar una modificación al algoritmo de forma que se retrase al máximo el momento de romper un nodo en dos. Con ello podríamos vernos beneficiados por dos razones fundamentalmente: Larazón más importante para modificar así el algoritmo es que los nodos en el árbol están más llenos con lo cual el gasto en memoria para mantener la estructura es mucho menor.
Retrasamos el momento en que la raíz llega a dividirse y por consiguiente retrasamos el momento en que la altura del árbol aumenta.
La forma más sencilla de realizar esta modificación es que en el caso de que tengamos querealizar esa división, antes de llevarla a cabo, comprobemos si los hermanos adyacentes tienen espacio libre de forma que si alguno de ellos lo tiene se redistribuyen las claves que se encuentran en el nodo actual más las de ese hermano más la clave que los separa(que se encuentra en el padre)más la clave a insertar de forma que en el padre se queda la mediana y las demás quedan distribuidas...