aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/bt/ft_btdestroy.c13
-rw-r--r--src/bt/ft_btnew.c16
-rw-r--r--src/bt/ft_btsorted_insert.c38
-rw-r--r--src/bt/ft_btsorted_search.c35
-rw-r--r--src/rbt/ft_rbtinsert.c83
-rw-r--r--src/rbt/ft_rbtnew.c35
-rw-r--r--src/rbt/ft_rbtrotate_left.c38
-rw-r--r--src/rbt/ft_rbtrotate_right.c38
8 files changed, 288 insertions, 8 deletions
diff --git a/src/bt/ft_btdestroy.c b/src/bt/ft_btdestroy.c
index c802db0..d8746ef 100644
--- a/src/bt/ft_btdestroy.c
+++ b/src/bt/ft_btdestroy.c
@@ -6,18 +6,25 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:30:53 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:35:19 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:47:45 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft_bt.h"
-void ft_btdestroy(t_ftbtree *tree, void (*del)(void *data))
+/*
+** \brief Destroy a binary tree
+** \param tree Binary tree to destroy
+** \param del Delete function applied to each node data
+*/
+
+void ft_btdestroy(t_ftbt *tree, void (*del)(void *data))
{
if (tree == NULL)
return ;
ft_btdestroy(tree->left, del);
ft_btdestroy(tree->right, del);
- (*del)(tree->data);
+ if (del != NULL)
+ del(tree->data);
free(tree);
}
diff --git a/src/bt/ft_btnew.c b/src/bt/ft_btnew.c
index 973e1a4..09cfa12 100644
--- a/src/bt/ft_btnew.c
+++ b/src/bt/ft_btnew.c
@@ -6,20 +6,26 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:33:16 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:34:35 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:46:57 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#include "libft_bt.h"
-t_ftbtree *ft_btnew(void *data)
+/*
+** \brief Create a new binary tree
+** \param data Node's data
+** \return Allocated node with left and right set to NULL, NULL on error
+*/
+
+t_ftbt *ft_btnew(void *data)
{
- t_ftbtree *tree;
+ t_ftbt *tree;
- if ((tree = (t_ftbtree*)malloc(sizeof(t_ftbtree))) == NULL)
+ if ((tree = (t_ftbt*)malloc(sizeof(t_ftbt))) == NULL)
return (NULL);
- tree->data = data;
tree->left = NULL;
tree->right = NULL;
+ tree->data = data;
return (tree);
}
diff --git a/src/bt/ft_btsorted_insert.c b/src/bt/ft_btsorted_insert.c
new file mode 100644
index 0000000..12c0cde
--- /dev/null
+++ b/src/bt/ft_btsorted_insert.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_btsorted_insert.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:10:36 by charles #+# #+# */
+/* Updated: 2020/04/26 19:19:24 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief Insert a data in a binary search tree so that it stays sorted
+** \param tree Tree where data is inserted
+** \param data Data to insert
+** \param cmp Comparison function
+** \return The new root or NULL if a new node couldn't be allocated
+*/
+
+t_ftbt *ft_btsorted_insert(t_ftbt *tree, void *data, int (*cmp)(void*, void*))
+{
+ if (tree == NULL)
+ return (ft_btnew(data));
+ if (cmp(data, tree->data) < 0)
+ {
+ if (ft_btsorted_insert(tree->left, data, cmp) == NULL)
+ return (NULL);
+ }
+ else
+ {
+ if (ft_btsorted_insert(tree->right, data, cmp) == NULL)
+ return (NULL);
+ }
+ return (tree);
+}
diff --git a/src/bt/ft_btsorted_search.c b/src/bt/ft_btsorted_search.c
new file mode 100644
index 0000000..00629d0
--- /dev/null
+++ b/src/bt/ft_btsorted_search.c
@@ -0,0 +1,35 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_btsorted_search.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:31:42 by charles #+# #+# */
+/* Updated: 2020/04/26 19:35:53 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief Search a element in a sorted binary tree
+** \param tree Searched tree
+** \param ref First argument of comparison function
+** \param cmp Comparison function
+** \return Node data if found, NULL otherwise
+*/
+
+void *ft_btsorted_search(t_ftbt *tree, void *ref, int (*cmp)(void*, void*))
+{
+ int res;
+
+ if (tree == NULL)
+ return (NULL);
+ if ((res = cmp(ref, tree->data)) == 0)
+ return (tree->data);
+ if (res < 0)
+ return (ft_btsorted_search(tree->left, ref, cmp));
+ else
+ return (ft_btsorted_search(tree->right, ref, cmp));
+}
diff --git a/src/rbt/ft_rbtinsert.c b/src/rbt/ft_rbtinsert.c
new file mode 100644
index 0000000..ce86777
--- /dev/null
+++ b/src/rbt/ft_rbtinsert.c
@@ -0,0 +1,83 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtinsert.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 19:10:36 by charles #+# #+# */
+/* Updated: 2020/04/26 21:02:52 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+static void st_insert_node(
+ t_ftrbt **root,
+ t_ftrbt *node,
+ int (*cmp)(void*, void*))
+{
+ if (*root == NULL)
+ {
+ *root = node;
+ return ;
+ }
+ if (cmp(node->data, (*root)->data) < 0)
+ st_insert_node(&(*root)->left, node->data, cmp);
+ else
+ st_insert_node(&(*root)->left, node->data, cmp);
+}
+
+static void st_repare_tree(t_ftrbt *node)
+{
+ (void)node;
+ /* t_ftrbt *parent; */
+ /* */
+ /* parent = node->parent; */
+ /* if (parent == NULL) */
+ /* node->color = FTRBT_COLOR_BLACK; */
+ /* else if (parent->color == FTRBT_COLOR_BLACK) */
+ /* return ; */
+ /* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_RED) */
+ /* { */
+ /* parent->color == FTRBT_COLOR_BLACK; */
+ /* uncle->color = FTRBT_COLOR_BLACK; */
+ /* parent->parent->color = FTRBT_COLOR_RED; */
+ /* st_repare_tree(parent->parent); */
+ /* } */
+ /* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_BLACK) */
+ /* { */
+ /* if (node == parent->right && parent == parent->parent->left) */
+ /* { */
+ /* ft_rbtrotate_left(parent); */
+ /* node = node->left; */
+ /* } */
+ /* else if (node == parent->left && parent == parent->parent->right) */
+ /* { */
+ /* ft_rbtrotate_right(parent); */
+ /* node = node->right; */
+ /* } */
+ /* if (node == parent->left) */
+ /* ft_rbtrotate_right(parent); */
+ /* else */
+ /* ft_rbtrotate_left(parent); */
+ /* parent->color = FTRBT_COLOR_BLACK; */
+ /* parent->parent->color = FTRBT_COLOR_RED; */
+ /* } */
+}
+
+t_ftrbt *ft_rbtinsert(
+ t_ftrbt *tree,
+ void *data,
+ int (*cmp)(void*, void*))
+{
+ t_ftrbt *node;
+
+ if ((node = ft_rbtnew(data, FTRBT_COLOR_RED)) == NULL)
+ return (NULL);
+ st_insert_node(&tree, node, cmp);
+ st_repare_tree(node);
+ while (node->parent != NULL)
+ node = node->parent;
+ return node;
+}
diff --git a/src/rbt/ft_rbtnew.c b/src/rbt/ft_rbtnew.c
new file mode 100644
index 0000000..bda7d55
--- /dev/null
+++ b/src/rbt/ft_rbtnew.c
@@ -0,0 +1,35 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtnew.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 20:22:07 by charles #+# #+# */
+/* Updated: 2020/04/26 20:24:44 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Create a new red-black tree
+** \param data Node's data
+** \param color Node's color
+** \return The created node with left, right and parent pointer to NULL
+** or NULL on error
+*/
+
+t_ftrbt *ft_rbtnew(void *data, enum e_ftrbt_color color)
+{
+ t_ftrbt *tree;
+
+ if ((tree = (t_ftrbt*)malloc(sizeof(t_ftrbt))) == NULL)
+ return (NULL);
+ tree->left = NULL;
+ tree->right = NULL;
+ tree->data = data;
+ tree->parent = NULL;
+ tree->color = color;
+ return (tree);
+}
diff --git a/src/rbt/ft_rbtrotate_left.c b/src/rbt/ft_rbtrotate_left.c
new file mode 100644
index 0000000..7cff65d
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_left.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtrotate_left.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 18:03:35 by charles #+# #+# */
+/* Updated: 2020/04/26 20:27:44 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Rotate a red-black tree to the left
+** \param tree Pointer to Pointer to a red-black tree
+**
+** 5 10
+** / \ / \
+** 4 10 --> 5 11
+** / \ / \
+** 6 11 4 6
+*/
+
+void ft_rbtrotate_left(t_ftrbt **tree)
+{
+ t_ftrbt *new_root;
+ t_ftrbt *tmp;
+
+ if (tree == NULL || *tree == NULL || (*tree)->right == NULL)
+ return ;
+ new_root = (*tree)->right;
+ tmp = new_root->left;
+ new_root->left = *tree;
+ (*tree)->right = tmp;
+ *tree = new_root;
+}
diff --git a/src/rbt/ft_rbtrotate_right.c b/src/rbt/ft_rbtrotate_right.c
new file mode 100644
index 0000000..46d72e2
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_right.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* ft_rbtrotate_right.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 18:10:57 by charles #+# #+# */
+/* Updated: 2020/04/26 20:27:53 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief Rotate a red-black tree to the right
+** \param tree Pointer to Pointer to a red-black tree
+**
+** 10 5
+** / \ / \
+** 5 11 --> 4 10
+** / \ / \
+** 4 6 6 11
+*/
+
+void ft_rbtrotate_right(t_ftrbt **tree)
+{
+ t_ftrbt *new_root;
+ t_ftrbt *tmp;
+
+ if (tree == NULL || *tree == NULL || (*tree)->left == NULL)
+ return ;
+ new_root = (*tree)->left;
+ tmp = new_root->right;
+ new_root->right = *tree;
+ (*tree)->left = tmp;
+ *tree = new_root;
+}
generated by cgit (git 2.34.1) at 2026-05-16 10:17:16 +0000