# 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**.

// 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:

#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.

---