Added ft_btsorted_insert, ft_btsorted_search, Red-black tree struct (not tested)

4 files changed, 94 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));
+}