Introdução

As árvores são estruturas de dados hierárquicas amplamente utilizadas em ciência da computação para representar relações em que cada elemento pode ter filhos, formando uma estrutura em forma de "ramificação".

Diferente das estruturas lineares (como vetores ou listas), uma árvore permite organizar e acessar dados de maneira mais eficiente em diversas situações, como buscas rápidas, ordenações, representações de hierarquias (como sistemas de arquivos), compiladores, bancos de dados, entre outros.

Conceitos Fundamentais

Termos básicos: Nó (node) - elemento da árvore, Raiz (root) - nó principal, que não possui pai, Folha (leaf) - nó sem filhos, Pai e filho - relação direta entre dois nós conectados, Altura - maior distância da raiz até uma folha, Subárvore - qualquer árvore contida dentro de outra, etc.

Tipos de Árvores

I) Árvore Binária: Cada nó pode ter no máximo dois filhos: o filho à esquerda e o filho à direita.

      8
     / \
    3   10
   / \    \
  1   6    14

II) Árvore Binária de Busca (BST – Binary Search Tree): Na árvore binária de busca, os elementos seguem a seguinte regra:

    • Nós à esquerda contêm valores menores que o nó atual.
    • Nós à direita contêm valores maiores que o nó atual.

Isso permite buscas, inserções e remoções com complexidade média O(log n).