---
# System prepended metadata

title: TP2 e 3 – Estruturas de Dados e Paralelismo

---

# Prova – Estruturas de Dados e Paralelismo


---

## Parte A — Árvore Rubro-Negra
### 0 Usando o código:
[https://github.com/leoinfnet/redblack-tp3] 

### 1. Rotação e recoloração  
Considere a sequência de inserções `41, 38, 31, 12, 19, 8` em uma **Árvore Rubro-Negra** vazia.

- Após inserir `31`, qual rotação ocorre (se ocorrer) e quem é o novo nó raiz?  
- Após inserir `19`, descreva **apenas** as operações de fix-up até o balanceamento final.  
  Cite o caso Tio-Vermelho, as rotações e as recolorações envolvidas.

---

### 2. Verdadeiro ou Falso  
Justifique brevemente cada afirmação.

- a) Todo caminho da raiz até uma folha externa (NIL) tem a mesma quantidade de nós pretos.  
- b) Em uma árvore Rubro-Negra, a raiz pode ser vermelha.  
- c) Após uma remoção, só há correção se o nó removido fosse vermelho.  
- d) A altura negra nunca diminui após uma inserção.

---

### 3. Complexidade e limites

- a) Explique por que a altura `h` de uma árvore Rubro-Negra com `n` chaves é da ordem de `O(log n)`.  
- b) Qual é o número máximo de rotações necessárias em uma inserção? Quando isso ocorre?

---
### 4. Implementação: 
Usando o repositório informado: 
 1-  Implemente a lógica de remoção de um nó na árvore.
 2-  Implemente o método inorder que deverá RECURSIVAMENTE percorrer a árvore e imprimir todos os elementos em ordem crescente. 
 3- Implemente o método: blackHeight que deverá calcular a quantidade de nós pretos de um determinado nó até um nó folha.

## Parte B — Árvore B

Considere uma Árvore B de grau mínimo `t = 2`.

### 1. Inserções  
Insira, nessa ordem, as chaves `10, 20, 5, 6, 12, 30, 7, 17`.  
Desenhe a árvore **após cada split**.  
Ao final, mostre o conteúdo da **raiz** e de **cada filho direto da raiz**.

---

### 2. Busca e custo

- a) Qual o número **mínimo** e **máximo** de chaves que podem estar na raiz (não-folha)?  
- b) Qual o número máximo de nós acessados em uma operação de busca (em termos de altura `h`)?

---

### 3. Remoção  
Comece com a árvore resultante da questão anterior.  
Remova, nessa ordem: `6`, depois `7`, depois `20`.

Para cada remoção:

- Indique se houve **empréstimo** ou **concatenação**.  
- Informe de qual lado ocorreu o empréstimo, se houver.  
- Mostre a chave promovida ou absorvida e o estado final dos nós alterados.

---

### 4. Implementação prática — Inserção na Árvore B

Implemente em Java, Python ou C++ a função abaixo para dividir um nó cheio em uma Árvore B de grau `t = 2`.  
Não é necessário implementar a árvore completa — apenas o trecho responsável pelo **split** e a **promoção da chave mediana**.

```c
// Estrutura básica (pode adaptar)
struct No {
    int chaves[3];
    int n;              // número atual de chaves
    struct No* filhos[4];
    bool folha;
};

// Função esperada
void divideNo(struct No* pai, int i, struct No* cheio);
```

Requisitos:

- O nó `cheio` possui 3 chaves.  
- Promova a chave do meio para o pai.  
- Crie um novo nó com as chaves da direita.  
- Atualize os ponteiros de filho do pai.

> **Itens para entregar:** código fonte do `divideNo` (arquivo separado ou colado no espaço de resposta), comentários curtos explicando as etapas do split e instruções mínimas de compilação (se aplicável).

---

## Parte C — OpenMP

### 1. Race condition e reduction

Analise o código a seguir:

```c
#include <omp.h>
#include <stdio.h>
int main() {
    long n = 1000000;
    long hits = 0;
    #pragma omp parallel for
    for (long i = 0; i < n; i++) {
        if ((i * 37) % 101 == 0) { hits++; }
    }
    printf("%ld\n", hits);
}
```

- a) Explique por que há **data race**.  
- b) Reescreva apenas a diretiva para corrigir o problema usando `reduction`.  
- c) Qual a diferença prática entre `schedule(static)` e `schedule(dynamic)` nesse caso?

---

### 2. Implementação prática — Estimativa de π com Monte Carlo paralelo

Implemente um programa em C usando OpenMP que estime o valor de π pelo método de Monte Carlo. 
## Dica: 
Utilize docker para criar a estrutura para rodar OpenMP.
Requisitos:

1. Gere `N` pontos aleatórios `(x, y)` no quadrado `[0, 1] × [0, 1]`.  
2. Conte quantos pontos caem dentro do quarto de círculo `x² + y² ≤ 1`.  
3. Paralelize o loop principal com OpenMP.  
4. Use `reduction(+:contador)` para evitar race condition.  
5. Calcule `π ≈ 4 × contador / N`.  
6. Mostre o valor estimado e o tempo de execução com 1 thread e com todos os núcleos.

> **Itens para entregar:** código fonte compilável, breve instrução de compilação (ex.: `gcc -fopenmp ...`), exemplo de execução com `N` indicado e saída exibida.

---
