ESTRUTURA DE DADOS 2

Prévia do material em texto

ESTRUTURA DE DADOS 2 
Avaliação 2 – Professor Miguel Figueiredo 2022.02 
Talitta Galvão Reis De Oliveira 20201101053 
UNIVERSIDADE VEIGA DE ALMEIDA Ciências da Computação 
1 
 
Sumário 
1. PROVA ................................................................................................................................... 2 
1.1 QUESTÃO 1 .................................................................................................................... 2 
1.2 QUESTÃO 2 .................................................................................................................... 3 
2. ATIVIDADES FÓRUM ............................................................................................................. 5 
3. ATIVIDADE ÁRVORE B ......................................................................................................... 11 
 
 
2 
 
1. PROVA 
 
1.1 QUESTÃO 1 
 
 
 
Em-ordem: Sub-árvore esquerda, raiz, sub-árvore direita. O Site utilizado para construção da 
árvore foi: https://graphonline.ru/pt/ 
 
 
 
3 
 
 
Balanceando e organizando: 
 
 
1.2 QUESTÃO 2 
 
 
4 
 
Orden1: Pré-Ordem: Visita a raiz, percorre sua subárvore esquerda, percorre a subárvore 
direita. O Perscurso pré-ordem segue os nós até chegar os mais profundos em ramos da 
subárvore da esquerda para direita. 
Orden2: Em-Ordem: Percorre a sua subárvore esquerda em in-order, visita a raiz, percorre a 
sua subárvore da direita in-order. 
Orden3: Pós-Ordem: Percorre a sua subárvore esquerda pós-ordem, percorre sua subárvore da 
direita em pós ordem e visitar a raiz. 
 
 
 
 
 
 
 
 
5 
 
2. ATIVIDADES FÓRUM 
Atividade (03/10/2022) - Implemente na linguagem C/C++ o algoritmo Inorder Tree Walk que 
permite imprimir todas as chaves de uma arvore binária em ordem de forma recursiva, 
conforme o pseudo-código abaixo: 
Inorder Walk(T, x) { 
 if x <> NIL { 
 Inorder Walk( T, left[x] ); 
 print(key[x]); 
 Inorder Walk( T, right[x] ); }}; 
Prazo final até 17/10/2022! 
 
 
 
#include 
#include 
#include 
 
/*Inorder Walk(T, x) { 
 
 if x <> NIL { 
 
 Inorder Walk( T, left[x] ); 
 print(key[x]); 
 Inorder Walk( T, right[x] ); 
 
 } 
 
};*/ 
 
 
//nó, ponteiro para filhos a esquerda e a direita 
typedef struct node { 
 int data; 
 struct node *left; 
 struct node *right; 
}node; 
 
//insere nó e aponta filhos esqr e direta para null 
6 
 
struct node* newNode(int data) 
{ 
 struct node* node 
 = (struct node*)malloc(sizeof(struct node)); 
 node->data = data; 
 node->left = NULL; 
 node->right = NULL; 
 
 return (node); 
} 
 
//print nodes em ordem: recurs esquerda, print nó, recursiva direita 
void printInorder(struct node* node) 
{ 
 if (node == NULL){ 
 return; 
 } 
 
 /* primeiro recursivo filho a esquerda */ 
 printInorder(node->left); 
 /* printa o valor do nó */ 
 printf("%d ", node->data); 
 /* depois recursiva filho a direita */ 
 printInorder(node->right); 
} 
 
void menu() { 
 printf("\n\t\t**Menu**\n"); 
 printf("1 - Inserir dados base\n"); 
 printf("2 - Imprimir Inorder Walk\n"); 
 printf("3 - Sair \n"); 
 printf("R:"); 
 
} 
 
 
int main(){ 
 
 node *root = NULL; 
 int data; 
 int op; 
 
 
 do{ 
 menu(); 
 scanf("%d", &op); 
 
 switch(op){ 
 
 case 1: 
 root = newNode(1); 
 root->left = newNode(2); 
 root->right = newNode(3); 
 root->left->left = newNode(4); 
 root->left->right = newNode(5); 
 
 break; 
 
 case 2: 
 printf("\n"); 
 printInorder(root); 
 printf("\n"); 
 break; 
 
 case 3: 
 printf("\nEncerrando...\n"); 
 break; 
 
 default: 
 printf("\nOpção inválida!\n\n"); 
 } 
 
 }while(op != 3); 
 
7 
 
 return 0; 
} 
 
Atividade (10/10/2022) - Implemente na linguagem C/C++ o algoritmo Search 
que retorna um ponteiro para um objeto com a chave k se existir, ou NIL caso 
contrário, a partir de uma raiz x e uma chave k, conforme o pseudo-código 
abaixo: 
Search(x, k){ 
 if x = NIL or key[x] = k 
 return x 
 if k < key[x] 
 Search(left[x], k) 
 else 
 Search(right[x], k); 
} 
 
 
 
#include 
#include 
 
//nó, ponteiro para filhos a esquerda e a direita 
typedef struct node { 
 int data; 
 struct node *left; 
 struct node *right; 
}node; 
 
//insere nó e aponta filhos esqr e direta para null 
struct node* newNode(int data) 
{ 
 struct node* node 
 = (struct node*)malloc(sizeof(struct node)); 
 node->data = data; 
 node->left = NULL; 
 node->right = NULL; 
 
