aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/libft_bt.h37
-rw-r--r--include/libft_rbt.h96
-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
10 files changed, 413 insertions, 16 deletions
diff --git a/include/libft_bt.h b/include/libft_bt.h
index 6e2cc91..7bd7eb4 100644
--- a/include/libft_bt.h
+++ b/include/libft_bt.h
@@ -6,23 +6,44 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/02/07 21:26:34 by cacharle #+# #+# */
-/* Updated: 2020/02/07 21:34:52 by cacharle ### ########.fr */
+/* Updated: 2020/04/26 19:45:56 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#ifndef LIBFT_BT_H
# define LIBFT_BT_H
+/*
+** \file libft_bt.h
+** \brief Binary tree
+*/
+
# include <stdlib.h>
-typedef struct s_ftbtree
+/*
+** \brief Binary tree struct
+** \param left Left node
+** \param right Right node
+** \param data Node data
+*/
+
+typedef struct s_ftbt
{
- void *data;
- struct s_ftbtree *left;
- struct s_ftbtree *right;
-} t_ftbtree;
+ struct s_ftbt *left;
+ struct s_ftbt *right;
+ void *data;
+} t_ftbt;
+
+t_ftbt *ft_btnew(void *data);
+void ft_btdestroy(t_ftbt *tree, void (*del)(void *data));
-t_ftbtree *ft_btnew(void *data);
-void ft_btdestroy(t_ftbtree *tree, void (*del)(void *data));
+t_ftbt *ft_btsorted_insert(
+ t_ftbt *tree,
+ void *data,
+ int (*cmp)(void*, void*));
+void *ft_btsorted_search(
+ t_ftbt *tree,
+ void *ref,
+ int (*cmp)(void*, void*));
#endif
diff --git a/include/libft_rbt.h b/include/libft_rbt.h
new file mode 100644
index 0000000..57653cc
--- /dev/null
+++ b/include/libft_rbt.h
@@ -0,0 +1,96 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* libft_rbt.h :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/04/26 16:09:51 by charles #+# #+# */
+/* Updated: 2020/04/26 20:25:36 by charles ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#ifndef LIBFT_RBT_H
+# define LIBFT_RBT_H
+
+/*
+** \file libft_rbt.h
+** \brief Red-black tree
+**
+** Rules: (from wikipedia)
+** 1. Each node is either red or black.
+** 2. The root is black. This rule is sometimes omitted. Since the root can
+** always be changed from red to black, but not necessarily vice versa,
+** this rule has little effect on analysis.
+** 3. All leaves (NULL) are black.
+** 4. If a node is red, then both its children are black.
+** 5. Every path from a given node to any of its descendant NULL nodes goes
+** through the same number of black nodes.
+**
+**
+** Unbalance case:
+**
+** 1. Node and parent are both red
+**
+** B1
+** \ left rot color swap
+** > R2 --> R2 --> B2
+** \ / \ / \
+** > R3 B1 R3 R1 R3
+**
+** 2. Node and parent are both red and uncle node is red
+**
+** B2 R2
+** / \ color swap / \
+** uncle> R1 R3 --> B1 B3
+** \ \
+** R4 R4
+*/
+
+# include <stdlib.h>
+
+/*
+** \brief Red-black tree color enum
+** \param FTRBT_COLOR_RED color red
+** \param FTRBT_COLOR_BLACK color black
+*/
+
+enum e_ftrbt_color
+{
+ FTRBT_COLOR_RED = 0,
+ FTRBT_COLOR_BLACK,
+};
+
+/*
+** \brief Red-black tree struct
+** \param left Left node
+** \param right Right node
+** \param data Pointer to data
+** \param parent Parent node
+** \param color Color of the node
+** \note The first 3 attricutes are the same
+** as t_ftbt (binary tree) struct
+** which means that we can use all functions
+** of binary tree on red-black tree.
+*/
+
+typedef struct s_ftrbt
+{
+ struct s_ftrbt *left;
+ struct s_ftrbt *right;
+ void *data;
+ struct s_ftrbt *parent;
+ enum e_ftrbt_color color;
+} t_ftrbt;
+
+t_ftrbt *ft_rbtnew(void *data, enum e_ftrbt_color color);
+void ft_rbtrotate_right(t_ftrbt **tree);
+void ft_rbtrotate_left(t_ftrbt **tree);
+
+t_ftrbt *ft_rbtinsert(
+ t_ftrbt *tree,
+ void *data,
+ int (*cmp)(void*, void*));
+
+
+#endif
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 14:45:43 +0000