Introdução às árvores na estrutura de dados
Antes de entender os Tipos de Árvores na Estrutura de Dados, primeiro estudaremos as árvores na Estrutura de Dados. A árvore no campo do computador também é chamada de árvore do mundo real; no entanto, a diferença entre o mundo real e a árvore do campo de computação é que ela é visualizada de cabeça para baixo e enraíza sobre ela e ramifica da raiz para as folhas das árvores. Entre vários aplicativos do mundo real, a estrutura de dados em árvore é usada, pois pode demonstrar relacionamentos entre diferentes nós com a hierarquia pai-filho. Também é chamada de estrutura hierárquica de dados por causa disso. É o mais popular para simplificar e acelerar a pesquisa e classificação. É considerada uma das estruturas de dados mais fortes e avançadas. Uma árvore é uma representação da estrutura de dados não linear. Uma árvore pode ser mostrada usando diferentes tipos de dados definidos pelo usuário ou primitivos. Podemos usar matrizes, classes de listas conectadas ou outros tipos de estruturas de dados para implementar a árvore. É um grupo de nós que estão inter-relacionados. Os nós são anexados às bordas para demonstrar o relacionamento.
Relações em uma árvore: No diagrama acima, P é a raiz da árvore e P é o pai de Q, R e S. Q é o filho de P. Portanto, Q, R e S são irmãos. Considerando que P é avô de A, B, C, D e E.
O que são árvores?
Uma árvore é uma estrutura de dados hierárquica que naturalmente armazena as informações de maneira hierárquica. A estrutura de dados da árvore é uma das mais eficientes e maduras. Os nós conectados pelas bordas são representados.
Propriedades da árvore: Toda árvore possui um nó raiz específico. Cada nó da árvore pode ser cruzado por um nó raiz. É chamado raiz, pois a árvore era a única raiz. Toda criança tem apenas um pai, mas o pai pode ter muitos filhos.
Tipos de árvores na estrutura de dados
Abaixo estão os tipos de árvores em uma estrutura de dados:
1. Árvore Geral
Se nenhuma restrição for colocada na hierarquia da árvore, uma árvore será chamada de árvore geral. Cada nó pode ter um número infinito de filhos na Árvore Geral. A árvore é o superconjunto de todas as outras árvores.
2. Árvore binária
A árvore binária é o tipo de árvore na qual a maioria dos dois filhos pode ser encontrada para cada pai. As crianças são conhecidas como a criança esquerda e a criança certa. Isso é mais popular do que a maioria das outras árvores. Quando certas restrições e características são aplicadas em uma árvore binária, várias outras, como árvore AVL, BST (árvore de pesquisa binária), árvore RBT, etc. também são usadas. Quando avançarmos, explicaremos todos esses estilos em detalhes.
3. Árvore de Pesquisa Binária
Árvore de Pesquisa Binária (BST) é uma extensão de árvore binária com várias restrições opcionais. O valor filho esquerdo de um nó no BST deve ser menor ou igual ao valor pai e o valor filho direito deve sempre ser maior ou igual ao valor pai. Essa propriedade Árvore de Pesquisa Binária o torna ideal para operações de pesquisa, pois podemos determinar com precisão em cada nó se o valor está na subárvore esquerda ou direita. É por isso que a Árvore de Pesquisa é nomeada.
4. Árvore AVL
A árvore AVL é uma árvore de pesquisa binária que se equilibra. Em nome dos inventores Adelson-Velshi e Landis, o nome AVL é dado. Esta foi a primeira árvore que se equilibrou dinamicamente. Um fator de balanceamento é alocado para cada nó na árvore do AVL, com base no equilíbrio ou não da árvore. A altura dos filhos do nó é no máximo 1. AVL vine. Na árvore AVL, o fator de equilíbrio correto é 1, 0 e -1. Se a árvore tiver um novo nó, ele será girado para garantir que a árvore esteja equilibrada. Será então girado. Operações comuns, como visualização, inserção e remoção, levam tempo O (log n) na árvore do AVL. É aplicado principalmente ao trabalhar com operações de pesquisas.
5. Árvore Vermelho-Preta
Outro tipo de árvore de balanceamento automático é vermelho-preto. O nome vermelho-preto é dado porque a árvore Vermelho-preto tem vermelho ou Preto pintado em cada nó, de acordo com as propriedades da árvore vermelho-preto. Mantém o equilíbrio da floresta. Mesmo que essa árvore não seja totalmente equilibrada, a operação de pesquisa leva apenas tempo O (log n). Quando os novos nós são adicionados na Árvore Vermelho-Preto, os nós serão rotacionados novamente para manter as propriedades da Árvore Vermelho-Preto.
6. Árvore N-ária
O número máximo de filhos nesse tipo de árvore que pode ter um nó é N. Uma árvore binária é uma árvore de dois anos, como no máximo 2 filhos em cada nó da árvore binária. Uma árvore N-ária completa é uma árvore na qual os filhos de um nó são 0 ou N.
Vantagens da Árvore
Agora vamos entender as vantagens da árvore:
- A árvore reflete nas conexões estruturais dos dados.
- A árvore é usada para hierarquia.
- Oferece um procedimento eficiente de busca e inserção.
- As árvores são flexíveis. Isso permite que as subárvores sejam realocadas com o mínimo esforço.
Conclusão - Tipos de árvores na estrutura de dados
Então, aqui neste artigo, vimos o que é estrutura de árvore, quais são os diferentes tipos de árvores na estrutura de dados e seus benefícios. Espero que você tenha uma idéia de algumas das árvores comuns na estrutura dos dados.
Artigos recomendados
Este é um guia para Tipos de árvores na estrutura de dados. Aqui discutimos o que são árvores, 6 tipos de árvores na estrutura de dados, com vantagens. Você também pode consultar nossos outros artigos relacionados para saber mais -
- Pipeline de dados da AWS
- Armazenamento de Dados Oracle
- Banco de Dados Multidimensional
- Estrutura de dados Java Interview Questions