Neste tutorial, você aprenderá sobre a estrutura de dados em árvore. Além disso, você aprenderá sobre os diferentes tipos de árvores e as terminologias usadas em árvores.
Uma árvore é uma estrutura de dados hierárquica não linear que consiste em nós conectados por arestas.
Uma árvore
Por que estrutura de dados em árvore?
Outras estruturas de dados, como matrizes, lista vinculada, pilha e fila, são estruturas de dados lineares que armazenam dados sequencialmente. Para realizar qualquer operação em uma estrutura de dados linear, a complexidade do tempo aumenta com o aumento do tamanho dos dados. Mas, não é aceitável no mundo computacional de hoje.
Diferentes estruturas de dados em árvore permitem um acesso mais rápido e fácil aos dados, pois é uma estrutura de dados não linear.
Terminologias de árvore
Nó
Um nó é uma entidade que contém uma chave ou valor e ponteiros para seus nós filhos.
Os últimos nós de cada caminho são chamados de nós folha ou nós externos que não contêm um link / ponteiro para nós filhos.
O nó com pelo menos um nó filho é chamado de nó interno .
Beira
É o link entre quaisquer dois nós.
Nós e arestas de uma árvore
Raiz
É o nó superior de uma árvore.
Altura de um Nó
A altura de um nó é o número de arestas do nó até a folha mais profunda (ou seja, o caminho mais longo do nó até o nó folha).
Profundidade de um Nó
A profundidade de um nó é o número de arestas da raiz ao nó.
Altura de uma árvore
A altura de uma árvore é a altura do nó raiz ou a profundidade do nó mais profundo.
Altura e profundidade de cada nó em uma árvore
Grau de um Nó
O grau de um nó é o número total de ramos desse nó.
Floresta
Uma coleção de árvores desconexas é chamada de floresta.
Criando floresta de uma árvore
Você pode criar uma floresta cortando a raiz de uma árvore.
Tipos de árvore
- Árvore Binária
- Árvore de pesquisa binária
- AVL Tree
- B-Tree
Tree Traversal
Para realizar qualquer operação em uma árvore, você precisa chegar ao nó específico. O algoritmo de travessia da árvore ajuda a visitar um nó necessário na árvore.
Para saber mais, visite tree traversal.
Aplicativos de árvore
- Árvores de busca binárias (BSTs) são usadas para verificar rapidamente se um elemento está presente em um conjunto ou não.
- Heap é um tipo de árvore usada para classificação de heap.
- Uma versão modificada de uma árvore chamada Tries é usada em roteadores modernos para armazenar informações de roteamento.
- Os bancos de dados mais populares usam árvores B e árvores T, que são variantes da estrutura de árvore que aprendemos acima para armazenar seus dados
- Compiladores usam uma árvore de sintaxe para validar a sintaxe de cada programa que você escreve.
