data_structures
rbt_height.c
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* rbt_height.c :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/07/18 14:34:08 by unite #+# #+# */
10 /* Updated: 2020/07/18 16:56:37 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #include "rbt.h"
15 
16 static size_t rbt_height_recur(const t_rbt *rbt, const t_rbt_node *node)
17 {
18  size_t left_height;
19  size_t right_height;
20 
21  if (node == NULL)
22  return (0);
23  left_height = rbt_height_recur(rbt, node->left);
24  right_height = rbt_height_recur(rbt, node->right);
25  return (1 + (left_height > right_height ? left_height : right_height));
26 }
27 
28 size_t rbt_height(const t_rbt *rbt)
29 {
30  return (rbt_height_recur(rbt, rbt->root));
31 }
s_rbt
A left-leaning red-black binary search tree.
Definition: rbt.h:72
s_rbt_node::right
struct s_rbt_node * right
The right child.
Definition: rbt.h:56
s_rbt_node::left
struct s_rbt_node * left
The left child.
Definition: rbt.h:55
rbt.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
rbt_height
size_t rbt_height(const t_rbt *rbt)
Returns the number of tiers in the tree.
Definition: rbt_height.c:28