Definição de uma árvore balanceada

100

Estou apenas pensando se alguém pode esclarecer a definição de uma árvore balanceada para mim. Eu tenho que "uma árvore é equilibrada se cada subárvore estiver equilibrada e a altura das duas subárvores diferir em no máximo uma.

Peço desculpas se esta é uma pergunta estúpida, mas essa definição se aplica a todos os nós, desde as folhas de uma árvore ou apenas às subárvores esquerda e direita imediatamente fora da raiz? Acho que outra maneira de enquadrar isso seria: é possível que os nós internos de uma árvore fiquem desequilibrados e toda a árvore permaneça balanceada?

Mark Soric
fonte
6
Só queria acrescentar que estamos falando sobre Comp. Definição científica de uma subárvore: Uma subárvore de uma árvore T é uma árvore que consiste em um nó em T e todos os seus descendentes em T. Para uma definição matemática regular (um subgráfico de uma árvore que é em si uma árvore) não é verdade .
TT_

Respostas:

123

A restrição é geralmente aplicada recursivamente a todas as subárvores. Ou seja, a árvore só é equilibrada se:

  1. As alturas das subárvores esquerda e direita diferem em no máximo um, E
  2. A subárvore esquerda é equilibrada, E
  3. A subárvore certa está equilibrada

De acordo com isso, a próxima árvore é equilibrada:

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

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

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

Dito isso, a restrição específica do primeiro ponto depende do tipo de árvore. O listado acima é o típico para árvores AVL .

Árvores vermelho-escuras , por exemplo, impõem uma restrição mais suave.

comocomocomocomo
fonte
50

Existem várias maneiras de definir "Equilibrado". O objetivo principal é manter a profundidade de todos os nós O(log(n)).

Parece-me que a condição de equilíbrio de que você estava falando é para a árvore AVL .
Aqui está a definição formal da condição de equilíbrio da árvore AVL :

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

Próxima pergunta, o que é " altura "?

A " altura " de um nó em uma árvore binária é o comprimento do caminho mais longo desse nó até uma folha.

Existe um caso estranho, mas comum:

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

Por exemplo, o filho esquerdo de 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, um exemplo de árvore balanceada :

        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 é um exemplo de árvore balanceada :

        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)      
CherylG
fonte
1
Observe que esta definição permite subárvores não balanceadas de árvores balanceadas. (por exemplo, estenda o exemplo de árvore balanceada acima adicionando um filho a D e outro a G) Isso é intencional?
gen
2
Não, não faz. " Para qualquer nó em AVL , a altura de sua subárvore esquerda difere no máximo 1 da altura de sua subárvore direita." Se você adicionar um filho a D, B não seguirá a regra acima. Portanto, a árvore não será uma BBT.
John Red de
1
sua resposta é muito prolixa e imprecisa
Marwen Trabelsi
9

Não há diferença entre essas duas coisas. Pense nisso.

Vamos dar uma definição mais simples: "Um número positivo é igual se for zero ou aquele número menos dois é par." Isso diz que 8 é par se 6 for par? Ou isso diz que 8 é igual se 6, 4, 2 e 0 são pares?

Não há diferença. Se ele disser que 8 é mesmo se 6 for par, também dirá que 6 é mesmo se 4 for par. E, portanto, também diz que 4 é igual se 2 for par. E, portanto, diz que 2 é igual se 0 for par. Portanto, se disser que 8 é mesmo se 6 for par, (indiretamente) dirá que 8 é par, se 6, 4, 2 e 0 forem pares.

É a mesma coisa aqui. Qualquer subárvore indireta pode ser encontrada por uma cadeia de subárvores diretas. Portanto, mesmo que se aplique diretamente a subárvores diretas, ainda se aplica indiretamente a todas as subárvores (e, portanto, a todos os nós).

David Schwartz
fonte
1
Digamos que o valor da raiz seja 15. À direita, tenho 16,17,18. Abaixo à esquerda, tenho 14,13,12. É uma árvore equilibrada? A altura de cada subárvore do nó está dentro de um. Mas tome o primeiro nó abaixo da raiz para a direita, ele não tem filhos à esquerda, mas a altura de seus filhos direitos é 2. Portanto, esse nó não está balanceado. Isso é correto?
Mark Soric
1
Corrigir. Portanto, a árvore não está equilibrada.
David Schwartz
1
Portanto, para que uma árvore seja balanceada - todos os nós devem ser balanceados. Beleza - Muito obrigada pela ajuda.
Mark Soric
1
@DavidSchwartz por que estamos tentando usar uma árvore balanceada? por que nos importamos se uma árvore está equilibrada ou não?
Dejell
3
Esta é, de longe, a resposta mais complexa que já vi no SO - para qualquer pergunta. Desculpe dizer isso.
Trevor
4

Árvore balanceada é uma árvore cuja altura é da ordem do 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 é equilibrada de cada subárvore é equilibrada e a altura das duas subárvores difere no máximo em uma" é seguida por árvores AVL.

Visto que as árvores AVL são balanceadas, mas nem todas as árvores balanceadas são árvores AVL, as árvores balanceadas não mantêm essa definição e os nós internos podem ser desequilibrados nelas. No entanto, as árvores AVL requerem que todos os nós internos sejam balanceados.

div
fonte
3

o objetivo da árvore balanceada é atingir a folha em um mínimo de travessia (altura mínima). O grau da árvore é o número de galhos menos 1. Uma árvore balanceada pode não ser binária.

Mohamed ROMDANE
fonte
0
  1. A altura de um nó em uma árvore é o comprimento do caminho mais longo desse nó para baixo até uma folha, contando os vértices inicial e final do caminho.
  2. Um nó em uma árvore terá sua altura balanceada se as alturas de suas subárvores diferirem em não mais do que 1.
  3. Uma árvore tem equilíbrio de altura se todos os seus nós tiverem equilíbrio de altura.
João paulo
fonte