5 tipos de árvore binária na estrutura de dados explicados

Uma árvore binária é uma estrutura de dados de árvore não linear que contém cada nó com no máximo 2 filhos. O nome binário sugere o número 2, então qualquer árvore binária pode ter um filho esquerdo e um filho direito.

Um ponteiro descreve uma árvore binária para o nó superior, geralmente conhecido como raiz da árvore. Cada nó em uma árvore binária contém dados, um ponteiro para o filho esquerdo e um ponteiro para o filho direito. Ponteiros são usados ​​para implementar uma árvore binária. O ponteiro raiz denota o primeiro nó na árvore. Para criar uma árvore binária, você precisa primeiro criar um nó.

Depois de estar familiarizado como que é árvore binária na estrutura de dados , você também precisa conhecer as operações básicas realizadas em uma árvore binária.Você pode executar funções como inserir um elemento, remover um elemento, procurar um elemento e percorrer a árvore binária.

Qualquerárvore binária na estrutura de dados é usada de duas maneiras diferentes na computação.Em primeiro lugar, eles são usados ​​para acessar nós dependendo de rótulos ou valores específicos vinculados a cada nó. Em segundo lugar, eles são usados ​​como representações de dados com uma estrutura ramificada relevante.

Antes de passar pelos váriostipos de árvore binária , primeiro vamos nos familiarizar com as terminologias usadas em uma árvore binária.

Nó: contém um valor de dados em uma árvore binária.

Raiz: o nó mais alto em qualquer árvore binária é chamado de raiz de uma árvore.

Tamanho: Denota o número de nós em uma árvore binária.

Nó pai: Um nó em uma árvore binária com um filho.

Nó filho: É um nó que se origina de um nó pai se afastando da raiz da árvore binária.

Nó interno: É um nó com pelo menos um filho em uma árvore binária.

Nó Folha: É um nó sem filho.É alternativamente um nó externo.

Profundidade de uma árvore de nós: é calculada no contexto de um determinado nó.É referido como o número de arestas de um determinado nó para a raiz.

Comprimento do caminho interno de uma árvore: Refere-se à soma dos níveis de cada nó interno em uma árvore binária.

Comprimento do caminho externo de uma árvore: é definido como a soma dos níveis de cada nó externo em uma árvore binária.

Altura do nó em uma árvore: É o número de arestas de um nó específico até o nó folha mais profundo da árvore binária.A altura da raiz sempre será maior que a dos outros nós da árvore binária.

Agora vamos verificar os detalhes de 5tipos de árvore binária.

Tipos de Árvore Binária

1. Árvore binária completa

Essaárvore binária na estrutura de dados também é conhecida pelos nomes -Árvore binária adequada e Árvore binária estrita.É um dostipos mais fundamentais de árvore binária na estrutura de dados.Uma árvore binária completa é definida como uma árvore binária em que cada nó deve ter dois ou nenhum filho.

É alternativamente caracterizado como uma árvore binária em que cada nó compreende dois filhos, exceto os nós folha. Os nós nos quais o endereço do nó raiz é armazenado são chamados de nós filhos da raiz. Esses nós desprovidos de filhos são chamados de nós de folha.

Você precisa percorrer todos os nós para verificar se uma árvore é uma árvore binária. O código retornará “False” se algum nó tiver um filho. Ele retornará “True” se todos os nós tiverem 0 ou 2 filhos.

Aqui estão as propriedades de uma árvore binária completa:

• O número de nós folhas é igual ao número de nós internos + 1. Por exemplo, se o número de nós internos for 4, o número de nós folhas será igual a 5.
• O número máximo de nós e o número de nós em uma árvore binária são iguais. É representado como 2h+1 -1.
• O número mínimo de nós em uma árvore binária completa é 2h-1.
• A altura mínima de uma árvore binária completa é log 2 (n+1) – 1.
• A altura máxima de uma árvore binária completa é h = (n+1)/2.

2. Árvore Binária Perfeita

Uma árvore binária perfeita é um daquelestipos de árvores binárias em que cada nó deve ter 0 ou 2 filhos e o nível de cada nó folha deve ser o mesmo.Em outras palavras, árvores binárias perfeitasna estrutura de dados são definidas como aquelas árvores onde todos os nós internos possuem dois ramos e aqueles nós sem ramos (nós folha) existem no mesmo nível.

