Estruturas tipo árvores

Prévia do material em texto

UNOESC – Universidade do Oeste do Estado de Santa Catarina 
Ciência da Computação 
Docente: Tiago Heineck 
Discente: Alexandre de Bortoli 
Videira, 02 de novembro de 2022 
 
ÁRVORES 
 
Estruturas tipo árvores – não lineares, não sequencial e não estão todos encadeados. 
Uma árvore é composta por um conjunto de nós. 
Árvore binária – conjunto infinito de elementos. Cada elemento é denominado nó. O 
primeiro é conhecido como raiz da árvore. 
Se todo nó que não é folha numa árvore binária tiver subárvores esquerda e direita 
não-vazias, a árvore será considerada uma árvore estritamente binária. 
Para uma árvore ser estritamente binária, todos os nós devem ter 0 ou 2 filhos. 
De maneira recursiva, podemos definir uma árvore binária como sendo: uma árvore 
vazia ou, um nó raiz tendo duas subárvores, identificadas como a subárvore da direita (sad) e 
a subárvore da esquerda (sae). 
Árvores são estruturas de dados adequadas para representação de hierarquias, como 
exemplo de uma estrutura hierárquica temos os arquivos (documentos) que criamos em um 
computador. 
Denominamos um nó r chamado raiz, este pode conter zero ou mais subárvores, que 
são chamados de filhos do nó pai, r. Nós com filhos são comumente chamados de nós internos, 
e nós que não têm filhos são chamados de filhos ou nós externos. 
Por notação textual podemos representar por uma árvore vazia e as não vazias por 
. Uma árvore é representada pelo endereço do nó raiz, uma árvore vazia é 
representada pelo valor NULL. Para tratar a árvore vazia de forma diferente das outras, é 
importante ter uma operação que diz se uma árvore é ou não vazia. 
Na computação as raízes ficam no topo e as folhas no chão. 
Definição de Ancestral e Descendente: supomos que em uma árvore tenhamos nove 
nós (A até I), no topo temos a raiz (A), a sua subárvore esquerda está enraizada em B e sua 
subárvore direita em C. Nessa estrutura ao lado direito temos os nós sem filhos H e I) e ao 
lado esquerdo temos os nós sem filhos (D e G) que chamamos de folha. Com isso, definimos 
por exemplo, como A sendo um ancestral de G e H como sendo um descente de C. Dois 
nós são irmãos se forem filhos esquerdo e direito do mesmo pai. 
O nível de um nó numa árvore binária tem a raiz da árvore como nível 0 e o nível de 
qualquer outro nó na árvore é um nível a mais que o nível de seu pai. 
REPRESENTAÇÃO DE ÁRVORE BINÁRIA EM C 
• Iniciamos com a função structs, também conhecida como Registros, para definir os 
tipos de dados que agrupam variáveis sob um mesmo tipo de dado. Cada nó deve 
armazenar três informações: a informação propriamente dita, no caso um caractere 
(char info), e dois ponteiros para as subárvores, à esquerda (struct arv* esq) e à direita 
(struct arv* dir); 
• A estrutura da árvore é representada por um ponteiro para o nó raiz, dado o ponteiro 
para o nó raiz da árvore, tem-se acesso aos demais nós. 
• Utilizaremos o comando typedef para definirmos o nome para o tipo determinado que 
no caso será o Arv, ficando desse jeito: “typedef struct arv Arv”; 
• Nesse exemplo estamos descrevendo operações que sejam as mais gerais possíveis, 
e para isso necessitamos incluir a criação de uma árvore vazia, representada pelo valor 
NULL. 
• CONSTRUÇÃO DE ÁRVORES NÃO-VAZIAS: operação que cria um nó raiz dadas a 
informação e as duas árvores (esquerda e direita). A estrutura ficará assim: 
Arv* arv_cria (char c1, Arv* sae, Arv* sad) 
Arv* p=(Arv*) malloc2(sizeof3(Arv)); 
p->info = c; 
p->esq = sae; 
p->dir = sad; 
return p; 
} 
• As duas funções para a criação de árvores, criavazia e cria, representam os dois casos 
da definição recursiva de árvore binária: uma árvore binária (Arv* a;) é vazia 
(a=arv_criavazia( );) ou é composta por uma raiz e duas subárvores 
(a=arv_cria(c,sae,sad);). 
• EXIBIR O CONTEÚDO DA ÁRVORE: esta função percorre recursivamente a árvore, 
visitando todos os nós e imprimindo sua informação. Para imprimir a informação de 
todos os nós da árvore, devemos primeiro testar se ela é vazia. Se não for, imprimimos 
a informação associada à raiz e chamamos (recursivamente) a função para imprimir as 
subárvores. 
Void4 arv_imprime (Arv* a) 
{ 
If (!arv_vazia(a)){ 
 Printf(“%c”5, a->info); 
 Arv_imprime(a->esq); 
 Arv_imprime(a->dir); 
 } 
} 
• LIBERAR A MEMÓRIA ALOCADA PELA ESTRUTURA DA ÁRVORE: um cuidado 
especial a ser tomado é liberar as subárvores antes de liberar o nó raiz, para que o acesso 
a elas não seja perdido antes de serem removidas. Nesse caso, vamos optar por fazer com 
que a função tenha como valor de retorno a árvore atualizada, isto é, uma árvore vazia, 
representada por NULL. 
 
