Árvore AVL
Última atualização
Uma árvore AVL é uma árvore binária de busca autobalanceada. Funciona como uma BST normal, mas após cada inserção verifica o fator de balanceamento de cada ancestral - a diferença de altura entre suas subárvores esquerda e direita - e se algum nó ficar desbalanceado (uma diferença maior que 1), realiza rotações para restaurar o balanceamento. Pressione reproduzir acima para ver os valores sendo inseridos e a árvore girar de volta à sua forma correta.
Como nunca deixa a árvore ficar mais do que levemente desequilibrada, uma árvore AVL garante altura O(log n), então busca, inserção e remoção são sempre O(log n) - mesmo para entradas ordenadas que arruinariam uma BST comum. O custo são as rotações extras e o controle de altura em cada inserção.
Complexidade de tempo e espaço
| Operação | Complexidade | Notas |
|---|---|---|
| Busca | O(log n) | A altura é sempre ~1.44 log n |
| Inserção | O(log n) | Mais O(1) rotações |
| Remoção | O(log n) | Mais O(log n) rotações |
| Espaço | O(n) | Um campo de altura por nó |
Os quatro casos de rotação
| Caso | Desbalanceamento | Correção |
|---|---|---|
| Esquerda-Esquerda | Pesado na esquerda do filho esquerdo | Uma rotação à direita |
| Direita-Direita | Pesado na direita do filho direito | Uma rotação à esquerda |
| Esquerda-Direita | Pesado na direita do filho esquerdo | Rotação à esquerda e depois à direita |
| Direita-Esquerda | Pesado na esquerda do filho direito | Rotação à direita e depois à esquerda |
Exemplo resolvido
Inserindo [10, 20, 30, 40, 50, 25] um valor de cada vez:
| Passo | Estrutura | Ação |
|---|---|---|
Inserir 10 | 10 | O primeiro nó se torna a raiz; balanceado |
Inserir 20 | 10(_, 20) | Vai à direita de 10; ainda balanceado |
Inserir 30 | 20(10, 30) | Direita-Direita em 10, então uma rotação à esquerda eleva 20 à raiz |
Inserir 40 | 20(10, 30(_, 40)) | Vai à direita de 30; todos os fatores de balanceamento ficam dentro de ±1 |
Inserir 50 | 20(10, 40(30, 50)) | Direita-Direita em 30, então uma rotação à esquerda em 30 eleva 40 |
Inserir 25 | 30(20(10, 25), 40(_, 50)) | Direita-Esquerda em 20: rotaciona à direita a subárvore de 40 e depois rotaciona à esquerda 20 |
Quando usar uma árvore AVL
| Use quando | Evite quando |
|---|---|
| As buscas superam em muito as inserções e você quer a altura mais compacta possível | Inserções e remoções dominam - as rotações e o rebalanceamento extras custam mais do que numa árvore rubro-negra |
Você precisa de pior caso garantido O(log n), mesmo para entradas adversárias ou ordenadas | Uma tabela hash simples bastaria - você não precisa de percurso ordenado nem consultas por intervalo |
| Você precisa de operações ordenadas: percurso em ordem, predecessor/sucessor, consultas por intervalo | O conjunto de dados é minúsculo - uma BST comum ou um array ordenado é mais simples e rápido o suficiente |
| Os dados podem chegar já ordenados, o que transformaria uma BST não balanceada numa lista encadeada | Você não pode arcar com a memória extra do campo de altura por nó num espaço muito restrito |
Código de AVL Tree
Uma implementação limpa e executável de AVL Tree em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de AVL Tree em Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)Código de AVL Tree em JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));Código de AVL Tree em Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}Código de AVL Tree em C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}Código de AVL Tree em C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}Perguntas frequentes sobre a árvore AVL
O que é um fator de balanceamento numa árvore AVL?
O fator de balanceamento de um nó é a altura de sua subárvore esquerda menos a altura de sua subárvore direita. Uma árvore AVL mantém o fator de balanceamento de cada nó em -1, 0 ou +1; se uma inserção o tira desse intervalo, uma rotação restaura o balanceamento.
Qual é a diferença entre uma árvore AVL e uma árvore rubro-negra?
Ambas são BSTs autobalanceadas com operações
O(log n). As árvores AVL são mais estritamente balanceadas, então as buscas são ligeiramente mais rápidas, mas podem fazer mais rotações na inserção/remoção. As árvores rubro-negras são mais frouxamente balanceadas, favorecendo menos rotações - por isso muitas bibliotecas padrão as usam para mapas e conjuntos.Por que usar uma árvore AVL em vez de uma árvore binária de busca comum?
Uma BST comum pode degradar para operações
O(n) se os valores chegarem em ordem, formando uma cadeia enviesada. Uma árvore AVL rotaciona para permanecer balanceada, garantindo altura e operações O(log n) independentemente da ordem de inserção.Uma árvore AVL é melhor que uma árvore rubro-negra para um índice de banco de dados?
Depende da carga de trabalho. As árvores AVL são mais rigidamente balanceadas, então vencem quando as leituras dominam e você quer os caminhos de busca mais curtos possíveis. Mas a maioria dos bancos de dados e bibliotecas de linguagens escolhe árvores rubro-negras (ou árvores B) porque rebalanceiam com menos rotações em cargas com muitas escritas, o que importa mais quando inserções e remoções são frequentes.
Quantas rotações uma única inserção AVL precisa?
É necessária no máximo uma rotação - seja uma rotação simples ou uma dupla (de dois passos) - para rebalancear a árvore após inserir um valor. Isso ocorre porque uma inserção aumenta a altura de uma subárvore em no máximo um, então uma única correção no ancestral desbalanceado mais baixo basta. A remoção é diferente: pode exigir até
O(log n) rotações à medida que o rebalanceamento se propaga em direção à raiz.Preciso atualizar as alturas dos nós após cada rotação?
Sim - um erro comum é rotacionar os ponteiros corretamente mas esquecer de recalcular a altura dos dois nós envolvidos. Após cada rotação você deve atualizar primeiro a altura do nó rebaixado e depois a do nó promovido, porque a altura do nó promovido depende de seus novos filhos. Omitir isso deixa fatores de balanceamento desatualizados que quebram as decisões de rebalanceamento futuras.
Recursos relacionados
Mais visualizações
