HYHaE2sA

1/**
2 * @file avl.c
3 * @brief Ficheiro que contém a API relativa á implementação de AVL's.
4 */
5
6#include "../include/avl.h"
7
8struct nodeAVL {
9    char* string;
10    void *cont;
11    int height;
12    struct nodeAVL *left;
13    struct nodeAVL *right;
14};
15
16struct avl {
17    NODO arvore;
18    int avl_tamanho;
19};
20
21
22static int height(NODO n);
23static int max(int a, int b);
24static int getBalance(NODO N);
25static Boolean node_lookUp(NODO node, Valor value);
26static NODO newNode(NODO node, Valor info, void *estrutura);
27static NODO rightRotate(NODO y);
28static NODO leftRotate(NODO x);
29static NODO atualiza_node(NODO node, char* value, void* estrutura);
30static NODO node_insert(NODO node, Valor string, Estrutura estrutura);
31static NODO tree_clone(NODO node, NODO novo);
32static Estrutura node_getEstrutura(NODO node, Valor value);
33static void tree_free(NODO node, Funcao f);
34
35/**
36 * @brief Função que inicializa uma nova AVL.
37 * @return Nova AVL nula
38 */
39AVL initAVL() {
40    AVL tree = malloc(sizeof(struct avl));
41    tree->arvore = NULL;
42    tree->avl_tamanho = 0;
43    return tree;
44}
45
46/**
47 * @brief Função que insere uma nova estrutura na arvore tree tendo como referência de posicionamento um char* value.
48 * @param tree AVL onde insere.
49 * @param value char* a inserir.
50 * @param estrutura Conteúdo/Estrutura a inserir.
51 * @return AVL atualizada.
52 */
53AVL atualiza_avl(AVL tree, char* value, Estrutura estrutura) {
54    tree->arvore = atualiza_node(tree->arvore,value,estrutura);
55    return tree;
56}
57
58/**
59 * @brief Função que insere na arvore tree tendo como referência de posicionamento um char*.
60 * @param tree AVL onde insere.
61 * @param key char* a inserir.
62 * @param estrutura Conteúdo/Estrutura a inserir.
63 * @return AVL com o novo nodo adicionado.
64 */
65AVL avl_insert(AVL tree, Valor key, Estrutura estrutura) {
66    tree->arvore = node_insert(tree->arvore,key,estrutura);
67    tree->avl_tamanho ++;
68    return tree;
69}
70
71/**
72 * @brief Função que devolve um Boolean referente a ter encontrado ou não na AVL o Valor value.
73 * @param tree AVL onde é efectuada a procura.
74 * @param value valor a procurar na AVL.
75 * @return Boolean com o resultado.
76 */
77Boolean avl_lookUp(AVL tree, Valor value) {
78    if(tree==NULL) return false;
79    return node_lookUp(tree->arvore,value);
80}
81
82/**
83 * @brief Função que devolve o tamanho (quantidade de nodos) de uma AVL passada como argumento.
84 * @param tree AVL da qual se pretende o tamanho.
85 * @return Int com tamanho da AVL.
86 */
87int avl_count(AVL tree) {
88    return tree->avl_tamanho;
89}
90
91/**
92 * @brief Função que executa um clone de uma dada AVL.
93 * @param node AVL a clonar.
94 * @param novo AVL onde colocar o clone.
95 * @return AVL nova, clonada da anterior.
96 */
97AVL avl_clone(AVL node, AVL novo) {
98    novo = (AVL) malloc(sizeof(struct avl));
99    novo->arvore = tree_clone(node->arvore,novo->arvore);
100    novo->avl_tamanho = node->avl_tamanho;
101    return novo;
102}
103
104/**
105 * @brief Função que devolve a estrutura associada a um nodo de uma AVL passada como argumento.
106 * @param node AVL de onde será devolvida a estrutura.
107 * @param value char* indicando o nodo a procurar onde estará a estrutura associada.
108 * @return void* com apontador para a estrutura ou NULL caso a mesma nao se encontre lá.
109 */
110Estrutura avl_getEstrutura(AVL node, Valor value) {
111    return node_getEstrutura(node->arvore,value);
112}
113
114
115int avl_getTamanho(AVL tree){
116  return tree->avl_tamanho;
117}
118
119/**
120 * @brief Função que dada uma AVL retorna o nodo da sua raiz.
121 * @param a AVL de onde se pretende o nodo.
122 * @return NODO.
123 */
124NODO getNodo(AVL a) {
125    NODO novo;
126    if(a->arvore) {
127        novo = (NODO) malloc(sizeof(struct nodeAVL));
128        novo->string = malloc((strlen(a->arvore->string)+1)*sizeof(char));
129        strcpy(novo->string,a->arvore->string);
130        novo->cont = a->arvore->cont;
131        novo->left = a->arvore->left;
132        novo->right = a->arvore->right;
133    }else {
134        novo = NULL;
135    }
136
137    return novo;
138}
139
140/**
141 * @brief Função que dado um NODO retorna o nodo á sua esquerda.
142 * @param n NODO.
143 * @return NODO à esquerda.
144 */
145NODO getNodoEsq(NODO n) {
146    NODO novo;
147    if(n->left) {
148        novo = (NODO) malloc(sizeof(struct nodeAVL));
149        novo->string = malloc((strlen(n->left->string)+1)*sizeof(char));
150        strcpy(novo->string,n->left->string);
151        novo->cont = n->left->cont;
152        novo->left = n->left->left;
153        novo->right = n->left->right;
154    }else {
155        novo = NULL;
156    }
157    return novo;
158}
159
160/**
161 * @brief Função que dado um NODO retorna o nodo á sua direita.
162 * @param n NODO.
163 * @return NODO à direita.
164 */
165NODO getNodoDir(NODO n) {
166    NODO novo;
167    if(n->right) {
168        novo = (NODO) malloc(sizeof(struct nodeAVL));
169        novo->string = malloc((strlen(n->right->string)+1)*sizeof(char));
170        strcpy(novo->string,n->right->string);
171        novo->cont = n->right->cont;
172        novo->left = n->right->left;
173        novo->right = n->right->right;
174    }else {
175        novo = NULL;
176    }
177    return novo;
178}
179
180/**
181 * @brief Função que dado um NODO retorna uma copia da sua string.
182 * @param n NODO.
183 * @return char* com a cópia.
184 */
185char* getString(NODO n) {
186    char* novo;
187    novo = malloc((strlen(n->string)+1)*sizeof(char));
188    strcpy(novo,n->string);
189    return novo;
190}
191
192/**
193 * @brief Função que dado um NODO retorna o seu contéudo.
194 * @param n NODO.
195 * @return void*.
196 */
197void* getCont(NODO n) {
198    return n->cont;
199}
200
201/**
202 * @brief Função com o objetivo de limpar da memória uma dada AVL.
203 * @param nodo AVL a limpar da memória.
204 * @param f Funcao que liberta a memória da estrutura associada.
205 */
206void avl_free(AVL nodo, Funcao f) {
207    tree_free(nodo->arvore,f);
208    free(nodo);
209}
210
211/**
212 * @brief Função que dado um NODO retorna a sua altura.
213 * @param n NODO.
214 * @return int altura.
215 */
216static int height(NODO n) {
217    if (n == NULL)
218        return 0;
219    return n->height;
220}
221
222/**
223 * @brief Função que calcula qual o maior de dois inteiros.
224 * @param int a.
225 * @param int b.
226 * @return int max.
227 */
228static int max(int a, int b) {
229    return (a > b)? a : b;
230}
231
232/**
233 * @brief Função que cria um novo nodo.
234 * @param node NODO.
235 * @param info Valor.
236 * @param estrutura void*.
237 * @return novo NODO.
238 */
239static NODO newNode(NODO node, Valor info, void *estrutura) {
240    node = (NODO) malloc(sizeof(struct nodeAVL));
241    node->string = malloc((strlen(info)+1)*sizeof(char));
242    strcpy(node->string,info);
243    node->cont = estrutura;
244    node->height = 1;
245    node->left   = NULL;
246    node->right  = NULL;
247    return node;
248}
249
250/**
251 * @brief Função que dado um NODO roda para a direita.
252 * @param y NODO.
253 * @return NODO depois de uma rotação à direita.
254 */
255static NODO rightRotate(NODO y) {
256
257    NODO x = y->left;
258    NODO T2 = x->right;
259
260    x->right = y;
261    y->left = T2;
262
263    y->height = max(height(y->left), height(y->right))+1;
264    x->height = max(height(x->left), height(x->right))+1;
265
266    return x;
267}
268
269/**
270 * @brief Função que dado um NODO roda para a esquerda.
271 * @param x NODO.
272 * @return NODO depois de uma rotação à esquerda.
273 */
274static NODO leftRotate(NODO x) {
275
276    NODO y = x->right;
277    NODO T2 = y->left;
278
279    y->left = x;
280    x->right = T2;
281
282    x->height = max(height(x->left), height(x->right))+1;
283    y->height = max(height(y->left), height(y->right))+1;
284
285    return y;
286}
287
288/**
289 * @brief Função que verifica se o nodo está balanceado e, consequentemente, a árvore.
290 * @param N NODO.
291 * @return int como Boolean.
292 */
293static int getBalance(NODO N) {
294    if (N == NULL)
295        return 0;
296    return height(N->left) - height(N->right);
297}
298
299/**
300 * @brief Função que insere um node NODO com um info Valor e uma estrutura Estrutura.
301 * @param node NODO a inserir.
302 * @param info Valor a inserir.
303 * @param estrutura Conteúdo/Estrutura a inserir.
304 * @return novo NODO inserido.
305 */
306static NODO node_insert(NODO node, Valor info, Estrutura estrutura) {
307    int balance;
308
309    if(node != NULL) {
310
311    if (strcmp(info,node->string) < 0)
312        node->left  = node_insert(node->left, info, estrutura);
313    else if(strcmp(info,node->string) > 0)
314        node->right = node_insert(node->right, info, estrutura);
315    else node->cont = estrutura;
316
317    /* Atualiza os pesos */
318    node->height = max(height(node->left), height(node->right)) + 1;
319
320    /* Varifica o balanceamento */
321    balance = getBalance(node);
322
323    /* Left Left Case */
324    if (balance > 1 && strcmp(info,node->left->string) < 0) return rightRotate(node);
325
326    /* Right Right Case */
327    if (balance < -1 && strcmp(info,node->right->string) > 0) return leftRotate(node);
328
329    /* Left Right Case */
330    if (balance > 1 && strcmp(info,node->left->string) > 0) {
331        node->left =  leftRotate(node->left);
332        return rightRotate(node);
333    }
334     /* Right Left Case */
335    if (balance < -1 && strcmp(info, node->right->string) < 0) {
336        node->right = rightRotate(node->right);
337        return leftRotate(node);
338    }
339
340    } else node = newNode(node,info,estrutura);
341
342   return node;
343}
344
345/**
346 * @brief Função que verifica se existe um nodo com um certo valor.
347 * @param node NODO a procurar.
348 * @param value Valor a procurar.
349 * @return Boolean com o resultado.
350 */
351static Boolean node_lookUp(NODO node, Valor value) {
352    int r;
353    if(node == NULL) return false;
354    else {
355        r = strcmp(value,node->string);
356        if(r == 0) return true;
357        else if(r < 0) node_lookUp(node->left, value);
358        else node_lookUp(node->right,value);
359    }
360}
361
362/**
363 * @brief Função que clona um nodo para outro nodo.
364 * @param node NODO a ser clonado.
365 * @param novo NODO clone.
366 * @return o novo NODO clone.
367 */
368static NODO tree_clone(NODO node, NODO novo) {
369
370    if(node) {
371        novo = malloc(sizeof(struct nodeAVL));
372        novo->string = malloc((strlen(node->string)+1)*sizeof(char));
373        strcpy(novo->string,node->string);
374        novo->height = node->height;
375        novo->cont = NULL;
376        novo->left = tree_clone(node->left,novo->left);
377        novo->right = tree_clone(node->right,novo->right);
378    }
379    else novo = NULL;
380
381    return novo;
382}
383
384/**
385 * @brief Função que atualiza um nodo.
386 * @param node NODO atualizado
387 * @param value char* utilizado como comparação para saber onde atualizar.
388 * @param estrutura Conteúdo/Estrutura a inserir quando atualizar.
389 * @return node NODO atualizado.
390 */
391static NODO atualiza_node(NODO node, char* value, Estrutura estrutura) {
392    int r;
393    r = strcmp(value,node->string);
394    if(r == 0) {
395        node->cont = estrutura;
396        return node;
397    }
398    else if(r < 0) atualiza_node(node->left, value,estrutura);
399    else atualiza_node(node->right,value,estrutura);
400
401    return node;
402}
403
404
405static Estrutura node_getEstrutura(NODO node, Valor value) {
406    int r;
407    if(node == NULL) return NULL;
408    else {
409        r = strcmp(value,node->string);
410        if(r == 0) return node->cont;
411        else if(r < 0) node_getEstrutura(node->left, value);
412        else node_getEstrutura(node->right,value);
413    }
414}
415
416/**
417 * @brief Função que limpa o espaço de memória ocupado por uma árvore.
418 * @param node NODO a libertar.
419 * @param f Funcao que liberta a memória da estrutura associada.
420 */
421static void tree_free(NODO node, Funcao f) {
422    if(node != NULL) {
423        tree_free(node->left,f);
424        tree_free(node->right,f);
425        if(node->cont != NULL) {
426            f(node->cont);
427        }
428        free(node->string);
429        free(node);
430    }
431}
432
433/**
434 * @brief Função que limpa da memória um dado NODO.
435 * @param node NODO a remover.
436 */
437void free_Nodo(NODO node) {
438    if(node != NULL) {
439        free(node->string);
440        free(node);
441    }
442}
443
444/**
445 * @brief Função que imprime os nodos da AVL.
446 * @param tree NODO a imprimir.
447 */
448void imprime_Conteudo_AVL(NODO tree){
449    if (tree == NULL) return;
450    imprime_Conteudo_AVL(tree->left);
451    printf("%s\n",tree->string);
452    imprime_Conteudo_AVL(tree->right);
453}
454
455/**
456 * @brief Função que imprime todas as Strings da AVL
457 * @param tree AVL a imprimir
458 */
459void imprime_AVL_String(AVL tree){
460    imprime_Conteudo_AVL(tree->arvore);
461}
462
463void get_Prod_AVLQ2(NODO tree, Q2 q){
464    if (tree == NULL) return;
465    get_Prod_AVLQ2(tree->left,q);
466    insere_ProdQ2(tree->string,q);
467    get_Prod_AVLQ2(tree->right,q);
468}
469
470void get_AVL_ProdQ2(AVL tree, Q2 q){
471    get_Prod_AVLQ2(tree->arvore,q);
472}