EL
ÀRBOL (AVL)
El árbol AVL toma su nombre de las iniciales de los apellidos de
sus inventores, Adelson-Velskii y Landis.
Lo dieron a conocer en la publicación de un artículo en 1962:
"An algorithm for the organization of information" ("Un
algoritmo para la organización de la información").
Los árboles
AVL 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. Gracias a esta forma de equilibrio (o balanceo), la complejidad
de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad
O(log
n). El factor de equilibrio puede ser almacenado directamente en cada
nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir
esta propiedad de equilibrio, la inserción y el borrado de los nodos se han de
realizar de una forma especial. Si al realizar una operación de inserción o
borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los
nodos.
Los árboles AVL más profundos son los árboles de Fibonacci.
Factor de equilibrio
Cada nodo, además de la información que se pretende
almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual
que los árboles
binarios de búsqueda (ABB), y además el dato que controla el factor
de equilibrio.
El factor de
equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol
izquierdo;
Por definición, para un árbol AVL, este valor debe
ser -1, 0 ó 1.
Operaciones
Las operaciones
básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos
que serían realizados en un árbol binario
de búsqueda desequilibrado, pero precedido o seguido por una o más
de las llamadas "rotaciones AVL".
Árbol-B+
En informática, un árbol-B es un tipo
de estructura de datos de árboles. Representa una colección de datos ordenados
de manera que se permite una inserción y borrado eficientes de elementos. Es un
índice, multinivel, dinámico, con un límite máximo y mínimo en el número de
claves por nodo.
Un árbol-B+ es
una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B,
toda la información se guarda en las hojas. Los nodos internos sólo contienen
claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel.
Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir
búsqueda secuencial.
El número máximo
de claves en un registro es llamado el orden del árbol-B+.
El mínimo número
de claves por registro es la mitad del máximo número de claves. Por ejemplo, si
el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre
n/2 y n claves.
El número de claves que
pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y
su altura.