Definição de árvore equilibrada

A restrição é geralmente aplicada recursivamente a cada sub-árvore. Ou seja, a árvore só é balanceada se:

1. as alturas esquerda e direita das sub-árvores diferem no máximo por uma, e
2. a sub-árvore esquerda é equilibrada, e
3. a sub-árvore direita é equilibrada

De acordo com isto, a árvore seguinte é equilibrada:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

O próximo é Não equilibrado porque as sub-árvores de C diferem em 2 na sua altura:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G  

Dito isto, o a restrição específica do primeiro ponto depende do tipo de árvore. A listada acima é a típica para as árvores de AVL .

As árvores vermelhas-pretas , por exemplo, impõem uma restrição mais suave.

Há várias formas de definir "equilibrado". O objetivo principal é manter as profundezas de todos os nós a ser O(log(n)). Parece-me que a condição de equilíbrio de que falavas é para a árvore AVL.
Aqui está a definição formal da condição de equilíbrio da árvore de AVL:

Para qualquer nó em AVL, a altura da sua sub-árvore esquerda difere por no máximo 1 da altura da sua sub-árvore direita.

Próxima pergunta., o que é "Altura"?

A "Altura " de um nó numa árvore binária é o comprimento do caminho mais longo desse nó para uma folha.

Há um caso estranho, mas comum:

As pessoas definem a altura de uma árvore vazia como (-1).

Por exemplo, o filho esquerdo da root é null:

              A  (Height = 2)
           /     \
(height =-1)       B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1
                    \
                     C (Height = 0)

Mais dois exemplos para determinar:

Sim, Uma Árvore Equilibrada Exemplo:

        A (h=3)
     /     \
 B(h=1)     C (h=2)        
/          /   \
D (h=0)  E(h=0)  F (h=1)
               /
              G (h=0)

Não, Não É Equilibrado. Árvore Exemplo:

        A (h=3)
     /     \
 B(h=0)     C (h=2)        <-- Unbalanced: 2-0 =2 > 1
           /   \
        E(h=1)  F (h=0)
        /     \
      H (h=0)   G (h=0)      

Não há diferença entre estas duas coisas. Pensa nisso. Vamos ter uma definição mais simples: "um número positivo é mesmo que seja zero ou que o número menos dois seja par."Isto diz que 8 é mesmo se 6 é par? Ou Isto diz que 8 é mesmo se 6, 4, 2, e 0 são iguais? Não há diferença. Se diz que 8 é mesmo se 6 é par, também diz que 6 é mesmo se 4 é par. E assim também diz que 4 é mesmo que 2 seja par. E assim diz que 2 é mesmo que 0 seja igual. Então se diz 8 é mesmo que 6 Seja par, ele (indiretamente) diz 8 é mesmo que 6, 4, 2, e 0 são pares. É a mesma coisa aqui. Qualquer sub-árvore indireta pode ser encontrada por uma cadeia de sub-árvores diretas. Assim, mesmo que apenas se aplique diretamente às sub-árvores diretas, ainda se aplica indiretamente a todas as sub-árvores (e, portanto, todos os nós).

Árvore balanceada é uma árvore cuja altura é de ordem de tronco (número de elementos na árvore).

height = O(log(n))
O, as in asymptotic notation i.e. height should have same or lower asymptotic
growth rate than log(n)
n: number of elements in the tree

A definição dada "uma árvore é balanceada de cada sub-árvore é balanceada e a altura das duas sub-árvores difere no máximo uma" é seguida por árvores AVL. Como as árvores AVL são balanceadas, mas nem todas as árvores balanceadas são árvores AVL, as árvores balanceadas não têm esta definição e os nós internos podem ser desequilibrados nelas. No entanto, as árvores AVL exigem que todos os nós internos sejam equilibrado.

O objectivo da árvore balanceada é atingir a folha num mínimo de traversal (altura mínima). O grau da árvore é o número de ramos menos 1. Uma árvore balanceada pode não ser binária.