5 tipos de árvore binária explicados [com ilustrações]

Na ciência da computação, várias estruturas de dados ajudam a organizar os dados em diferentes formas. Entre elas, as árvores são estruturas de dados abstratas amplamente utilizadas que simulam uma estrutura de árvore hierárquica. Uma árvore geralmente tem um valor raiz e subárvores que são formadas pelos nós filhos de seus nós pais. As árvores são estruturas de dados não lineares.

Uma estrutura de dados de árvore geral não tem limitação no número de nós filhos que ela pode conter. No entanto, este não é o caso de uma árvore binária. Este artigo aprenderá sobre uma estrutura de dados de árvore específica – árvore binária e tipos de árvore binária .

O que é estrutura de dados de árvore binária?

Uma árvore binária é uma estrutura de dados não linear do tipo árvore com um máximo de dois filhos para cada pai. Cada nó em uma árvore binária tem uma referência esquerda e direita junto com o elemento de dados. O nó no topo da hierarquia de uma árvore é chamado de nó raiz. Os nós que contêm outros subnós são os nós pais.

Um nó pai tem dois nós filhos: o filho esquerdo e o filho direito. Hashing, roteamento de dados para tráfego de rede, compactação de dados, preparação de heaps binários e árvores de pesquisa binárias são alguns dos aplicativos que usam uma árvore binária.

Terminologias associadas a Árvores Binárias e Tipos de Árvores Binárias

• Nó: Representa um ponto de terminação em uma árvore.
• Raiz: o nó mais alto de uma árvore.
• Pai: Cada nó (além da raiz) em uma árvore que possui pelo menos um subnó próprio é chamado de nó pai.
• Filho: Um nó que veio imediatamente de um nó pai ao se afastar da raiz é o nó filho.
• Nó Folha: São nós externos. Eles são os nós que não têm filhos.
• Nó interno: como o nome sugere, são nós internos com pelo menos um filho.
• Profundidade de uma árvore: O número de arestas do nó da árvore até a raiz é.
• Altura de uma Árvore: É o número de arestas do nó até a folha mais profunda. A altura da árvore também é considerada a altura da raiz.

Como você já está familiarizado com as terminologias associadas à árvore binária e os tipos de árvore binária, é hora de entender os componentes da árvore binária . Confira nossos cursos de ciência de dados para aprender a fundo sobre estrutura e componentes binários.

Componentes da árvore binária

Existem três componentes de árvore binária . Cada nó de árvore binária tem esses três componentes associados a ele. Torna-se um conceito essencial para os programadores entenderem esses três componentes da árvore binária:

1. Elemento de dados
2. Ponteiro para a subárvore esquerda
3. Ponteiro para a subárvore direita

Fonte

Esses três componentes de árvore binária representam um nó. Os dados residem no meio. O ponteiro esquerdo aponta para o nó filho, formando a subárvore esquerda. O ponteiro direito aponta para o nó filho à sua direita, criando a subárvore direita.

Leia: Principais perguntas de estimativa e métodos informativos para ciência de dados

Tipos de Árvores Binárias

Existem vários tipos de árvores binárias e cada um desses tipos de árvores binárias possui características únicas. Aqui estão cada um dos tipos de árvore binária em detalhes:

1. Árvore Binária Completa

É um tipo especial de árvore binária que tem zero filhos ou dois filhos. Isso significa que todos os nós nessa árvore binária devem ter dois nós filhos de seu nó pai ou o nó pai é ele próprio o nó folha ou o nó externo.

Em outras palavras, uma árvore binária completa é uma árvore binária única onde cada nó, exceto o nó externo, tem dois filhos. Quando contém um único filho, essa árvore binária não será uma árvore binária completa. Aqui, a quantidade de nós folha é igual ao número de nós internos mais um. A equação é como L=I+1, onde L é o número de nós folha e I é o número de nós internos.

Aqui está a estrutura de uma árvore binária completa:

2. Árvore Binária Completa

Uma árvore binária completa é outro tipo específico de árvore binária onde todos os níveis da árvore são preenchidos inteiramente com nós, exceto o nível mais baixo da árvore. Além disso, no último ou no nível mais baixo dessa árvore binária, cada nó deve residir no lado esquerdo. Aqui está a estrutura de uma árvore binária completa:

3. Árvore Binária Perfeita

Uma árvore binária é dita 'perfeita' se todos os nós internos têm estritamente dois filhos, e cada nó externo ou folha está no mesmo nível ou na mesma profundidade dentro de uma árvore. Uma árvore binária perfeita com altura 'h' tem 2h – 1 nó. Aqui está a estrutura de uma árvore binária perfeita:

4. Árvore Binária Balanceada

Uma árvore binária é dita 'balanceada' se a altura da árvore for O(logN), onde 'N' é o número de nós. Em uma árvore binária balanceada, a altura das subárvores esquerda e direita de cada nó deve variar em no máximo um. Uma árvore AVL e uma árvore vermelho-preta são alguns exemplos comuns de estrutura de dados que podem gerar uma árvore de busca binária balanceada. Aqui está um exemplo de uma árvore binária balanceada:

5. Árvore Binária Degenerada

Uma árvore binária é considerada uma árvore binária degenerada ou uma árvore binária patológica se cada nó interno tiver apenas um único filho. Essas árvores são semelhantes a uma lista vinculada em termos de desempenho. Aqui está um exemplo de uma árvore binária degenerada:

Benefícios de uma árvore binária

• A operação de busca em uma árvore binária é mais rápida em comparação com outras árvores
• Apenas dois percursos são suficientes para fornecer os elementos em ordem ordenada
• É fácil pegar os elementos máximos e mínimos
• A travessia de grafos também usa árvores binárias
• A conversão de diferentes expressões de prefixo e postfix é possível usando árvores binárias

Leia também: Árvores de decisão em aprendizado de máquina: funções, classificação, prós e contras

Conclusão

A árvore binária é uma das árvores mais utilizadas na estrutura de dados. Cada um dos tipos de árvore binária tem suas características únicas. Essas estruturas de dados têm requisitos específicos em ciência da computação aplicada. Esperamos que este artigo sobre tipos de árvores binárias tenha sido útil. O upGrad oferece vários cursos em ciência de dados, aprendizado de máquina, big data e muito mais.

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.