From 1ceaa1773b21e4abe2ee6db9d5cea3c12c97a2e9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Luk=C3=A1=C5=A1=20Ji=C5=99i=C5=A1t=C4=9B?= Date: Thu, 31 Jul 2025 15:10:54 +0200 Subject: [PATCH] Implement red-black tree This is an untested implementation. --- Makefile | 10 +++ ft_struct/ft_rbtree_decide.c | 10 +++ ft_struct/ft_rbtree_delete.c | 12 +++ ft_struct/ft_rbtree_erase_node.c | 105 +++++++++++++++++++++++++++ ft_struct/ft_rbtree_free.c | 20 +++++ ft_struct/ft_rbtree_helpers.c | 29 ++++++++ ft_struct/ft_rbtree_init.c | 11 +++ ft_struct/ft_rbtree_insert.c | 117 ++++++++++++++++++++++++++++++ ft_struct/ft_rbtree_search.c | 13 ++++ ft_struct/ft_rbtree_search_node.c | 28 +++++++ inc/ft_struct.h | 40 +++++++++- 11 files changed, 394 insertions(+), 1 deletion(-) create mode 100644 ft_struct/ft_rbtree_decide.c create mode 100644 ft_struct/ft_rbtree_delete.c create mode 100644 ft_struct/ft_rbtree_erase_node.c create mode 100644 ft_struct/ft_rbtree_free.c create mode 100644 ft_struct/ft_rbtree_helpers.c create mode 100644 ft_struct/ft_rbtree_init.c create mode 100644 ft_struct/ft_rbtree_insert.c create mode 100644 ft_struct/ft_rbtree_search.c create mode 100644 ft_struct/ft_rbtree_search_node.c diff --git a/Makefile b/Makefile index e900d0a..28173b9 100644 --- a/Makefile +++ b/Makefile @@ -31,6 +31,16 @@ SRCstruct:= ft_stack_free.c \ ft_tree_replace_with_child.c \ ft_tree_forget_child.c \ ft_tree_free.c \ + ft_rbtree_decide.c \ + ft_rbtree_delete.c \ + ft_rbtree_erase_node.c \ + ft_rbtree_free.c \ + ft_rbtree_helpers.c \ + ft_rbtree_init.c \ + ft_rbtree_insert.c \ + ft_rbtree_search.c \ + ft_rbtree_search_node.c \ + SRCparse:= ft_parse.c \ ft_parsing_table_init.c \ diff --git a/ft_struct/ft_rbtree_decide.c b/ft_struct/ft_rbtree_decide.c new file mode 100644 index 0000000..f69f3f7 --- /dev/null +++ b/ft_struct/ft_rbtree_decide.c @@ -0,0 +1,10 @@ +#include "ft_struct.h" + +t_rbtree_node *ft_rbtree_decide(t_rbtree_node *node, int cmp_res) +{ + if (cmp_res < 0) + return (node->left); + if (cmp_res > 0) + return (node->right); + return (NULL); +} diff --git a/ft_struct/ft_rbtree_delete.c b/ft_struct/ft_rbtree_delete.c new file mode 100644 index 0000000..0bb2631 --- /dev/null +++ b/ft_struct/ft_rbtree_delete.c @@ -0,0 +1,12 @@ +#include "ft_struct.h" + +void ft_rbtree_delete(t_rbtree *tree, void *element, void (*free_el)(void *)) +{ + t_rbtree_node *node; + + node = ft_rbtree_search_node(tree->root, element); + if (!node) + return ; + ft_rbtree_erase_node(node, free_el); + return ; +} diff --git a/ft_struct/ft_rbtree_erase_node.c b/ft_struct/ft_rbtree_erase_node.c new file mode 100644 index 0000000..8c30748 --- /dev/null +++ b/ft_struct/ft_rbtree_erase_node.c @@ -0,0 +1,105 @@ +#include "ft_struct.h" +#include "libft.h" +#include + +static void rewrite_child(t_rbtree_node *old, t_rbtree_node *new) +{ + if (new) + new->parent = old->parent; + if (!old->parent) + { + old->tree->root = new; + return ; + } + if (old->parent->left == old) + old->parent->left = new; + else + old->parent->right = new; + return ; +} + +static t_rbtree_node *get_only_child(t_rbtree_node *node) +{ + if (node->left) + return (node->left); + return (node->right); +} + +static void rebalance(t_rbtree_node *parent, t_rbtree_node *node) +{ + t_rbtree_node *sibling; + t_rbtree_node *close_nephew; + t_rbtree_node *dist_nephew; + + if (!parent) + return ; + if (parent->left == node) + { + sibling = parent->right; + close_nephew = sibling->left; + dist_nephew = sibling->right; + } + else + { + sibling = parent->left; + close_nephew = sibling->right; + dist_nephew = sibling->left; + } + if (!ft_rbtree_is_black(sibling)) + { + ft_rbtree_rotate(sibling); + rebalance(parent, node); + return ; + } + if (ft_rbtree_is_black(dist_nephew) && !ft_rbtree_is_black(close_nephew)) + { + close_nephew->is_black = 1; + sibling->is_black = 0; + ft_rbtree_rotate(close_nephew); + dist_nephew = sibling; + sibling = close_nephew; + } + if (!ft_rbtree_is_black(dist_nephew)) + { + ft_rbtree_rotate(sibling); + return ; + } + if (!ft_rbtree_is_black(parent)) + { + parent->is_black = 1; + sibling->is_black = 0; + return ; + } + rebalance(parent->parent, parent); + return ; +} + +void ft_rbtree_erase_node(t_rbtree_node *node, void (*free_el)(void *)) +{ + t_rbtree_node *helper; + + if (free_el) + free_el(&node->data); + if (node->left && node->right) + { + helper = node->right; + while (helper->left) + helper = helper->left; + ft_memcpy(&node->data, &helper->data, node->tree->el_size); + ft_rbtree_erase_node(helper, NULL); + return ; + } + if (node->left || node->right) + { + helper = get_only_child(node); + helper->is_black = 1; + rewrite_child(node, helper); + free(node); + return ; + } + rewrite_child(node, NULL); + if (node->is_black) + rebalance(node->parent, NULL); + free(node); + return ; +} diff --git a/ft_struct/ft_rbtree_free.c b/ft_struct/ft_rbtree_free.c new file mode 100644 index 0000000..7f436f6 --- /dev/null +++ b/ft_struct/ft_rbtree_free.c @@ -0,0 +1,20 @@ +#include "ft_struct.h" +#include + +static void free_node(t_rbtree_node *node, void (*free_el)(void *)) +{ + free_el(&node->data); + free_node(node->left, free_el); + free_node(node->right, free_el); + free(node->left); + free(node->right); + return ; +} + +void ft_rbtree_free(t_rbtree *tree, void (*free_el)(void *)) +{ + free_node(tree->root, free_el); + free(tree->root); + tree->root = NULL; + return ; +} diff --git a/ft_struct/ft_rbtree_helpers.c b/ft_struct/ft_rbtree_helpers.c new file mode 100644 index 0000000..cb95238 --- /dev/null +++ b/ft_struct/ft_rbtree_helpers.c @@ -0,0 +1,29 @@ +#include "ft_struct.h" + +int ft_rbtree_is_black(t_rbtree_node *node) +{ + return (!node || node->is_black); +} + +void ft_rbtree_rotate(t_rbtree_node *node) +{ + t_rbtree_node *transferred; + t_rbtree_node *parent; + + parent = node->parent; + if (node == parent->left) + { + transferred = node->right; + node->right = parent; + parent->left = transferred; + } + else + { + transferred = node->left; + node->left = parent; + parent->right = transferred; + } + node->parent = parent->parent; + parent->parent = node; + return ; +} diff --git a/ft_struct/ft_rbtree_init.c b/ft_struct/ft_rbtree_init.c new file mode 100644 index 0000000..27c2e4c --- /dev/null +++ b/ft_struct/ft_rbtree_init.c @@ -0,0 +1,11 @@ +#include "ft_struct.h" + +t_ft_stat ft_rbtree_init(t_rbtree *tree, size_t el_size, t_cmp_fun cmp_el) +{ + if (!tree || !cmp_el || el_size == 0) + return (invalid_input); + tree->el_size = el_size; + tree->cmp_el = cmp_el; + tree->root = NULL; + return (success); +} diff --git a/ft_struct/ft_rbtree_insert.c b/ft_struct/ft_rbtree_insert.c new file mode 100644 index 0000000..e8a56a5 --- /dev/null +++ b/ft_struct/ft_rbtree_insert.c @@ -0,0 +1,117 @@ +#include "ft_struct.h" +#include "libft.h" +#include + +static t_rbtree_node *get_parent(t_rbtree_node *node) +{ + if (!node) + return (NULL); + return (node->parent); +} + +static t_rbtree_node *get_sibling(t_rbtree_node *node) +{ + t_rbtree_node *const parent = get_parent(node); + + if (!parent) + return (NULL); + if (parent->left == node) + return (parent->right); + return (parent->left); +} + +static void rebalance(t_rbtree_node *node) +{ + t_rbtree_node *parent; + t_rbtree_node *grandparent; + t_rbtree_node *uncle; + + parent = get_parent(node); + grandparent = get_parent(parent); + uncle = get_sibling(parent); + if (parent && !grandparent) + parent->is_black = 1; + if (!parent || !grandparent || parent->is_black) + return ; + if (!ft_rbtree_is_black(parent) && !ft_rbtree_is_black(uncle)) + { + parent->is_black = 1; + uncle->is_black = 1; + grandparent->is_black = 0; + rebalance(grandparent); + return ; + } + if ((parent == grandparent->left) != (node == parent->left)) + { + ft_rbtree_rotate(node); + ft_swap((void **)&node, (void **)&parent); + } + parent->is_black = 1; + grandparent->is_black = 0; + ft_rbtree_rotate(parent); + return ; +} + +static t_ft_stat add_leaf(t_rbtree_node *node, void *element, int is_left) +{ + t_rbtree_node *new_node; + + new_node = malloc(sizeof(t_rbtree_node) + node->tree->el_size); + if (!new_node) + return (alloc_fail); + new_node->tree = node->tree; + new_node->parent = node; + new_node->is_black = 0; + new_node->left = NULL; + new_node->right = NULL; + ft_memcpy(&new_node->data, element, new_node->tree->el_size); + if (is_left) + node->left = new_node; + else + node->right = new_node; + rebalance(new_node); + return (success); +} + +t_ft_stat insert_root(t_rbtree *tree, void *element) +{ + t_rbtree_node *new_node; + + new_node = malloc(sizeof(t_rbtree_node) + tree->el_size); + if (!new_node) + return (alloc_fail); + new_node->is_black = 1; + new_node->tree = tree; + new_node->parent = NULL; + new_node->left = NULL; + new_node->right = NULL; + ft_memcpy(&new_node->data, element, tree->el_size); + return (success); +} + +t_ft_stat ft_rbtree_insert(t_rbtree *tree, void *element) +{ + t_cmp_fun cmp_el; + int cmp_res; + t_rbtree_node *node; + t_rbtree_node *next; + + if (!tree->root) + return (insert_root(tree, element)); + node = tree->root; + cmp_el = node->tree->cmp_el; + while (1) + { + cmp_res = cmp_el(&node->data, element); + next = ft_rbtree_decide(node, cmp_res); + if (!next) + break ; + node = next; + } + if (cmp_res == 0) + { + ft_memcpy(&node->data, element, tree->el_size); + return (success); + } + return (add_leaf(node, element, cmp_res < 0)); +} diff --git a/ft_struct/ft_rbtree_search.c b/ft_struct/ft_rbtree_search.c new file mode 100644 index 0000000..76d2ceb --- /dev/null +++ b/ft_struct/ft_rbtree_search.c @@ -0,0 +1,13 @@ +#include "ft_struct.h" + +void *ft_rbtree_search(t_rbtree *tree, void *element) +{ + t_rbtree_node *node; + + if (!tree || !element) + return (NULL); + node = ft_rbtree_search_node(tree->root, element); + if (!node) + return (NULL); + return (&node->data); +} diff --git a/ft_struct/ft_rbtree_search_node.c b/ft_struct/ft_rbtree_search_node.c new file mode 100644 index 0000000..3e3c79c --- /dev/null +++ b/ft_struct/ft_rbtree_search_node.c @@ -0,0 +1,28 @@ +#include "ft_struct.h" + +static t_rbtree_node *find_node(t_rbtree_node *node, const void *element, t_cmp_fun cmp_el) +{ + int cmp_res; + t_rbtree_node *next; + + if (!node || !cmp_el) + return (NULL); + while (1) + { + cmp_res = cmp_el(&node->data, element); + next = ft_rbtree_decide(node, cmp_res); + if (!next) + break ; + node = next; + } + if (cmp_res == 0) + return (node); + return (NULL); +} + +t_rbtree_node *ft_rbtree_search_node(t_rbtree_node *node, void *element) +{ + if (!node) + return (NULL); + return (find_node(node, element, node->tree->cmp_el)); +} diff --git a/inc/ft_struct.h b/inc/ft_struct.h index 8d4f4c1..d9d29af 100644 --- a/inc/ft_struct.h +++ b/inc/ft_struct.h @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/06/20 16:59:43 by ljiriste #+# #+# */ -/* Updated: 2025/07/31 15:07:44 by ljiriste ### ########.fr */ +/* Updated: 2025/08/01 11:23:49 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -59,6 +59,44 @@ t_ft_stat ft_tree_replace_with_child(t_tree_node *tree_node, size_t i, void (*fr t_ft_stat ft_tree_forget_child(t_tree_node *tree_node, size_t i); void ft_tree_free(t_tree *tree, void (*free_el)(void *)); +// I wanted to use t_tree_node to define binary tree and use that +// to define a red-black and AVL trees +// but because of the flexible array member it is not possible... +typedef struct s_rbtree_node t_rbtree_node; + +typedef int (*t_cmp_fun)(const void *, const void *); + +typedef struct s_rbtree +{ + size_t el_size; + t_cmp_fun cmp_el; + t_rbtree_node *root; +} t_rbtree; + +struct s_rbtree_node +{ + int is_black; + t_rbtree *tree; + t_rbtree_node *parent; + t_rbtree_node *left; + t_rbtree_node *right; + char data[]; +}; + +t_ft_stat ft_rbtree_init(t_rbtree *tree, size_t el_size, t_cmp_fun cmp_el); +void ft_rbtree_free(t_rbtree *tree, void (*free_el)(void *)); + +t_ft_stat ft_rbtree_insert(t_rbtree *tree, void *element); +void *ft_rbtree_search(t_rbtree *tree, void *element); +void ft_rbtree_delete(t_rbtree *tree, void *element, void (*free_el)(void *)); + +t_rbtree_node *ft_rbtree_search_node(t_rbtree_node *node, void *element); +void ft_rbtree_erase_node(t_rbtree_node *node, void (*free_el)(void *)); +t_rbtree_node *ft_rbtree_decide(t_rbtree_node *node, int cmp_res); + +int ft_rbtree_is_black(t_rbtree_node *node); +void ft_rbtree_rotate(t_rbtree_node *node); + # ifdef __cplusplus } # endif // __cplusplus -- 2.30.2