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?
Respostas:
A restrição é geralmente aplicada recursivamente a todas as subárvores. Ou seja, a árvore só é equilibrada se:
De acordo com isso, a próxima árvore é equilibrada:
O próximo não é equilibrado porque as subárvores de C diferem em 2 em sua altura:
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.
fonte
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 :
Próxima pergunta, o que é " altura "?
Existe um caso estranho, mas comum:
Por exemplo, o filho esquerdo de root é
null
:Mais dois exemplos para determinar:
Sim, um exemplo de árvore balanceada :
Não, não é um exemplo de árvore balanceada :
fonte
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).
fonte
Árvore balanceada é uma árvore cuja altura é da ordem do tronco (número de elementos na árvore).
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.
fonte
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.
fonte
fonte