Á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