bst.c File Reference

#include "bst.h"
#include <stdlib.h>

Go to the source code of this file.

Classes
struct	bst
struct	bst_node

Typedefs
typedef struct bst_node	bst_node_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, void *), 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)
static void	destroy_subtree (bst_node_t *n)
static void	in_order_recursive (const bst_node_t *n, void(*visit)(int, void *), void *ctx)
static bst_node_t *	make_node (int v)

Detailed Description

Plain binary search tree, no rebalancing. Sufficient for teaching the recursive structure; production code would reach for a red-black tree or AVL.

Definition in file bst.c.

Typedef Documentation

bst_node_t

typedef struct bst_node bst_node_t

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, void *)	visit,
		void *	ctx
	)

Definition at line 122 of file bst.c.

References in_order_recursive(), and bst::root.

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.

destroy_subtree()

static void destroy_subtree ( bst_node_t *  n )

static

Definition at line 31 of file bst.c.

References destroy_subtree(), bst_node::left, and bst_node::right.

Referenced by bst_destroy(), and destroy_subtree().

in_order_recursive()

static void in_order_recursive ( const bst_node_t *  n, void(*)(int, void *)  visit, void *  ctx  )

static

Definition at line 113 of file bst.c.

References in_order_recursive(), bst_node::left, bst_node::right, and bst_node::value.

Referenced by bst_in_order(), and in_order_recursive().

make_node()

static bst_node_t * make_node ( int  v )

static

Definition at line 44 of file bst.c.

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

Referenced by bst_insert().