data_structures
rbt_nth.c
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* rbt_nth.c :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/09/07 23:10:59 by unite #+# #+# */
10 /* Updated: 2020/09/07 23:48:13 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #include "rbt.h"
15 #include "rbt_utils.h"
16 
17 void *rbt_nth_recur(const t_rbt *rbt, const t_rbt_node *node, size_t n)
18 {
19  size_t rank;
20 
21  rank = rbt_size_subtree(node->left);
22  if (n == rank)
23  return (node->key);
24  if (n < rank)
25  return (rbt_nth_recur(rbt, node->left, n));
26  else
27  return (rbt_nth_recur(rbt, node->right, n - rank - 1));
28 }
29 
30 void *rbt_nth(const t_rbt *rbt, size_t n)
31 {
32  if (n > rbt_size(rbt))
33  return (NULL);
34  return (rbt_nth_recur(rbt, rbt->root, n));
35 }
s_rbt
A left-leaning red-black binary search tree.
Definition: rbt.h:72
rbt_nth
void * rbt_nth(const t_rbt *rbt, size_t n)
Returns the key of the nth element in the tree.
Definition: rbt_nth.c:30
s_rbt_node::right
struct s_rbt_node * right
The right child.
Definition: rbt.h:56
rbt_size
size_t rbt_size(const t_rbt *rbt)
Returns the number of elements in this tree.
Definition: rbt_size.c:17
s_rbt_node::left
struct s_rbt_node * left
The left child.
Definition: rbt.h:55
s_rbt_node::key
void * key
The key.
Definition: rbt.h:53
rbt.h
rbt_utils.h
s_rbt_node
A node in a red-black tree.
Definition: rbt.h:51
s_rbt::root
t_rbt_node * root
The root of the tree.
Definition: rbt.h:74