Baixe o app para aproveitar ainda mais
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/
Compartilhar