4 Tipos de Árvores na Estrutura de Dados Explicados: Propriedades e Aplicações

O que é uma árvore na estrutura de dados?

Uma árvore é um tipo de estrutura de dados que representa dados hierárquicos. Possui uma estrutura não linear composta por nós conectados por arestas. Entre os outros tipos de estruturas de dados que realizam operações em uma estrutura de dados linear, a complexidade aumenta com o aumento do tamanho dos dados. No entanto, a estrutura de dados em árvore fornece acesso mais rápido aos dados que não são lineares. Disponibilidade dos vários tipos de estruturas de dados e dos algoritmos a eles associados, o desempenho da tarefa tornou-se uma forma fácil e eficiente.

Algumas terminologias associadas às árvores na estrutura de dados são:

• Nó : o nó é uma entidade em uma estrutura de dados em árvore que contém uma chave ou um valor e ponteiros para seus nós filhos.
• Nó filho : Um nó filho é o descendente de qualquer nó.
• Nós folha: os nós que não possuem nós filhos e são os nós mais inferiores em uma árvore. Eles também são chamados de nós externos.
• Raiz : É o ponto mais alto de uma árvore.
• Nó interno : O nó que tem pelo menos um nó filho.
• Aresta: Uma aresta refere-se à conexão entre quaisquer dois nós em uma árvore.
• Altura de um nó: Número de arestas do nó até a folha mais profunda.
• Profundidade de um nó : Número de arestas da raiz ao nó.
• Altura de uma árvore : Altura do nó raiz.
• Grau de um nó : Número total de ramificações para esse nó.
• Floresta: Uma coleção de árvores disjuntas.

Tipos de árvore

1. Árvore binária

A árvore binária é um tipo de estrutura de dados de árvore em que cada nó pai tem no máximo dois nós filhos. Como o nome sugere, binário significa dois, portanto, cada nó pode ter 0, 1 ou 2 nós. Uma estrutura de dados de árvore binária é mostrada na Figura 1. O nó 1 na árvore contém dois ponteiros, um para cada nó filho. O nó 2 novamente tem dois ponteiros para os dois nós filhos. Enquanto os nós 3, 5 e 6 são nós folha e, portanto, possuem ponteiros nulos nas partes esquerda e direita.

