Fator de balanceamento em árvores AVL
Em algumas implementações de árvore balanceadas, existe uma propriedade chamada comumente de fb (fato de balanceamento), ou em inglês bf (balance factor), que é um valor compreendido entre
+1: subárvore esquerda mais alta que a direita0: subárvore esquerda igual a direita- 1: subárvore direita mais alta do que a esquerda
O fator de balanceamento é calculador a partir de
Warning
A explicação acima foi baseada a partir da seguinte fórmula para calcular o fator de balanceamento
. Entretanto, algumas referências podem adotar a seguinte fórmula , a única diferença é que os sinais do fbestarão trocados.
class Node {
private int value;
private Node left;
private Node right;
private int fb;
// Construtor, getters e setters
}Para rebalancear as subárvores existem algoritmos de rotação para garantir que essa propriedade se mantenha em árvores AVL, por exemplo.