1 Char c serve para alocar espaço na memória para algumas variáveis 
2 Abreviatura de memory allocation aloca espaço para um bloco de bytes consecutivos na memória RAM do computador e 
devolve o endereço desse bloco. 
3 Este operador permite saber o número de bytes ocupado por um determinado tipo de variável. É muito usado na alocação 
dinâmica de memória. 
4 Void quer dizer vazio. Ele nos permite fazer funções que não retornam nada e funções que não tem parâmetros. 
5 %c = um único caractere. 
Arv* arv_libera (Arv* a) { 
 If (!arv_vazia(a)){ 
 Arv_libera(a->esq); 
 Arv_libera(a->dir); 
 Free(a); 
} 
Return NULL; 
} 
• Devemos notar que a definição de árvore, por ser recursiva não faz distinção entre 
árvores e subárvores. O cria pode ser usado para acrescentar (“enxertar”) uma subárvore 
em um ramo de uma árvore, e o libera pode ser usado para remover (“podar”) uma 
subárvore qualquer de uma árvore dada. 
 
ANÁLISE DA COMPLEXIDADE DE ÁRVORES 
 
A relação existente entre altura da árvore (h) e número de nós (n) é uma informação 
muito importante. Possuem altura máxima aquelas em que cada nó possui apenas um único 
filho. A altura de tais árvores é igual a n. Já uma árvore completa possui altura mínima. 
Um dos cuidados é fazer a ramificação da árvore para que os elementos da árvore não 
fiquem ou totalmente para a ramificação da esquerda ou totalmente para a direita, nesses 
casos a altura da árvore segue uma estrutura linear e ela acaba sendo igual ao total de 
elementos que você está armazenando ali, esse é o pior cenário pois a árvore degenera para 
algo parecido com uma lista. 
O melhor caso é quando os elementos são distribuídos nível a nível, nesse caso a altura 
será log (n), pois as folhas da árvore é composta pela metade de todos os elementos que 
temos na árvore completa, se tiramos o último nível anterior teremos a metade dessa outra 
metade, com isso temos uma relação logarítmica. 
Assim teremos a distribuição desses elementos na função logarítmica de base 2, ou 
seja, teremos a raiz com um elemento, no próximo nível dois elementos, no próximo 4, depois 
8,16,32 e assim por diante. 
Esse seria o cenário ideal para termos uma árvore completa, pois assim teríamos a 
altura mínima, e conseguiríamos fazer busca, inserção e remoção em O(log(n)). 
O maior desafio é conseguir deixar essa árvore sempre completa, pois em 
determinadas situações você teria que mexer na árvore inteira para conseguir que ela 
continue sendo completa e isso consumiria O(n) e não queremos fazer essas operações que 
passem por todos os nós, pois a quantidade deles pode ser enorme. 
Então ao invés de ter uma preocupação excessiva para que a altura seja igual ao 
logaritmo da quantidade de elementos, utilizamos o proporcional a log (n), podendo ser um 
múltiplo de log (n), por exemplo: 2 vezes log(n) ou 3 vezes log(n). Mesmo que seja dobrado, 
ou triplicado, não teremos problemas, pois log (n) é um numero muito pequeno, por exemplo 
em relação a 1 milhão ele esta na casa de dezenas. 
Com isso concluímos que uma árvore balanceada é proporcional a log(n) (logaritmo 
da quantidade de elementos que existem armazenados na árvore). 
Uma árvore AVL é uma árvore na qual asalturas das subárvores esquerda e direita de 
cada nó diferem no máximo por uma unidade. Se o fator de balanceamento de qualquer nó 
ficar menor do que -1 ou maior do que 1 então a árvore tem que ser balanceada.