Figura 1: Uma representação de uma árvore binária ( https://www.javatpoint.com/binary-tree ).

Propriedades de uma árvore binária

• O número máximo de nós em cada nível de I é 2 i .
• A altura da árvore na Figura 1 é 3, o que significa que o número máximo de nós será (1+2+4+8) =15.

• Na altura h, o número máximo de nós possível é (20 + 21 + 22+….2h) = 2h+1 -1.

• Na altura h, o número mínimo de nós possível é igual a h+1.

• Um número mínimo de nós representará uma árvore com altura máxima e vice-versa.

Mesmo as árvores binárias podem ser divididas nos seguintes tipos de árvore:

• Árvore binária completa: É um tipo especial de árvore binária. Nesta estrutura de dados em árvore, cada nó pai ou um nó interno tem dois filhos ou nenhum nó filho.
• Árvore binária perfeita: neste tipo de estrutura de dados em árvore , cada nó interno tem exatamente dois nós filhos e todos os nós folha estão no mesmo nível.
• Árvore binária completa: Assemelha-se à árvore binária completa com algumas diferenças.
• Cada nível está completamente preenchido.
• Os nós folha se inclinam para a esquerda da árvore.
• Não é um requisito para o último nó folha ter o irmão certo, ou seja, uma árvore binária completa não precisa ser uma árvore binária completa.
• Árvore degenerada ou patológica: Essas árvores têm um único filho à esquerda ou à direita do nó pai.
• Árvore binária distorcida: É uma árvore patológica ou degenerada onde a árvore é dominada pelos nós esquerdos ou pelos nós direitos. Portanto, existem dois tipos de árvores binárias assimétricas, ou seja, a árvore binária assimétrica à esquerda ou a árvore binária assimétrica à direita.
• Árvore binária balanceada: A diferença entre a altura da subárvore esquerda e direita para cada nó é 0 ou 1.

2. Árvore de Pesquisa Binária

Essas estruturas de árvore não são lineares e um nó está conectado a vários nós. O nó pode ser conectado a no máximo dois nós filhos. É chamada de árvore de busca binária porque:

• Cada nó tem no máximo dois nós filhos.
• Ele pode ser usado para pesquisar um elemento em tempo 0(log(n)) e, portanto, conhecido como árvore de pesquisa.

Figura: Um exemplo de uma árvore de pesquisa binária ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

As propriedades de uma árvore de busca binária são:

• O valor em todos os nós de uma subárvore esquerda deve ser menor que o valor no nó raiz.
• O valor em todos os nós de uma subárvore direita deve ser maior que o valor no nó raiz.

3. Árvore AVL

As árvores AVL são os tipos ou variantes de uma árvore binária. Ele consiste em propriedades tanto do binário quanto de uma árvore de busca binária. Inventadas por Adelson Velsky Lindas, essas árvores são auto-equilibradas, o que significa que a altura da subárvore esquerda e da subárvore direita é equilibrada. Esse equilíbrio é medido em termos de um fator de equilíbrio.

Fator de equilíbrio:

• É a diferença entre a subárvore esquerda e a subárvore direita.
• O valor de um fator de balanceamento deve ser 0, -1 ou 1. Portanto, cada nó de uma árvore AVL deve consistir em um valor de fator de balanceamento, ou seja, 0, -1 ou 1.
• Fator de Equilíbrio = (Altura da Subárvore Esquerda - Altura da Subárvore Direita)
• Uma árvore AVL é dita balanceada se o fator de balanceamento de cada nó estiver entre -1 e 1.

Valores de nós diferentes de -1 a 1 em uma árvore AVL representarão uma árvore não balanceada que precisa ser balanceada.

• Se um nó tiver um fator de equilíbrio de 1, significa que a subárvore esquerda está um nível acima da subárvore direita.
• Se um nó tiver um fator de equilíbrio de 0, significa que a altura da subárvore esquerda e da subárvore direita é igual.
• Se um nó tiver um fator de equilíbrio de -1, significa que a subárvore direita está um nível acima da subárvore esquerda ou a subárvore esquerda está um nível abaixo da subárvore direita.

4. Árvore B

B Tree é uma forma mais generalizada de uma árvore de busca binária. Também é conhecida como a árvore m way balanceada em altura, onde m é a ordem da árvore. Cada nó da árvore pode ter mais de uma chave e mais de dois nós filhos. No caso de uma árvore binária, os nós folha podem não estar no mesmo nível. No entanto, no caso de uma Árvore B, todos os nós folha devem estar no mesmo nível.

Propriedades de uma árvore B:

• As chaves são armazenadas em ordem crescente para cada nó x.
• Um valor booleano “x.leaf” existe em cada nó, o que é verdadeiro se x for uma folha.
• Os nós internos devem ter no máximo “n-1” chaves, onde n é a ordem da árvore. Ele também deve ter um ponteiro para cada criança.
• Todos os nós terão no máximo n filhos e pelo menos n/2 filhos, exceto o nó raiz.
• Os nós folha da árvore têm a mesma profundidade.
• O nó raiz terá no mínimo 1 chave e pelo menos dois filhos.
• Se n ≥ 1, então para qualquer árvore B de n chaves de altura h e grau mínimo t ≥ 2, h ≥ logt (n+1)/2.

Formulários

• A árvore Binary Search pode ser aplicada para pesquisar um elemento em um conjunto de elementos.
• Árvores de heap são usadas para classificação de heap.
• Roteadores modernos usam um tipo de árvore chamada Tries para armazenar informações de roteamento.
• As B-Trees e as T-Trees são usadas principalmente por bancos de dados populares para armazenar seus dados.
• Uma árvore de sintaxe é usada pelos compiladores para validar a sintaxe de cada programa escrito.

Conclusão

As estruturas de dados fornecem uma maneira organizada de armazenar os dados para fácil gerenciamento e manuseio eficaz. Existem vários tipos de estruturas de dados para diferentes tipos de dados. Com base no tipo de dados que precisam ser armazenados, eles são escolhidos pelo usuário.

Árvores são tipos de tais estruturas de dados onde o tipo hierárquico de dados pode ser armazenado. Os dados são armazenados nos nós que às vezes armazenam a referência para outros nós chamados nós filhos.

Com base no número de nós filhos, as árvores podem ser classificadas em vários tipos, conforme mencionado no artigo. Com base na disposição dos nós nos tipos de árvore, cada estrutura de árvore tem propriedades associadas. Com os diferentes tipos de operação que podem ser realizados pelas diferentes classes de árvores, esse tipo de estrutura de dados tem encontrado aplicações em algoritmos de ordenação e armazenamento de dados.

Um Programa Executivo PG em Desenvolvimento de Software - Especialização em Desenvolvimento Full Stack, com curadoria de upGrad & IIIT-Bangalore, pode ajudá-lo a melhorar seu perfil e garantir melhores oportunidades de emprego como programador.