 return (node); 
8 
 
} 
 
 
node* search (node *node, int k) { 
 if (node == NULL || node->data == k) 
 return node; 
 if (node->data > k) 
 return search (node->left, k); 
 else 
 return search (node->right, k); 
} 
 
 
//print nodes em ordem: recurs esquerda, print nó, recursiva direita 
void printInorder(struct node* node) 
{ 
 if (node == NULL){ 
 return; 
 } 
 
 /* primeiro recursivo filho a esquerda */ 
 printInorder(node->left); 
 /* printa o valor do nó */ 
 printf("%d ", node->data); 
 /* depois recursiva filho a direita */ 
 printInorder(node->right); 
} 
 
 
void menu() { 
 printf("\n\t\t**Menu**\n"); 
 printf("1 - Inserir dados base\n"); 
 printf("2 - Imprimir Inorder Walk\n"); 
 printf("3 - Buscar elemento\n"); 
 printf("4 - Sair \n"); 
 printf("R:"); 
 
} 
 
 
int main(){ 
 
 node *root = NULL; 
 int data; 
 int op; 
 
 
 do{ 
 menu(); 
 scanf("%d", &op); 
 
 switch(op){ 
 
 case 1: 
 /*printf("\nVocê escolheu inserir.\nDigite um valor:\n"); 
 scanf("%d", &data); 
 printf("\n"); 
 root = newNode(data);*/ 
 root = newNode(1); 
 root->left = newNode(2); 
 root->right = newNode(3); 
 root->left->left = newNode(4); 
 root->left->right = newNode(5); 
 
 break; 
 
 case 2: 
 printf("\n"); 
 printInorder(root); 
 printf("\n"); 
 break; 
 
 case 3: 
 printf("\nDigite valor procurado\n"); 
9 
 
 search (root, scanf("%d", data)); 
 
 break; 
 
 case 4: 
 printf("\nEncerrando...\n"); 
 break; 
 
 default: 
 printf("\nOpção inválida!\n\n"); 
 } 
 
 }while(op != 4); 
 
 return 0; 
} 
 
Atividade (24/10/2022) - Calcule manualmente o fator de balanceamento de 
cada nó da árvore binária abaixo. 
 
 
Atividade (31/10/2022) - Faça uma pesquisa sobre a estrutura de dados do 
tipo Árvore de Busca Binária denominada Árvore Rubro Negra, ressaltando seus 
principais aspectos. Elabore um exemplo. 
 
10 
 
 
 
São tipos de árvores binárias de busca ditas balanceadas com altura O(log n). 
Altura é no máximo igual a 2 log(n + 1). 
 
Uma árvore rubro-negra é uma árvore binária de busca em que cada nó é constituído dos 
seguintes campos: 
1 - cor (1 bit): pode ser vermelho ou preto. 
2 - key (e.g. inteiro): indica o valor de uma chave. 
3 e 4 - left, right: ponteiros que apontam para a subárvore 
esquerda e direita, resp. 
5 - pai: ponteiro que aponta para o nó pai. O campo pai do nó raiz aponta para nil. 
O ponteiro pai facilita a operação da árvore rubro-negra. 
 
As propriedades da árvore rubro-negra são 
1 - Todo nó da árvore ou é vermelho ou é preto. 
2 - A raiz é preta. 
3 - Toda folha (nil) é preta. 
4 -Se um nó é vermelho, então ambos os filhos são pretos. 
5 - Para todo nó, todos os caminhos do nó até as folhas descendentes contêm o mesmo 
número de nós pretos. 
 
 
11 
 
 
 
Referências: 
https://www.ufjf.br/jairo_souza/files/2012/11/5-Indexa%c3%a7%c3%a3o-Arvore-Vermelho-
Preta.pdf 
https://www.ime.usp.br/~song/mac5710/slides/08rb.pdf 
 
3. ATIVIDADE ÁRVORE B 
Atividade (14/11/2022) Faça uma pesquisa sobre a estrutura de dados do 
tipo Árvore denominada Árvore B, ressaltando seus principais aspectos. Elabore 
um exemplo. 
 
 
Arvores B 
Criadas por R. Bayer e E. M. McCreight em 1972, são árvores auto equilibradas normalmente 
usada em bancos de dados e sistemas de arquivos. foi projetada para funcionar especialmente 
em memória secundária como um disco magnético ou outros dispositivos de armazenamento 
secundário. 
 
12 
 
Nós dessa árvore podem ter muitos filhos. Por isso, é possível reduzir o número de acessos ao 
disco. Sua altura é O(ln(n)). Um fator de ramificação alto reduz a altura da árvore. Um nó de 
uma árvore B é também chamado de página. 
 
Características de uma árvore B de ordem d: 
A raiz é uma folha ou tem no mínimo 2 filhos 
Cada nó interno (não folha e não raiz) possui no mínimo d + 1 filhos 
Cada nó tem no máximo 2d + 1 filhos 
Todas as folhas estão no mesmo nível 
 
Referências: 
https://www.ic.unicamp.br/~zanoni/teaching/mo637/2007-2s/aulas/arvoresB.pdf 
https://ic.unicamp.br/~afalcao/mc202/aulas16a18-ArvoreB.pdf 
http://www2.ic.uff.br/~vanessa/material/ed/11-ArvoreB.pdf 
https://acervolima.com/introducao-de-b-tree/