2020_1_A1_ATIVIDADE_INDIVIDUAL_ESTRUTURA_DE_DADOS_2_1INF35ACopia

Prévia do material em texto

Curso de Graduação em Ciência da Computação
ATIVIDADE INDIVIDUAL AVALIATIVA
Especificação da atividade:
QUESTÃO 1 – Árvores de altura balanceada ou de altura equilibrada foram introduzidas em 1962 por Adelson-Velskii e Landis, também conhecidas como árvores AVL Devido ao balanceamento da árvore, as operações de busca, inserção e remoção em uma árvore com n elementos podem ser efetuadas em O(log2n), mesmo no pior caso. Um teorema provado por Adelson-Velskii e Landis garante que a árvore balanceada nunca será 45% mais alta que a correspondente árvore perfeitamente balanceada, independentemente do número de nós existentes. A seguir são apresentadas as regras de rotações para uma árvore AVL, as quais foram criadas com o objetivo de manter a árvore balanceada.
RSE (PAI): Rotação Simples à esquerda
· O nó que causou o desbalanceamento foi inserido na subárvore direita da subárvore direita (RR) do nó que ficou com FB = -2.
· FB(pai) = -2
· FB(dir) <= 0
RSD (PAI): Rotação Simples à Direita
· O nó que causou o desbalanceamento foi inserido na subárvore esquerda da subárvore esquerda (LL) do nó que ficou com FB = +2.
· FB(pai) = +2
· FB(esq) >= 0
RDE (PAI): Rotação Dupla DIR-ESQ
· O nó que causou o desbalanceamento foi inserido na subárvore esquerda da subárvore direita (RL) do nó que ficou com FB = -2.
· FB(pai) = -2
· FB(dir) > 0
· Primeiro: RSD(dir) | Segundo: RSE(pai) 
RED (PAI): Rotação Dupla ESQ-DIR
· O nó que causou o desbalanceamento foi inserido na subárvore direita da subárvore esquerda (LR) do nó que ficou com FB = +2.
· FB(pai) = +2
· FB(esq) < 0
· Primeiro: RSE(esq) | Segundo: RSD(pai)
Dada a AVL a seguir:
A) Insira os elementos {1, 65, 12, 18, 66, 38, 95, 58, 59, 70, 68, 39, 62, 60, 43, 16, 67, 36, 35} nesta arvore, indicando todas as rotações necessárias. (1,5)
B) Retire os elementos {35, 34, 67, 16, 42, 60, 62, 39, 68, 70, 59, 58, 95, 38, 66, 18, 12, 64, 1} desta arvore, explicitando todas as rotações realizadas. (1,0)
QUESTÃO 2 – O número de acesso ao disco é medido em termos do número de páginas de informações que precisam ser lidas/gravadas. Observamos que o tempo de acesso ao disco não é constante – ele depende da distância entre a trilha atual e a trilha desejada, e também do estado inicial de rotação do disco. Em uma aplicação típica de árvore B, a quantidade de dados manipulados é tão grande que não cabem todos na memória principal de uma só vez.
Os algoritmos de árvore B copiam páginas selecionadas do disco para a memória principal conforme necessário e gravam novamente em disco as páginas que foram alteradas. Os dados da árvore são paginados.
Uma árvore B possui as seguintes regras:
1) Seja T uma árvore B com raiz (root[T]). Ela possuirá então as seguintes propriedades:
· Todo o nó x tem os campos:
· A) n[x]: o número de chaves atualmente armazenadas em x,
· B) as n[x] chaves armazenadas em ordem crescente, i.e., key[x] <= key1[x] <= . . . <= keyn[x][x]
· C) folha [x]: um valor booleano que vale true se x é uma folha e false se x é um nó interno
2) Cada nó interno x também contém n[x] + 1 apontadores c0[x], c1[x], ...,cn[x][x] para os filhos. As folhas têm todos seus apontadores nulos; assim seus campos ci são indefinidos (null).
3) Todas as folhas têm a mesma profundidade, que é a altura da árvore: h
4) As chaves keyi[x] separam os intervalos de chaves armazenadas em cada sub-árvore. Assim, se ki é uma chave armazenada na sub-árvore com raiz ci[x], então:
· k0 <= key0[x] <= k1 <= key1[x] <= . . . <= keyn[x]−1[x] <= kn[x]
5) Existem limites superiores e inferiores para o número de chaves num nó. Eles são expressos em termos de um inteiro fixo t >= 2, chamado grau mínimo da árvore:
· Todo nó que não seja raiz deve ter pelo menos t − 1 chaves. Portanto, todo nó interno que não seja a raiz tem pelo t ou mais filhos. Se a árvore for não vazia, a raiz deve ter pelo menos uma chave.
· Todo nó pode conter no máximo 2t − 1 chaves. Portanto, um nó interno, pode ter no máximo 2t filhos. O nó dito estar cheio quando ele contém exatamente 2t − 1 chaves
De acordo com estas informações sobre Árvore B, responda as perguntas a seguir:
A) Considerando uma árvore B com fator de ramificação t =2, demonstre o passo a passo das seguintes inclusões e remoções de chaves nesta árvore (2,0):
Primeiro realize todas as inserções nesta ordem: {5, 20, 26, 49, 51, 74, 99, 101, 15, 30, 65, 100, 25, 75, 50}
Depois realize todas as remoções nesta ordem: {49, 50, 101, 20, 5, 30, 25, 75, 74, 51}
OBS: O aluno deve indicar os casos de inserção (split) e remoção (1, 2A, 2B, 2C, 3, 3A, 3B) que estão sendo realizados.
B) Considerando o programa desenvolvido em C, e apresentado em sala de aula, que implementa a inclusão e a remoção em uma árvore B, crie uma função que retorne uma lista simplesmente encadeada com todas as chaves da árvore B que estão entre dois valores inteiros K1 e K2. O ponteiro para a raiz da árvore B (TAB* arv) e os inteiros K1 e K2 são parâmetros de entrada desta função. A seguir é possível verificar a assinatura desta função (1,5):
TLSE* chaves_entre_k1_k2(TAB* arv, int k1, int k2) 
QUESTÃO 3 – Uma árvore B+ armazena todas as informações satélites nas folhas e só armazena ponteiros de chaves e filhos nos nós internos, maximizando assim o fator de ramificação dos nós internos. Manter uma árvore B é mais complexo que manter uma B+. Conforme visto em sala, a remoção em uma árvore B+ só tem os casos 1, 3A e 3B.
Conforme pode ser visto na figura a seguir, as folhas de uma árvore B+ são interconectadas como uma lista simplesmente encadeada, de forma a facilitar o acesso aos dados. Como as informações “satélites” estão sempre nas folhas, para buscar um elemento com chave K na árvore, basta descer até a folha. a partir da qual se deseja buscar K, e em seguida percorrer esta “lista”, caso seja necessário obter informações das chaves maiores que K.
Com base nestas informações, responda as questões a seguir:
A) Considerando uma árvore B+ com fator de ramificação t =3, demonstre o passo a passo das seguintes inclusões e remoções de chaves nesta árvore (2,0):
Primeiro realize todas as inserções nesta ordem: {81, 44, 23, 7, 13, 35, 18, 21, 16, 72, 29, 95, 12, 66, 69, 89, 24, 41, 54, 40, 11}
Depois realize todas as remoções nesta ordem: {23, 21, 13, 7, 16, 12, 29}
B) Considerando o programa desenvolvido em C, e apresentado em sala de aula, que implementa a inclusão e a remoção em uma árvore B+, crie uma função que retorne uma lista simplesmente encadeada com todas as chaves da árvore B* que são maiores que inteiro K. O ponteiro para a raiz da árvore B+ (TABM* arv) e o inteiro K são parâmetros de entrada desta função. A seguir é possível verificar a assinatura desta função (2,0):
TLSE* chaves_maiores_k(TABM* arv, int k)
Universidade Veiga de Almeida - UVA Página 6 de 6