miniatura|alt=Animación da inserción de elementos nunha árbore AVL con rotacións simples e dobres.|Animación da inserción de varios elementos nunha árbore AVL. Inclúe rotacións simples á esquerda e á dereita, e dobres esquerda-dereita e dereita-esquerda. miniatura|dereita|262px|alt=Árbore AVL cos factores de equilibrio indicados en verde.|Fig. 1: Árbore AVL cos factores de equilibrio (en verde).
En ciencias da computación, unha árbore AVL (chamada así polos seus inventores, Adelson-Velsky e Landis) é unha árbore binaria de busca auto-equilibrada. Nunha árbore AVL, as alturas das dúas subárbores fillas de calquera nó difiren como máximo nunha unidade; se nalgún momento difiren en máis dunha, realízase un reequilibrado para restaurar esa propiedade. A busca, a inserción e o borrado teñen un custo tanto de media como no peor caso, onde é o número de nós da árbore antes da operación. As insercións e os borrados poden requirir reequilibrar a árbore mediante unha ou máis rotacións.
A árbore AVL recibe o nome dos seus dous inventores soviéticos, Georgy Adelson-Velsky e Evgenii Landis, que a publicaron en 1962 no artigo «An algorithm for the organization of information». Tradución inglesa de Myron J. Ricci en Soviet Mathematics - Doklady, 3:1259–1263, 1962. É a primeira estrutura de datos de árbore binaria de busca auto-equilibrada que se inventou.
As árbores AVL compáranse a miúdo coas árbores rubinegras, porque ambas admiten o mesmo conxunto de operacións e empregan para as operacións básicas. O equilibrio máis estrito das AVL pode reducir as comparacións nas aplicacións con moitas buscas, pero o rendemento práctico depende da implementación e da carga de traballo. O equilibrio en altura non implica que as subárbores irmás teñan un número semellante de descendentes: estas estruturas non impoñen as mesmas restricións de tamaño ca unha árbore de peso equilibrado.
Definición Factor de equilibrio Nunha árbore binaria, o factor de equilibrio dun nó X defínese como a diferenza de alturas
onde é a subárbore dereita de e a esquerda.
Unha árbore binaria de busca é unha árbore AVL se
para cada nó X da árbore.
Un nó X con denomínase «pesado á esquerda», un con denomínase «pesado á dereita», e un con ás veces denomínase simplemente «equilibrado».
Propiedades Os factores de equilibrio poden manterse actualizados coñecendo os factores anteriores e a variación de altura; non é necesario coñecer a altura absoluta. Para gardar a información de equilibrio da árbore AVL abondan dous bits por nó.Non obstante, a información de equilibrio pode gardarse nos nós fillos como un bit que indique se o pai é máis alto en 1 ou en 2; así, unha diferenza de 2 non pode producirse nos dous fillos á vez. Deste xeito, a árbore AVL é unha árbore equilibrada en rango (rank balanced), na terminoloxía de Haeupler, Sen e Tarjan.
A altura (contada como o número máximo de niveis) dunha árbore AVL con nós está no intervalo:
onde é o número áureo e Isto débese a que unha árbore AVL de altura contén polo menos nós, onde é a sucesión de Fibonacci cos valores iniciais
Operacións As operacións de lectura nunha árbore AVL realizan as mesmas accións que nunha árbore binaria de busca non equilibrada, pero as modificacións deben respectar e restaurar o equilibrio de altura das subárbores.
Busca A busca dunha chave concreta nunha árbore AVL pódese facer do mesmo xeito que nunha árbore binaria de busca calquera, equilibrada ou non. Para que a busca funcione correctamente, debe empregar unha función de comparación que estableza unha orde total (ou polo menos unha preorde total) no conxunto de chaves. O número de comparacións necesarias nunha busca con éxito está limitado pola altura , e nunha busca sen éxito é moi próximo a , polo que ambas están en , onde é o número de nós da árbore.
Percorrido Como operación de lectura, o percorrido dunha árbore AVL funciona igual que en calquera outra árbore binaria. Explorar os nós da árbore visita cada ligazón exactamente dúas veces: unha visita descendente para entrar na subárbore con raíz nese nó, e outra ascendente para saír dela despois de explorala.
Unha vez atopado un nó nunha árbore AVL, pódese acceder ao nó seguinte ou anterior en tempo constante amortizado. Algúns casos de exploración destes nós «próximos» requiren percorrer ata ligazóns (en particular, ao navegar desde a folla máis á dereita da subárbore esquerda da raíz ata a raíz, ou desde a raíz ata a folla máis á esquerda da subárbore dereita; na árbore AVL da figura 1, navegar do nó P ao nó Q inmediatamente á dereita require 3 pasos). Como calquera árbore ten ligazóns, o custo amortizado é , é dicir, aproximadamente 2.
Inserción Ao inserir un nó nunha árbore AVL, séguense inicialmente os mesmos pasos que ao inserir nunha árbore binaria de busca. Se a árbore está baleira, o nó insírese como raíz. Se non está baleira, descéndese desde a raíz de forma recursiva buscando o lugar onde inserir o novo nó, guiándose pola función de comparación. O nó substitúe sempre unha referencia nula (esquerda ou dereita) dun nó externo da árbore, é dicir, o nó convértese no fillo esquerdo ou dereito do nó externo.
Despois desta inserción, se a árbore queda desequilibrada, só están desequilibrados os antepasados do nó inserido, porque son os únicos cuxas subárbores se alteraron. Por tanto, hai que comprobar cada antepasado do nó para verificar a súa coherencia coas invariantes das árbores AVL; isto denomínase «retroceso» (retracing). Faise considerando o factor de equilibrio de cada nó.
Como cunha soa inserción a altura dunha subárbore AVL non pode aumentar en máis dunha unidade, o factor de equilibrio temporal dun nó tras unha inserción estará no rango [–2,+2]. Para cada nó comprobado, se o factor de equilibrio temporal permanece entre –1 e +1, abonda con actualizar o factor e non é necesaria ningunha rotación. Porén, se o factor de equilibrio temporal é ±2, a subárbore con raíz nese nó está desequilibrada e cómpre unha rotación. Coa inserción, como mostra o código seguinte, a rotación axeitada reequilibra de inmediato a árbore.
Na figura 1, ao inserir o novo nó Z como fillo do nó X, a altura da subárbore Z aumenta de 0 a 1.
Invariante do bucle de retroceso dunha inserción A altura da subárbore con raíz en Z aumentou nunha unidade. Xa ten forma AVL.
Código de exemplo dunha operación de inserción for (X = parent(Z); X != null; X = parent(Z)) { // Bucle (posiblemente ata a raíz) // Hai que actualizar FE(X): if (Z == right_child(X)) { // A subárbore dereita aumenta if (FE(X) > 0) { // X é pesado á dereita // ==> o FE(X) temporal == +2 // ==> cómpre reequilibrar. G = parent(X); // Gardar o pai de X durante as rotacións if (FE(Z) < 0) // Caso dereita-esquerda (ver figura 3) N = rotate_RightLeft(X, Z); // Rotación dobre: Right(Z) e despois Left(X) else // Caso dereita-dereita (ver figura 2) N = rotate_Left(X, Z); // Rotación simple Left(X) // Tras a rotación, adaptar a ligazón do pai } else { if (FE(X) < 0) { FE(X) = 0; // O aumento de altura de Z absórbese en X. break; // Saír do bucle
FE(X) = +1; Z = X; // Altura(Z) aumenta 1 continue;
} else { // Z == left_child(X): a subárbore esquerda aumenta if (FE(X) < 0) { // X é pesado á esquerda // ==> o FE(X) temporal == -2 // ==> cómpre reequilibrar. G = parent(X); // Gardar o pai de X durante as rotacións if (FE(Z) > 0) // Caso esquerda-dereita N = rotate_LeftRight(X, Z); // Rotación dobre: Left(Z) e despois Right(X) else // Caso esquerda-esquerda N = rotate_Right(X, Z); // Rotación simple Right(X) // Tras a rotación, adaptar a ligazón do pai } else { if (FE(X) > 0) { FE(X) = 0; // O aumento de altura de Z absórbese en X. break; // Saír do bucle
FE(X) = -1; Z = X; // Altura(Z) aumenta 1 continue;
// Tras unha rotación, adaptar a ligazón do pai: // N é a nova raíz da subárbore rotada // A altura non cambia: Altura(N) == Altura antiga de X parent(N) = G; if (G != null) { if (X == left_child(G)) left_child(G) = N; else right_child(G) = N; } else tree->root = N; // N é a nova raíz da árbore completa break; // Cada rama termina en break ou continue. } // Se o bucle non sae por break, a altura da árbore completa aumenta 1.
Para actualizar os factores de equilibrio de todos os nós, obsérvese primeiro que todos os que requiren corrección están, de fillo a pai, ao longo do camiño da folla inserida. Se se aplica o procedemento anterior aos nós deste camiño, comezando pola folla, todos os nós da árbore volverán ter un factor de equilibrio de −1, 0 ou 1.
O retroceso pode deterse se o factor de equilibrio pasa a 0, o que implica que a altura desa subárbore non cambia.
Se o factor de equilibrio pasa a ±1, a altura da subárbore aumenta nunha unidade e o retroceso debe continuar.
Se o factor de equilibrio pasa temporalmente a ±2, hai que corrixilo cunha rotación axeitada, tras a cal a subárbore ten a mesma altura que antes (e a súa raíz, factor de equilibrio 0).
O tempo necesario é para a busca, máis un máximo de niveis de retroceso ( de media) no regreso cara á raíz, polo que a operación se completa en tempo .
Borrado Os pasos previos para borrar un nó son os mesmos que nunha árbore binaria de busca. O borrado efectivo do nó afectado ou do nó de substitución reduce a altura da subárbore correspondente de 1 a 0 ou de 2 a 1, se ese nó tiña un fillo.
A partir desa subárbore, hai que comprobar cada antepasado para verificar a súa coherencia coas invariantes das árbores AVL. Isto denomínase «retroceso».
Como cun só borrado a altura dunha subárbore AVL non pode diminuír en máis dunha unidade, o factor de equilibrio temporal dun nó estará no rango de −2 a +2. Se o factor de equilibrio permanece entre −1 e +1, pódese axustar conforme ás regras AVL. Se pasa a ±2, a subárbore está desequilibrada e cómpre rotala. A diferenza da inserción, onde unha rotación sempre equilibra a árbore, tras un borrado pode ocorrer que FE(Z) ≠ 0 (ver figuras 2 e 3), de modo que tras a rotación simple ou dobre axeitada a altura da subárbore reequilibrada diminúe nunha unidade, o que obriga a reequilibrar de novo no nivel superior. Os distintos casos de rotación descríbense na sección Reequilibrado.
Invariante do bucle de retroceso dun borrado A altura da subárbore con raíz en N diminuíu nunha unidade. Xa ten forma AVL.
Pseudocódigo do retroceso dunha operación de borrado Antes de retirar o nó gárdanse o pai P da subárbore que perde altura e un indicador from_left do lado afectado. Isto permite iniciar o retroceso mesmo cando a subárbore de substitución N é nula. for (X = P; X != null; X = G) { // P e from_left conserváronse antes do borrado G = parent(X); // Gardar o pai de X durante as rotacións bool next_from_left = G != null && X == left_child(G); // Aínda non se actualizou FE(X)! if (from_left) { // A subárbore esquerda diminúe if (FE(X) > 0) { // X é pesado á dereita // ==> o FE(X) temporal == +2 // ==> cómpre reequilibrar. Z = right_child(X); // Irmán de N (máis alto en 2) b = FE(Z); if (b < 0) // Caso dereita-esquerda (ver figura 3) N = rotate_RightLeft(X, Z); // Rotación dobre: Right(Z) e despois Left(X) else // Caso dereita-dereita (ver figura 2) N = rotate_Left(X, Z); // Rotación simple Left(X) // Tras a rotación, adaptar a ligazón do pai } else { if (FE(X) == 0) { FE(X) = +1; // A diminución de altura de N absórbese en X. break; // Saír do bucle
N = X; FE(N) = 0; // Altura(N) diminúe 1 from_left = next_from_left; continue;
} else { // (N == right_child(X)): A subárbore dereita diminúe if (FE(X) < 0) { // X é pesado á esquerda // ==> o FE(X) temporal == -2 // ==> cómpre reequilibrar. Z = left_child(X); // Irmán de N (máis alto en 2) b = FE(Z); if (b > 0) // Caso esquerda-dereita N = rotate_LeftRight(X, Z); // Rotación dobre: Left(Z) e despois Right(X) else // Caso esquerda-esquerda N = rotate_Right(X, Z); // Rotación simple Right(X) // Tras a rotación, adaptar a ligazón do pai } else { if (FE(X) == 0) {