diff options
Diffstat (limited to 'include/libft_rbt.h')
| -rw-r--r-- | include/libft_rbt.h | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/include/libft_rbt.h b/include/libft_rbt.h new file mode 100644 index 0000000..6865cdf --- /dev/null +++ b/include/libft_rbt.h @@ -0,0 +1,95 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* libft_rbt.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2020/04/26 16:09:51 by charles #+# #+# */ +/* Updated: 2020/05/11 16:11:16 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 |