Nesse contexto, o nível de um nó é a distância ou altura do nó raiz. Você pode considerar uma árvore binária perfeita como uma árvore binária completa em que o último nível também está completamente ocupado.

Aprendacursos de ciência de dadoson-line nas principais universidades do mundo.Ganhe Programas Executivos de PG, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

3. Árvore binária completa

Uma árvore binária completa é um daqueles tipos de árvore binária na estrutura de dados em que todos os níveis da árvore são totalmente preenchidos.O último nível da árvore binária pode ou não estar completamente preenchido. No entanto, cada nó deve estar localizado na posição mais à esquerda no último nível do nó. Os nós devem ser incluídos a partir da esquerda.

Eles são um dostipos essenciais de árvores binárias porque oferecem a melhor relação entre o número de nós e a altura de uma árvore.

Aqui estão as principais propriedades de uma árvore binária completa:

• O número máximo de nós é 2 h+1 – 1.
• O número mínimo de nós é 2 h .
• A altura mínima é log 2 (n+1) – 1.

4. Árvore Binária Balanceada

Em árvores binárias balanceadas, a altura de uma árvore é log 2 do número total de nós. Suponha que a altura da árvore seja h e o número total de nós da árvore seja n. A equação para calcular a altura é h = log(n). A diferença máxima de altura entre uma subárvore direita e uma subárvore esquerda deve ser “1”.

A diferença pode ter outros valores como 0 e -1. Esses tipos de árvores binárias também são chamados de árvores AVL.Um dos exemplos bem conhecidos de árvores binárias balanceadas é a árvore Rubro-Negra.

Você pode implementar o código a seguir para executar uma árvore binária balanceada.

Nó de classe privada {

valor int privado;

Nó privado deixado;

direito de nó privado;

}

public boolean isBalanced(Nó n) {

if (balancedtreeHeight(n) > -1)

retornar verdadeiro;

retorna falso;

}

public int balancedtreeHeight(Nó n) {

se (n == nulo)

retorna 0;

int h1 = balancetreeHeight(n.right);

int h2 = balancetreeHeight(n.left);

se (h1 == -1 || h2 == -1)

retornar -1;

se (Math.abs(h1 – h2) > 1)

retornar -1;

se (h1 > h2)

retornar h1 + 1;

retornar h2 + 1;

}

Confira nossos Programas de Ciência de Dados nos EUA

5. Árvore Binária Degenerada

Uma árvore binária degenerada é um dos tipos menos usados​​de árvore binária de pesquisa .É uma árvore binária em que cada nó possui apenas um filho, ou seja, um filho esquerdo ou direito. Nenhum nó deve ter filhos esquerdo e direito.

Leia nossos artigos populares sobre ciência de dados nos EUA

Conclusão

É essencial entendero que é árvore binária na estrutura de dados se você quiser usá-la para vários aplicativos.A implementação de diferentes funções em árvores binárias pode ajudá-lo a organizar e armazenar dados com eficiência.

Estudar vários tipos de árvores binárias ajuda você a executar operações com mais eficiência na complexidade do tempo. Os fundamentos da ciência de dados, incluindoestrutura de dados de árvore binária, ajudam você a iniciar sua jornada de ciência de dados facilmente.Posteriormente, você pode trabalhar em projetos avançados de ciência de dados para aprimorar suas habilidades e portfólio.

Comece sua jornada de aprendizado de máquina no upGrad

Se você deseja aprender ciência de dados, pode seguir o programa de mestrado em ciência de dados da upGrad . Este curso de 24 meses oferece habilidades como Python, implantação de modelos de ML, processamento de BD usando Spark, análises e estatísticas preditivas e modelos de ML supervisionados e não supervisionados. O curso é adequado para gerentes ambiciosos, graduados em MBA, engenheiros e profissionais em vários domínios.

A conclusão deste curso ajudará você a trabalhar como Engenheiro de Dados, Analista de Big Data, Engenheiro de Machine Learning e Cientista de Dados.