TRABALHO SOBRE ÁRVORE

TRABALHO SOBRE ÁRVORE

Introdução As árvores são estruturas de dados que seguem o conceito de hierarquia, e a forma mais simples de defini-la é por recursividade. O objetivo de árvore é estruturar os dados de forma flexível, permitindo a busca binária. O sentido da raiz para as folhas é "para baixo" e o sentido oposto é "para cima". Quando você percorre uma árvore a partir das folhas na direção da raiz, diz-se que você está "subindo" a árvore, e se partir da raiz para as folhas, você está "descendo" a árvore. As árvores binárias AVL é a solução encontrada para resolver um problema pertinente da árvore binária de busca (ABB). Esta solução foi apresentada por 2 soviéticos Adelson-Velskii e Landis. Este tipo de árvore, então ficou conhecida com as iniciais dos seus nomes. Por definição, uma árvore AVL é uma árvore binária de pesquisa onde a diferença de altura entre as subárvores esquerda e direita é no máximo 1 (modular). Assim, para cada nó podemos def inir um fator de balanceamento (FB), que vem a ser um número inteiro igual a FB (nó p) = altura (subárvore direita p) – altura(subárvore esquerda p) Para uma árvore ser AVL os fatores de balanço devem ser necessariamente -1, 0 ou 1.

Algumas definições de Árvores:

Nós ou Nodos: São os itens guardados na árvore.
Raiz: É o primeiro nó e o nó principal da árvore. Há somente um nó em cada árvore, conforme mostra a figura abaixo:
Pais: São nós que vem antes de outros nós;
Filhos: São os nós que vem depois dos nós pais. Um filho precisa de um pai para ser filho, entendeu ? =P
Folhas: São nós que não tem filhos. Eles são os últimos das árvores.
Grau de um nó: Números de filhos de cada nó;
Nível de um nó: Por definição, é zero para a raiz, e, para os demais nós, é o número de “linhas” que ligam o nó à raiz;
Altura de árvore: É o nível mais alto da árvore;
Floresta: Conjunto de árvores disjuntas;
Galhos: Quaisquer nodos que não são raiz e nem folhas de árvore;
Aresta: É a linha que liga dois