características -chave de uma árvore binária perfeita
Uma árvore binária perfeita (também chamada de árvore binária completa, no sentido de que todos os níveis estão cheios) exibe as seguintes características:
1.
Todos os nós internos têm exatamente dois filhos: Todo nó que não é um nó de folha deve ter um filho esquerdo e uma criança certa.
2.
Todos os nós da folha estão no mesmo nível: A profundidade de todos os nós foliares (nós sem filhos) é idêntica. Isso significa que a árvore está perfeitamente equilibrada.
3.
o número de nós no nível `i` é '2^i`: Onde o nível da raiz é considerado o nível 0.
4.
O número total de nós em uma árvore binária perfeita de altura `h` é` 2^(h+1) - 1` .
5.
altura de uma árvore binária perfeita com `n` nós é` log2 (n+1) - 1` . Isso geralmente é aproximado como `log2 (n)`.
Implicações dessas características: * Uma árvore binária perfeita é inerentemente equilibrada.
* Sua estrutura é altamente previsível e regular.
* É altamente eficiente em termos de espaço, com memória desperdiçada mínima devido a nós não preenchidos.
Detalhes da implementação em java
Veja como você pode implementar uma árvore binária perfeita em Java, concentrando -se em uma estrutura básica e operações principais:
`` `Java
classe PerfectBinaryTree {
Nó da classe estática {
int dados;
Nó esquerdo;
Nó à direita;
Nó (int dados) {
this.data =dados;
this.left =null;
this.right =null;
}
}
Raiz do nó;
int altura; // altura da árvore (número de níveis - 1)
public PerfectBinaryTree (int altura) {
this.Height =altura;
this.root =constructPerfectBinaryTree (0, altura);
}
Node Private ConstructPerFectBinaryTree (Int CurrentLevel, int maxHeight) {
if (CurrentLEvel> maxHeight) {
retornar nulo;
}
// Crie um nó
Nó nó =novo nó ((int) math.pow (2, CurrentLevel)); // Exemplo:use 2^nível como valor do nó
// Crie recursivamente subárvores esquerda e direita
node.left =constructPerfectBinaryTree (CurrentLevel + 1, MaxHeight);
node.right =construtPerfectBinaryTree (CurrentLevel + 1, MaxHeight);
Nó de retorno;
}
// Exemplo:Traversal inorder para verificar a estrutura
public void inOrderTraversal (nó nó) {
if (node! =null) {
inOrderTraversal (node.left);
System.out.print (node.data + "");
inOrderTraversal (Node.right);
}
}
public static void main (string [] args) {
int altura =2; // 3 níveis (raiz + 2 mais)
PerfectBinaryTree PerfectTree =new PerfectBinaryTree (altura);
System.out.println ("inomert transversal:");
PerfectTree.inOrderTraversal (PerfectTree.root); // saída:4 2 5 1 6 3 7
}
}
`` `
Explicação: 1.
`node` classe: * Representa um nó na árvore binária.
* Contém `dados` (um número inteiro neste exemplo),` `esquerda 'e` direita'.
2.
`PerfectBinaryTree` Classe: * `root`:o nó raiz da árvore.
* `altura`:a altura da árvore. A raiz é o nível 0, então uma árvore de altura `h` tem` h+1` níveis.
* `PerfectBinaryTree (int altura)`:o construtor. Ele leva a `altura 'desejada da árvore binária perfeita como entrada. Fundamentalmente, ele chama de "constructperFectBinaryTree ()" para construir a estrutura da árvore recursivamente.
3.
* Esta é a função auxiliar recursiva que constrói a árvore.
* `currentLEvel`:o nível atual que está sendo construído (a partir de 0 para a raiz).
* `maxHeight`:a altura máxima da árvore.
*
Caso base: `CurrentLevel> maxHeight`:se o` CurnLevel` exceder o `maxHeight`, significa que chegamos além dos nós da folha, então retornamos` null`.
*
Etapa recursiva: * Cria um novo `node`. O valor `data` está definido (neste exemplo) como` 2^CurrentLevel 'para demonstrar a estrutura baseada em nível, mas isso pode ser qualquer lógica para inicializar os dados do nó.
* Chama recursivamente `constructPerfectBinaryTree ()` para construir as subárvores esquerda e direita, incrementando o `CrentLevel 'em cada chamada.
* Conecta as subáridas recém -criadas ao nó atual (`node.left` e` node.right`).
* Retorna o nó recém -criado.
4.
`inOrderTraversal (nó nó)`: * Uma travessia de encomenda padrão para imprimir os elementos da árvore. Isso é apenas para demonstração e verificação.
* Esquerda -> raiz -> direita
5. Método
`main`: * Demonstra como criar um objeto `PerfectBinaryTree` com uma altura especificada.
* Chama `inOrderTraversal` para imprimir a árvore.
Considerações importantes: *
Construção: A chave para criar uma árvore binária perfeita é a abordagem de construção recursiva. Ele garante que todos os níveis sejam completamente preenchidos antes de se mudarem para o próximo.
*
Inicialização de dados: O exemplo usa `Math.pow (2, CurrentLevel)` para inicializar os `dados` do nó, mas você pode adaptar isso para preencher a árvore com os dados desejados. A parte essencial é preencher todos os nós em cada nível.
*
imutabilidade (opcional): Se você deseja que a árvore seja imutável após a criação, faça os campos `Node`'s` Data`, `Left` e` Right` 'final` e não forneça nenhum método para alterar a estrutura da árvore após a construção.
*
sem inserção/exclusão (geralmente): Como as árvores binárias perfeitas são inerentemente equilibradas, a inserção direta ou a exclusão dos nós * mantendo a estrutura perfeita * é difícil e geralmente impraticável. Se você precisar inserir/excluir, normalmente precisará reconstruir completamente a árvore após cada operação. As árvores binárias perfeitas são mais frequentemente usadas quando o conjunto de dados é conhecido com antecedência e permanece estático.
*
Representação da matriz: Devido à sua estrutura regular, árvores binárias perfeitas podem ser representadas com eficiência usando matrizes (especialmente se você não precisar inserir/excluir elementos). A raiz está no índice 0. O filho esquerdo do nó no índice `i` está em '2i + 1` e a criança certa está em` 2i + 2`. Isso evita a necessidade de objetos e indicadores explícitos, economizando espaço.
Exemplo:representação da matriz de uma árvore binária perfeita Uma árvore binária perfeita pode ser armazenada com muita eficiência em uma matriz. Considere a árvore com a altura 2:
`` `
1
/ \
2 3
/ \ / \
4 5 6 7
`` `
A representação da matriz seria:
`` `
[1, 2, 3, 4, 5, 6, 7]
`` `
As relações entre pais e filhos estão implícitas nos índices de matriz:
* Pai do nó no índice `i` está no índice` (i-1)/2` (divisão inteira)
* Filho de nó esquerdo no índice `i` está no índice` 2i + 1`
* Filho direito do nó no índice `i` está no índice` 2i + 2`
Essa representação da matriz é incrivelmente eficiente em termos de espaço para árvores binárias perfeitas, porque não há lacunas na matriz.
Quando usar árvores binárias perfeitas: * Quando os dados são conhecidos com antecedência e permanecem estáticos.
* Quando você precisa de uma estrutura de árvore equilibrada garantida.
* Quando você prioriza o acesso rápido a nós com base em sua posição dentro da árvore.
* As estruturas de dados de heap (mini-heaps, max-heaps) são comumente implementadas usando a representação da matriz de uma árvore binária * quase completa *, que está relacionada a uma árvore binária perfeita.
As árvores binárias perfeitas são valiosas para casos de uso específicos, onde sua estrutura rígida e desempenho previsível oferecem vantagens. No entanto, para cenários dinâmicos em que você frequentemente precisa inserir ou excluir nós, outras estruturas de árvores equilibradas, como árvores AVL ou árvores vermelhas-pretas, geralmente são mais adequadas.
