data_structures
src
data_structures
rbt
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
Generated by
1.8.16