Árvore AVL
Comece com uma árvore AVL aleatória e insira, busque ou exclua valores passo a passo: veja o fator de balanceamento de cada nó, as rotações LL, RR, LR e RL, sua forma em array e o código C++ destacado.
Tudo é simulado neste navegador; nada é enviado a nenhum servidor.
Sem passos
Sem passos
Árvore AVL
Índice no array · Fator de balanceamento
Forma em array
Os filhos do índice i estão em 2i+1 e 2i+2.
- Sem relação
- Já percorrido
- Sendo comparado
- Encontrado
- Novo
- A excluir
- Sucessor
- Desbalanceado
- Pivô
Sem passos
Código
#include <iostream>
#include <algorithm>
using namespace std;
class Node { // Um nó guarda seu valor e ponteiros para seus dois filhos
private: // Atributos privados: só os métodos acessam
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Altura: uma folha vale 1 e uma posição vazia (nullptr) vale 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Fator de balanceamento: altura esquerda menos altura direita
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Rotação simples à direita: o filho esquerdo x sobe e y desce
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Rotação simples à esquerda: o filho direito y sobe e x desce
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Devolve a raiz da subárvore, balanceada
int bf = balanceFactor(n); // Calcula-se o fator de balanceamento do nó
if (bf > 1) { // Pesada à esquerda. Se o filho esquerdo não é pesado à direita, é o caso LL
if (balanceFactor(n->getLeft()) < 0) // O filho esquerdo é pesado à direita: caso LR, girar à esquerda primeiro
n->setLeft(rotateLeft(n->getLeft())); // Primeira rotação do caso LR
return rotateRight(n); // Rotação à direita: resolve LL e a segunda metade de LR
}
if (bf < -1) { // Pesada à direita. Se o filho direito não é pesado à esquerda, é o caso RR
if (balanceFactor(n->getRight()) > 0) // O filho direito é pesado à esquerda: caso RL, girar à direita primeiro
n->setRight(rotateRight(n->getRight())); // Primeira rotação do caso RL
return rotateLeft(n); // Rotação à esquerda: resolve RR e a segunda metade de RL
}
return n; // O fator está entre -1 e 1: não é preciso rotacionar
}
Node* insert(Node* root, int v) { // Insere v na árvore AVL e devolve a raiz
if (root == nullptr) // Posição vazia: o novo nó fica aqui
return new Node(v); // Cria o novo nó
if (v < root->getValue()) // Valores menores vão para a esquerda e maiores para a direita
root->setLeft(insert(root->getLeft(), v)); // Desce pela subárvore esquerda
else
root->setRight(insert(root->getRight(), v)); // Desce pela subárvore direita
return rebalance(root); // Na volta de cada chamada, verifica-se o balanceamento do nó
}
int main() {
Node* root = buildTree(); // A árvore exibida, já construída
root = insert(root, v); // Primeira chamada, a partir de main
return 0; // Fim da operação
}