Árvores pt I: Teoria, Introdução, Binárias e AVL.

Árvores são estruturas de dados que nos proporcionam controles otimizados sobre uma coleção de dados. Podemos usá-la para prover uma pesquisa mais rápida de um determinado elemento, bem como apresentações diferenciadas dos dados (listagens em pré-ordem, in-ordem e pós-ordem). Depois analisaremos isto com mais detalhes.

As árvores proporcionam vantagens tanto na listagem, e em alguns casos na remoção e inserção de elementos também(quando a mesma não for balanceada a cada operação).

Então, ela nada mais é do que um conjunto de elementos denominados vértices. Na verdade há muito o que conhecer sobre seus elementos e estrutura, e é isto que eu pretendo explicar neste post.

Mas antes vejamos algumas aplicações da mesma:

• Banco de Dados
• Inteligência Artificial
• Avaliação de expressões Lógicas e/ou Matemáticas

Seus elementos:

• Raiz: Elemento mais ao alto, o primeiro elemento de referência da árvore.
• Nó ou Vértice: o elemento da árvore.
• Folha: últimos elementos, os mais profundos, e que não tem filhos.
• Aresta: Conector dos elementos, indicando sua relação.
• Pai: Elemento que contém vértices conectados a ele em profundidade mais elevada.
• Filho: Elemento que contém um vértice superior vinculado a ele.

Sua estrutura:

• Sub-árvore: Um pedaço de uma árvore analisado separadamente.
• Floresta: Conjunto de árvores e/ou sub-árvores.
• Altura: Quantidade de nós máxima ao seguir por um caminho (se nos referirmos a altura de uma árvore, então considerasse o maior caminho da mesma).
• Profundidade: Quantidades de arestas até um determinado nó (se nos referirmos a uma árvore, então considerasse o maior caminho da mesma).
• Grau: quantidade de filhos de uma vértice.

Árvore Binária: É caracterizada por vértices que podem ter no máximo dois filhos. Por padrão, se o filho for menor do que o pai ele deve ser alocado à esquerda. Se o filho for maior que o pai, então é alocado a direita. Com isso ganhamos agilidade ao procurar e inserir um elemento, pois temos um caminho mais otimizado para percorrer!

Árvore AVL: É uma árvore binária, porém balanceada, ou seja, tentando fazer com que o caminho até suas folhas sejam menores possíveis e de alturas e profundidades parecidas.

Ambas as árvores (Binária e AVL) tratarei mais detalhadamente em outro post.

Por hora, fica o resumo da ópera em slides:

Árvores por Eduardo Spaki

Ficam alguns exercícios conceituais:

Dada a figura ao acima:

1. Qual a altura da árvore?
2. Qual o filho à esquerda do nó “b” ?
3. Qual o filho à direita do nó “a”?
4. Qual a profundidade do nó “i”?
5. Quem são as folhas?
6. Quem nós são pais de que nós?
7. Qual é o grau de cada nó?
8. Qual é a altura da árvore?
9. Admita que o vértice “e” é a raiz, e redesenhe a árvore com a raiz em cima.
10. Admita que o vértice “f” é a raiz, e redesenhe a árvore com a raiz em cima.
11. Esta árvore é binária?

Espero que tenham gostado :)