estructura de datos

ÁRBOLES BALANCEADOS
La forma más eficaz de realizar una búsqueda en un árbol binario, es que el mismo esté balanceado.
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".
ROTACIONES
Las rotaciones internas enárboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico
El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia laderecha o hacia la izquierda.
ROTACIÓN SIMPLE A LA DERECHA
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será elhijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
op rotDer: AVL{X} -> [AVL{X}] .
eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) ==
arbolBin(R2, I2, arbolBin(R1, D2, D)) .
ROTACIÓN SIMPLE A LA IZQUIERDA.
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos elhijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición: Tiene que tener hijo derecho no vacío.
op rotIzq: AVL{X} -> [AVL{X}] .
eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) ==
arbolBin(R2, arbolBin(R1,I, I2), D2) .
Si la inserción se produce en el hijo derecho del hijo izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación.
ROTACIÓN DOBLE A LA DERECHA. La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.
ROTACIÓN DOBLE A LA IZQUIERDA
La Rotación doble a la Izquierda son dos rotacionessimples, primero rotación simple derecha y luego rotación simple izquierda.
Lamentablemente, la operación insertar no asegura, que el árbol permanezca balancea, el mismo depende del orden en que son insertados los datos en el nodo. La altura de un árbol binario depende del nivel máximo de sus hojas, es decir, su profundidad.
La altura de un árbol nulo se define como, un árbol binario balanceado es através de las alturas de los dos subárboles de un nodo defiere a la suma 1. El balance de un nodo en un árbol binario se define como la altura de su subárbol izquierdo menos la altura de su árbol derecho.
Cada nodo en un árbol binario balanceado, tiene el balance de 1, -1 ó 0, dependiendo de la altura de su árbol izquierdo es mayor que, menor que o igual que, a la altura de su subárbol derecho.Es fácil ver que un árbol se vuelve desbalanceado si y solo si el nodo recién insertado es un descendiente izquierdo de un nodo que tenia de manera previa balance 1, o si es un derecho descendiente de un nodo que tenia de manera previa balance -1.
Para que el árbol se mantenga balanceado es necesario realizar transformación en el mismo que:
1.- el recorrido del árbol sea el mismo que para elárbol original (es decir, que el árbol transformado siga siendo un árbol de búsqueda binaria).
2.- el árbol balanceado este transformado.
El árbol de la figura 1b es una rotación derecha del árbol con raíz en A de manera similar, el árbol de la figura c se dice que es una rotación izquierda del árbol con una raíz en A.
Un algoritmo para implementar una rotación izquierda de un subárbol con una...