Binary search tree of int (no balancing — O(log n) average, O(n) worst-case on sorted input). More...

#include <stdbool.h>
#include <stddef.h>

Typedefs
typedef struct bst	bst_t

Functions
bool	bst_contains (const bst_t *t, int value)

bst_t *	bst_create (void)

void	bst_destroy (bst_t *t)

void	bst_in_order (const bst_t t, void(visit)(int value, void ctx), void ctx)

bool	bst_insert (bst_t *t, int value)

bool	bst_max (const bst_t t, int out_value)

bool	bst_min (const bst_t t, int out_value)

size_t	bst_size (const bst_t *t)

Detailed Description

Binary search tree of int (no balancing — O(log n) average, O(n) worst-case on sorted input).

Operations:

op	average	worst
insert	O(log n)	O(n)
contains	O(log n)	O(n)
min / max	O(log n)	O(n)
in_order	O(n)	O(n)

Definition in file bst.h.

Typedef Documentation

◆ bst_t

typedef struct bst bst_t

Definition at line 21 of file bst.h.

Function Documentation

◆ bst_contains()

bool bst_contains	(	const bst_t *	t,
		int	value
	)

Definition at line 84 of file bst.c.

References bst_node::left, bst_node::right, bst::root, and bst_node::value.

◆ bst_create()

bst_t * bst_create ( void )

Definition at line 23 of file bst.c.

References bst::root, and bst::size.

◆ bst_destroy()

void bst_destroy ( bst_t * t )

Definition at line 38 of file bst.c.

References destroy_subtree(), and bst::root.

◆ bst_in_order()

void bst_in_order	(	const bst_t *	t,
		void()(int value, void ctx)	visit,
		void *	ctx
	)

Visits every node in ascending order, calling visit on each value.

◆ bst_insert()

bool bst_insert	(	bst_t *	t,
		int	value
	)

Inserts value. Duplicates are ignored. Returns true on success.

Definition at line 52 of file bst.c.

References bst_node::left, make_node(), bst_node::right, bst::root, bst::size, and bst_node::value.

◆ bst_max()

bool bst_max	(	const bst_t *	t,
		int *	out_value
	)

Definition at line 103 of file bst.c.

References bst_node::right, bst::root, and bst_node::value.

◆ bst_min()

bool bst_min	(	const bst_t *	t,
		int *	out_value
	)

Definition at line 95 of file bst.c.

References bst_node::left, bst::root, and bst_node::value.

◆ bst_size()

size_t bst_size ( const bst_t * t )

Definition at line 111 of file bst.c.

References bst::size.

Typedefs

Functions