Árvores

Uma ávore é um grafo conectado não cíclico

Grafos não cíclicos mas não conectados são chamados de florestas, e seus subgrafos conectados são chamados de árvores

Árvores tem características não presentes em outros grafos

Ex.: Seu número de pontas é sempre igual ao número total de vértices menos 1

Árvores Enraizadas

Para cada dois vértices de uma árvore, sempre existe um caminho simples que os ligue

Como dois vértices sempre tem um caminho simples entre eles, é possível escolher um vértice para representar uma raiz da árvore, de onde os outros vértices e caminho se originam

O mapa mental abaixo exemplifica essa representação

a

b

c

d

e

Árvores enraizadas tem diversas utilidades na Ciência da Computação. Elas oferecem algoritmos de busca, implementações de dicionários, decrições de hierarquias e mais

Nele, o vértice "a" cumpre o papel de raiz

Vértices de um árvore

Além de "raiz", há outros termos usados para se referir a vértices e grupos de vértices de um árvore. Esses termos são importantes para se compreender o que é dito sobre árvores

Os vértices que fazem parte do caminho de um vértice para a raiz, são chamados de "ancestrais"

Assim, os vértices "a", "b" e "d" são ancestrais de "d"

Nota-se que um vértice é ancestral de si mesmo

Os ancestrais de um vértices não incluindo o próprio vértice são chamados "ancestrais próprios" do vértice

No exemplo, "a" e "b" são os ancestrais próprios tanto de "d" quanto de "e"

Todos os vértices para os quais um vértice v é ancestral são chamados "descendentes" de v

Assim como os ancestrais, os descendentes de um vértice incluem o próprio vértice. Os descendentes de um vértice diferentes de si são os "descendentes próprios" do vértice

O primeiro ancestral próprio no caminho de um vértice à raiz é chamado o "pai" (parent) do vértice, e o vértice é chamado "filho" do pai

Os filhos de um mesmo pai são "irmãos"

Vértices que não tem filhos, as extremidades da árvore, são chamados de "folhas"

"d" e "e" são irmãos, assim como "b" e "c"

"c", "d" e "e" são as folhas da árvore-exemplo

Assim, "a", "b", "c", "d" e "e" são todos descendentes de "a"

No exemplo, "b" é pai de "d" e "e", e "d" e "e" são filhos de b

"b", "c", "d" e "e" são os descendentes próprios de "a"

Uma árvore formada pelos descendentes de um vértice v e os caminhos que os ligam é uma subárvore da original. E o vértice v é a raiz dessa subárvore

Veja uma subárvore de árvore usada nos exemplos

b

d

e

Nessa subárvore, "b" é a raiz

A profundidade de um vértice é o comprimento do seu caminho simples até a raiz

No exemplo, a profundidade de "a" é 0, a de "b" é 1 e a de "d" é 2

A altura de uma árvore é o comprimento da maior caminho simples de uma folha à raiz

No exemplo, a altura é 2, e na subárvore enraizada em "b", a altura é 1

Árvores Ordenadas

Uma árvore ordenada é uma árvore onde todos os filhos de um vértice estão ordenados

Convenciona-se considerar que os filhos são ordenados da esquerda para a direita

Ávores Binárias

Árvore binária é um tipo especial de árvore ordenada na qual todo vértice tem dois filhos no máximo

Esses filhos são chamados filhos esquerdo e direito

A árvore do exemplo é uma árvore binária

Como toda subárvore de uma árvore binária também é uma árvore binária, pode-se observar uma recursão

Árvores de Busca Binárias

Estas são árvores binárias nas quais os filhos esquerdos tem valores menores que seus pais, e os direitos, valores maiores

Elas também podem ser generalizadas para criar "multiway search trees", usadas para acessar grandes agrupamentos de dados de forma eficient

Na computação. elas são implementadas com nódulos

Cada nódulo teria informações correspondentes aos vértices, como um valor de um tipo de dado, e referências para os dois filhos, o primeiro apontando para o filho esquerdo e o segundo, para o direito

Essa representação, no entanto, não é prática para árvores de com números variáveis de filhos

Graças a essa organização, realizar uma busca em uma árvore binária é uma operação simples e de eficiência da classe logarítmica

Começamos a busca verificando se a árvore está vazia. Se estiver, a busca falhou

Se não estiver, verificamos o valor em sua raiz

Se o valor na raiz for igual ao valor buscado, a busca foi bem sucedida

Se o valor na raiz for maior que o valor buscado, recomeçamos a busca na subárvore enraizada no filho esquerdo

Se o valor na raiz for menor que o valor buscado, recomeçamos a busca na subárvore enraizada no filho direito

Vemos aqui a natureza recursiva da árvore binária

Como a altura da árvore diminui a cada iteração, essa operação de busca se qualifica como um algoritmo de decrescimento de tamanho variável

A operação de inserção de novos itens segue a mesma lógica

Atravessando Árvores Binárias

Para facilitar a visualização e cáluclo de eficiência de algoritmos que percorrem uma árvore, pode-se considerar as subárvores vazias (filhos faltantes) de uma árvore como nódulos especiais

Estes nódulos são chamados externos, e os nódulos regulares da árvore, internos

Com isso em mente, podemos avaliar o algoritmo que determina a altura de uma árvore

A altura de uma árvore é o comprimento do maior caminho da raiz até uma folha

Assim, para cada vértice a partir da raiz, verificamos se a árvore é vazia. Se for, o algoritmo encerra

Se a árvore não for vazia, sua altura é a maior altura entre as subárvores direita e esquerda mais 1 (por causa da raiz)

O algoritmo se repete recursivamente até alcançar os nódulos externos

O algoritmo compara a raiz, para determinar se ela é vazia, um número de vezes igual ao número de nódulos internos e externos

Como todo nódulo da árvore além da raiz é um dos filhos de outro nódulo, esse valor é igual ao número de nódulos internos da ávore mais 1

No algoritmo de busca na árvore binária, não era preciso verificar as duas subárvores de cada árvore, mas em um algoritmo como o para determinar a altura da árvore, isso é necessário

Em algoritmos com essa necessidade, as subárvores podem ser percorridas de três formas

Preordem

Verifica-se a raiz da árvore, então as subárvores esquerda e direita respectivamente

Em ordem

Verifica-se a subárvore esquerda, a raiz, e então, a subárvore direita

Pós ordem

Verifica-se as subárvores esquerda e direita, depois a raiz