Los árboles AVL son árboles de búsqueda binaria (BST) de equilibrio automático. Un BST normal puede estar sesgado a ambos lados, lo que resultará en un esfuerzo mucho mayor para buscar una clave (el orden será mucho más que [matemática] O (\ log_2n) [/ matemática]) y algunas veces igual [matemática] O (n [/ math])) a veces da el resultado del peor de los casos, que es el mismo esfuerzo dedicado a la búsqueda secuencial. Esto hace que los BST sean inútiles como una estructura de datos prácticamente eficiente.
La solución es el árbol AVL como versiones de equilibrio automático del árbol binario. El árbol verificará la diferencia de profundidad entre sus subárboles izquierdo y derecho y realiza la rotación izquierda o derecha o combinada de ciertos nodos de pivote esencialmente manteniendo la diferencia de profundidad como 1. El equilibrio se realiza con cada inserción para que la complejidad total de la inserción No cambia significativamente. Sin embargo, cada vez hay más aumento en el espacio requerido, ya que cada nodo ahora llevará un equipaje de profundidad. Los beneficios son incalculables, ya que recuperar los datos es muy eficiente y casi siempre la complejidad estará en O ( \log_2n)
Vea a continuación el código para la inserción AVL
paquete edu.amrita.cen;
import edu.amrita.cen.BinaryTree.TNode;
/ **
* *
* T1, T2, T3 y T4 son subárboles.
zy
/ \ / \
y T4 Girar a la derecha (z) xz
/ \ – – – – – – – – -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
b) Caso izquierdo derecho
zzx
/ \ / \ / \
y T4 Rotar a la izquierda (y) x T4 Rotar a la derecha (z) yz
/ \ – – – – – – – – -> / \ – – – – – – – -> / \ / \
T1 xy T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
c) Derecho Derecho Caso
zy
/ \ / \
T1 y Girar a la izquierda (z) zx
/ \ – – – – – – – -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
d) Caso derecho izquierdo
zzx
/ \ / \ / \
T1 y Rotar a la derecha (y) T1 x Rotar a la izquierda (z) zy
/ \ – – – – – – – – -> / \ – – – – – – – -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
Ejemplos de inserción:
* @author vijaykrishnamenon
* *
* /
AVLTrees de clase pública {
clase TNode {
int val, altura;
TNodo izquierda, derecha;
Public TNode (int v, TNode l, TNode r) {
val = v;
izquierda = l;
derecha = r;
altura = 0;
}
TNode público (int v) {
esto (v, nulo, nulo);
}
}
Raíz de TNode = nulo;
public int height (TNode n) {
if (n == null) devuelve 0;
de lo contrario regrese n. altura;
}
public int max (int i, int j) {
si (i> j) devuelve i;
de lo contrario, devuelve j;
}
saldo público int (TNode n) {
if (n == null) devuelve 0;
return (altura (n.left) – altura (n.right));
}
Public TNode leftRotate (TNode n) {
if (n == null) devuelve n;
TNode y = n.right;
n.right = y.izquierda;
y.izquierda = n;
n.height = max (altura (n.left), altura (n.right)) + 1;
y.height = max (altura (y.izquierda), altura (y.derecha)) + 1;
volver y;
}
Public TNode rightRotate (TNode n) {
if (n == null) devuelve n;
TNode y = n.left;
n.left = y.right;
y.right = n;
n.height = max (altura (n.left), altura (n.right)) + 1;
y.height = max (altura (y.izquierda), altura (y.derecha)) + 1;
volver y;
}
TNode protegido insert_r (raíz de TNode, int a) {
if (root == null) root = new TNode (a);
si no (root.val> a) root.left = insert_r (root.left, a);
sino root.right = insert_r (root.right, a);
root.height = max (height (root.left), height (root.right)) + 1;
int bal = balance (raíz);
//Izquierda izquierda…
if (bal> 1 && a return rightRotate (root);
//Izquierda derecha…
if (bal> 1 && a> = root.left.val) {
root.left = leftRotate (root.left);
return rightRotate (root);
}
//Bien bien…
if (bal <-1 && a> = root.right.val)
return leftRotate (root);
//Derecha izquierda…
if (bal <-1 && a root.right = rightRotate (root.right);
return leftRotate (root);
}
volver root;
}
inserción vacía pública (clave int) {
root = insert_r (raíz, clave);
System.out.println (“\ n”);
preordenar (raíz);
}
public void create (int [] a) {
para (int i = 0; i insertar (a [i]);
}
pedido público vacío (raíz de TNode) {
if (root == null) return;
System.out.print (root.val + “(“);
if (root.left! = null) {
preordenar (root.left);
System.out.print (“,”);
}
if (root.right! = null) {
preordenar (root.right);
}
System.out.print (“)”);
}
public static void main (String [] args) {
AVLTrees t = new AVLTrees ();
int [] a = {7,6,5,4,3,2,1, -1, -2};
t.crear (a);
System.out.println (“\ n”);
t.preorder (t.root);
}
}
