**Considering rb_init and color sentinel** I'm thinking about the implementation of `rb_init` with a color sentinel, specifically BLACK, and how to manage the free list. I’ll utilize an enum for colors as uint8. Providing the code is a must, but I should be cautious not to claim all optimizations since that might not be feasible. It's crucial to ensure the code compiles correctly. The delete function should return a bool for key uniqueness. Finally, I’ll work on implementing `rb_insert` with proper key handling. Abaixo está uma implementação **iterativa** de árvore rubro-negra em C, usando: - Pool de nós com tamanho fixo; - Nenhum `malloc`, `calloc` ou `free`; - Índices inteiros em vez de ponteiros; - Nó sentinela `NIL`, evitando verificações de `NULL`; - Inserção, busca e remoção; - Lista livre para reutilização dos nós removidos; - Complexidade `O(log n)` para busca, inserção e remoção; - Operações sem recursão. > O código considera chaves `int32_t` únicas. ```c #include #include #include #ifndef RB_MAX_NODES #define RB_MAX_NODES 100000 #endif typedef uint32_t rb_index_t; #define RB_NIL ((rb_index_t)0) enum { RB_BLACK = 0, RB_RED = 1 }; typedef struct { int32_t key; rb_index_t left; rb_index_t right; rb_index_t parent; uint8_t color; } RBNode; typedef struct { RBNode node[RB_MAX_NODES + 1]; rb_index_t root; rb_index_t free_head; uint32_t size; } RBTree; /* -------------------------------------------------------------------------- */ /* Inicialização */ /* -------------------------------------------------------------------------- */ static inline void rb_init(RBTree *restrict tree) { tree->root = RB_NIL; tree->free_head = 1; tree->size = 0; /* * O índice 0 é o nó sentinela NIL. * Os demais nós formam uma lista encadeada de nós livres. */ tree->node[RB_NIL].color = RB_BLACK; tree->node[RB_NIL].left = RB_NIL; tree->node[RB_NIL].right = RB_NIL; tree->node[RB_NIL].parent = RB_NIL; for (rb_index_t i = 1; i <= RB_MAX_NODES; ++i) { tree->node[i].right = (i < RB_MAX_NODES) ? (i + 1) : RB_NIL; } } /* -------------------------------------------------------------------------- */ /* Gerenciamento do pool */ /* -------------------------------------------------------------------------- */ static inline rb_index_t rb_alloc_node(RBTree *restrict tree) { const rb_index_t index = tree->free_head; if (index == RB_NIL) return RB_NIL; /* Pool cheio */ tree->free_head = tree->node[index].right; ++tree->size; return index; } static inline void rb_release_node(RBTree *restrict tree, rb_index_t index) { tree->node[index].right = tree->free_head; tree->free_head = index; --tree->size; } /* -------------------------------------------------------------------------- */ /* Rotações */ /* -------------------------------------------------------------------------- */ static inline void rb_rotate_left(RBTree *restrict tree, rb_index_t x) { rb_index_t y = tree->node[x].right; tree->node[x].right = tree->node[y].left; if (tree->node[y].left != RB_NIL) tree->node[tree->node[y].left].parent = x; tree->node[y].parent = tree->node[x].parent; if (tree->node[x].parent == RB_NIL) { tree->root = y; } else if (x == tree->node[tree->node[x].parent].left) { tree->node[tree->node[x].parent].left = y; } else { tree->node[tree->node[x].parent].right = y; } tree->node[y].left = x; tree->node[x].parent = y; } static inline void rb_rotate_right(RBTree *restrict tree, rb_index_t x) { rb_index_t y = tree->node[x].left; tree->node[x].left = tree->node[y].right; if (tree->node[y].right != RB_NIL) tree->node[tree->node[y].right].parent = x; tree->node[y].parent = tree->node[x].parent; if (tree->node[x].parent == RB_NIL) { tree->root = y; } else if (x == tree->node[tree->node[x].parent].right) { tree->node[tree->node[x].parent].right = y; } else { tree->node[tree->node[x].parent].left = y; } tree->node[y].right = x; tree->node[x].parent = y; } /* -------------------------------------------------------------------------- */ /* Busca */ /* -------------------------------------------------------------------------- */ static inline rb_index_t rb_find(const RBTree *restrict tree, int32_t key) { rb_index_t current = tree->root; while (current != RB_NIL) { const int32_t current_key = tree->node[current].key; if (key == current_key) return current; current = (key < current_key) ? tree->node[current].left : tree->node[current].right; } return RB_NIL; } /* -------------------------------------------------------------------------- */ /* Correção após inserção */ /* -------------------------------------------------------------------------- */ static void rb_insert_fixup(RBTree *restrict tree, rb_index_t z) { while (tree->node[tree->node[z].parent].color == RB_RED) { rb_index_t parent = tree->node[z].parent; rb_index_t grand = tree->node[parent].parent; if (parent == tree->node[grand].left) { rb_index_t uncle = tree->node[grand].right; if (tree->node[uncle].color == RB_RED) { tree->node[parent].color = RB_BLACK; tree->node[uncle].color = RB_BLACK; tree->node[grand].color = RB_RED; z = grand; } else { if (z == tree->node[parent].right) { z = parent; rb_rotate_left(tree, z); parent = tree->node[z].parent; grand = tree->node[parent].parent; } tree->node[parent].color = RB_BLACK; tree->node[grand].color = RB_RED; rb_rotate_right(tree, grand); } } else { rb_index_t uncle = tree->node[grand].left; if (tree->node[uncle].color == RB_RED) { tree->node[parent].color = RB_BLACK; tree->node[uncle].color = RB_BLACK; tree->node[grand].color = RB_RED; z = grand; } else { if (z == tree->node[parent].left) { z = parent; rb_rotate_right(tree, z); parent = tree->node[z].parent; grand = tree->node[parent].parent; } tree->node[parent].color = RB_BLACK; tree->node[grand].color = RB_RED; rb_rotate_left(tree, grand); } } } tree->node[tree->root].color = RB_BLACK; } /* -------------------------------------------------------------------------- */ /* Inserção */ /* -------------------------------------------------------------------------- */ bool rb_insert(RBTree *restrict tree, int32_t key) { rb_index_t parent = RB_NIL; rb_index_t current = tree->root; while (current != RB_NIL) { parent = current; if (key == tree->node[current].key) return false; /* Não permite chaves duplicadas */ current = (key < tree->node[current].key) ? tree->node[current].left : tree->node[current].right; } const rb_index_t z = rb_alloc_node(tree); if (z == RB_NIL) return false; /* Pool cheio */ tree->node[z].key = key; tree->node[z].parent = parent; tree->node[z].left = RB_NIL; tree->node[z].right = RB_NIL; tree->node[z].color = RB_RED; if (parent == RB_NIL) { tree->root = z; } else if (key < tree->node[parent].key) { tree->node[parent].left = z; } else { tree->node[parent].right = z; } rb_insert_fixup(tree, z); return true; } /* -------------------------------------------------------------------------- */ /* Transplante */ /* -------------------------------------------------------------------------- */ static inline void rb_transplant(RBTree *restrict tree, rb_index_t u, rb_index_t v) { if (tree->node[u].parent == RB_NIL) { tree->root = v; } else if (u == tree->node[tree->node[u].parent].left) { tree->node[tree->node[u].parent].left = v; } else { tree->node[tree->node[u].parent].right = v; } /* * Mesmo o sentinela NIL possui parent temporariamente. * Isso simplifica a remoção sem casos especiais. */ tree->node[v].parent = tree->node[u].parent; } /* -------------------------------------------------------------------------- */ /* Menor elemento de uma subárvore */ /* -------------------------------------------------------------------------- */ static inline rb_index_t rb_minimum(const RBTree *restrict tree, rb_index_t root) { while (tree->node[root].left != RB_NIL) root = tree->node[root].left; return root; } /* -------------------------------------------------------------------------- */ /* Correção após remoção */ /* -------------------------------------------------------------------------- */ static void rb_delete_fixup(RBTree *restrict tree, rb_index_t x) { while (x != tree->root && tree->node[x].color == RB_BLACK) { const rb_index_t parent = tree->node[x].parent; if (x == tree->node[parent].left) { rb_index_t sibling = tree->node[parent].right; if (tree->node[sibling].color == RB_RED) { tree->node[sibling].color = RB_BLACK; tree->node[parent].color = RB_RED; rb_rotate_left(tree, parent); sibling = tree->node[parent].right; } const rb_index_t sl = tree->node[sibling].left; const rb_index_t sr = tree->node[sibling].right; if (tree->node[sl].color == RB_BLACK && tree->node[sr].color == RB_BLACK) { tree->node[sibling].color = RB_RED; x = parent; } else { if (tree->node[sr].color == RB_BLACK) { tree->node[sl].color = RB_BLACK; tree->node[sibling].color = RB_RED; rb_rotate_right(tree, sibling); sibling = tree->node[parent].right; } tree->node[sibling].color = tree->node[parent].color; tree->node[parent].color = RB_BLACK; tree->node[tree->node[sibling].right].color = RB_BLACK; rb_rotate_left(tree, parent); x = tree->root; } } else { rb_index_t sibling = tree->node[parent].left; if (tree->node[sibling].color == RB_RED) { tree->node[sibling].color = RB_BLACK; tree->node[parent].color = RB_RED; rb_rotate_right(tree, parent); sibling = tree->node[parent].left; } const rb_index_t sl = tree->node[sibling].left; const rb_index_t sr = tree->node[sibling].right; if (tree->node[sr].color == RB_BLACK && tree->node[sl].color == RB_BLACK) { tree->node[sibling].color = RB_RED; x = parent; } else { if (tree->node[sl].color == RB_BLACK) { tree->node[sr].color = RB_BLACK; tree->node[sibling].color = RB_RED; rb_rotate_left(tree, sibling); sibling = tree->node[parent].left; } tree->node[sibling].color = tree->node[parent].color; tree->node[parent].color = RB_BLACK; tree->node[tree->node[sibling].left].color = RB_BLACK; rb_rotate_right(tree, parent); x = tree->root; } } } tree->node[x].color = RB_BLACK; } /* -------------------------------------------------------------------------- */ /* Remoção */ /* -------------------------------------------------------------------------- */ bool rb_delete(RBTree *restrict tree, int32_t key) { const rb_index_t z = rb_find(tree, key); if (z == RB_NIL) return false; rb_index_t y = z; rb_index_t x; const uint8_t original_color = tree->node[y].color; if (tree->node[z].left == RB_NIL) { x = tree->node[z].right; rb_transplant(tree, z, tree->node[z].right); } else if (tree->node[z].right == RB_NIL) { x = tree->node[z].left; rb_transplant(tree, z, tree->node[z].left); } else { y = rb_minimum(tree, tree->node[z].right); x = tree->node[y].right; if (tree->node[y].parent == z) { tree->node[x].parent = y; } else { rb_transplant(tree, y, tree->node[y].right); tree->node[y].right = tree->node[z].right; tree->node[tree->node[y].right].parent = y; } rb_transplant(tree, z, y); tree->node[y].left = tree->node[z].left; tree->node[tree->node[y].left].parent = y; tree->node[y].color = tree->node[z].color; } if (original_color == RB_BLACK) rb_delete_fixup(tree, x); rb_release_node(tree, z); /* * Não é necessário manter parent do NIL fora das operações. * Isso apenas deixa o estado do sentinela limpo. */ tree->node[RB_NIL].parent = RB_NIL; return true; } /* -------------------------------------------------------------------------- */ /* Informações auxiliares */ /* -------------------------------------------------------------------------- */ static inline bool rb_empty(const RBTree *restrict tree) { return tree->root == RB_NIL; } static inline uint32_t rb_size(const RBTree *restrict tree) { return tree->size; } ``` ### Exemplo de uso ```c #include int main(void) { /* * Use static ou global para evitar consumir a pilha. */ static RBTree tree; rb_init(&tree); rb_insert(&tree, 50); rb_insert(&tree, 20); rb_insert(&tree, 70); rb_insert(&tree, 10); rb_insert(&tree, 30); if (rb_find(&tree, 30) != RB_NIL) printf("30 encontrado\n"); rb_delete(&tree, 20); printf("Elementos: %u\n", rb_size(&tree)); return 0; } ``` Para compilação com otimizações: ```bash gcc -std=c11 -O3 -march=native -flto -DNDEBUG arvore_rb.c -o arvore_rb ``` A estrutura possui complexidade: | Operação | Complexidade | |---|---:| | Busca | `O(log n)` | | Inserção | `O(log n)` | | Remoção | `O(log n)` | | Memória | `O(MAX_NODES)` | A principal limitação é que o número máximo de elementos é definido em tempo de compilação por `RB_MAX_NODES`. Isso elimina a alocação dinâmica e torna o comportamento de memória determinístico.

Escreva o algorítimo da arvore rubro negra que tenha uma per...