2.1 Componentes principais de uma árvore
Árvore é um tipo especial de grafo, que é
acíclico e
conexo. Em uma árvore, existe um único
caminho entre qualquer par de nós, o que torna sua estrutura
hierárquica.
Componentes principais de uma árvore:
1. Nós:
- Elementos principais de uma árvore, que contêm dados.
- Por exemplo, cada círculo no diagrama representa um nó.
2. Raiz:
- Nó que não tem nós pais. É o ponto inicial da árvore.
- Por exemplo, o nó superior no diagrama.
3. Folhas:
- Nós que não têm nós filhos. Eles estão nas "pontas" da árvore.
- Por exemplo, os nós na parte inferior do diagrama.
4. Arestas:
- Conexões entre os nós. Determinam as relações pai-filho entre nós.
- Por exemplo, as linhas que conectam os nós no diagrama.
5. Subárvores:
- Qualquer subconjunto da árvore, consistindo de um nó e todos os seus descendentes.
- Por exemplo, um ramo da árvore que se origina de um nó.
Características importantes de uma árvore:
1. Altura da árvore:
- Comprimento do caminho da raiz até a folha mais distante.
- Por exemplo, o número de níveis no diagrama.
2. Profundidade do nó:
- Comprimento do caminho da raiz até um determinado nó.
- Por exemplo, o número de níveis da raiz até um nó específico.
2.2 Árvores binárias
Podemos identificar diferentes tipos de árvores. Vamos começar com as mais simples.
Árvore binária é uma árvore na qual cada nó tem no máximo dois nós filhos, chamados de filho esquerdo e filho direito.
Exemplo de uma árvore binária:
Tipos especiais de árvores binárias:
Árvore binária completa:
Todos os níveis da árvore, exceto o último, estão completamente preenchidos, e todos os nós do último nível estão o mais à esquerda possível.
Árvore binária perfeita:
Todos os nós internos têm exatamente dois nós filhos, e todas as folhas estão no mesmo nível.
Árvore binária balanceada:
A diferença de altura das subárvores de qualquer nó não é superior a 1.
Árvore binária de busca:
Para qualquer nó, sua subárvore esquerda contém apenas nós com valores menores, e a subárvore direita contém apenas nós com valores maiores.
2.3 Árvores n-árias
Árvore n-ária é uma árvore na qual cada nó pode ter no máximo n nós filhos.
Tipos especiais de árvores n-árias:
1. Árvore ternária (Ternary Tree):
Cada nó pode ter no máximo três nós filhos.
2. Árvore k-ária (k-ary Tree):
Cada nó pode ter no máximo k nós filhos.
Exemplo de 3-ária árvore (cada nó pode ter no máximo três nós filhos):
2.4 Exemplos de uso de árvores
1. Sistema de arquivos
Aplicação das árvores: Representação da estrutura hierárquica de arquivos e pastas em um sistema operacional.
O nó raiz representa o diretório raiz, os nós internos representam as pastas, e as folhas representam os arquivos. As operações incluem criar, excluir e mover arquivos e pastas.
2. Árvore de decisão
Aplicação das árvores: Análise e aprendizado de máquina para tomada de decisões.
Os nós internos representam perguntas ou condições, os galhos representam respostas possíveis, e as folhas representam decisões ou ações finais. Por exemplo, diagnóstico de doenças na medicina com base em sintomas.
3. Documento XML/HTML
Aplicação das árvores: Representação estruturada de dados no formato XML ou HTML.
O nó raiz representa o documento inteiro, os nós internos representam as tags e elementos, e as folhas representam nós de texto e atributos. Isso ajuda na análise e manipulação do conteúdo dos documentos.
4. Estrutura organizacional
Aplicação das árvores: Representação da hierarquia em organizações e empresas.
O nó raiz representa o CEO, os nós internos representam os gerentes e departamentos, e as folhas representam os funcionários. Isso ajuda a visualizar e gerenciar a estrutura organizacional.
5. Jogo de xadrez
Aplicação das árvores: Representação de movimentos possíveis no jogo.
O nó raiz representa o estado inicial do jogo, os nós internos representam os movimentos possíveis, e as folhas representam os estados finais do jogo. Isso ajuda no planejamento de estratégias e na tomada de decisões em programas de xadrez.
GO TO FULL VERSION