src/randbst.h File Reference

A self-balancing binary search tree that uses randomness to ensure the tree is balanced. More...

#include <stdlib.h>
#include <stdbool.h>
#include "cdsa_types.h"

Include dependency graph for randbst.h:

Go to the source code of this file.

Typedefs
typedef struct RandBst	RandBst
	A RandBst is a randomized binary search tree, as described above.
Functions
Core Functions
cdsa_status_t	randbst_new (RandBst **tree, cdsa_compare_func_t compare, cdsa_destroy_map_func_t destroy)
	Create a new binary search tree using the given compare function for ordering the nodes, setting *tree to the new tree if successful.
cdsa_status_t	randbst_destroy (RandBst **tree)
	Destroy *tree and free associated memory, setting *tree to NULL on success.
cdsa_status_t	randbst_is_empty (const RandBst *const tree, bool *is_empty)
	Answer if the tree contains at least 1 (key, value) pair, recording answer in *is_empty.
cdsa_status_t	randbst_size (const RandBst *const tree, size_t *size)
	Answer the size of tree, recording result in *size.
cdsa_status_t	randbst_has_key (const RandBst *const tree, const void *const key, bool *has_key)
	Answer whether tree contains key, recording result in *has_key.
cdsa_status_t	randbst_get (const RandBst *const tree, const void *const key, void *ptr)
	Answer the value, if any, for the key in tree, recording the value in *ptr if there is a value.
cdsa_status_t	randbst_put (RandBst *const tree, const void *const key, const void *const value, void *prev_val)
	Put the (key, value) pair in the tree, setting the *prev_val pointer to the previous value for the given key if there was already a value in the tree for the key.
cdsa_status_t	randbst_remove (RandBst *const tree, void *const key, void *prev_val)
	Remove the (key, value) pair with the given key from the tree, setting *prev_val to the removed value on success.

---

Detailed Description

A self-balancing binary search tree that uses randomness to ensure the tree is balanced.

randbst stores only pointers to client data, and all memory management of the keys and values is the responsibility of the client. A NULL value is permitted, but NULL keys are not. For a default-type value, create a unique NIL pointer and use that as the key. Duplicate keys are also not permitted. Adding a value for a key that is already in the tree (i.e., a key equal according to the comparison function) results in the former value being replaced by the new value, and the old value is returned.

The client may optionally supply a function when creating a new randbst for performing book-keeping tasks when the tree is destroyed (via randbst_destroy). If such a function is supplied, it is called once for every (key, value) pair in the tree during an in-order traversal.

This implementation of a binary search tree randomly inserts new elements anywhere along the search path for that element. The tree is built using no more than about 2N ln N comparisons for N items, and the resultant tree requires no more than about 2 ln N comparisons for a search. Each key inserted is equally likely to end up at the root of the tree (and this holds for sub-keys too).

Building a randomized binary search tree is equivalent to randomly permuting a list of keys to be inserted and then inserting them into a normal binary search tree.

This implementation is based on the Java implementation in Sedgewick's _Algorithms in Java_, 3rd edition.

Definition in file randbst.h.

---

Typedef Documentation

typedef struct RandBst RandBst

A RandBst is a randomized binary search tree, as described above.

It is incompletely defined here so that clients may only use it via the API exposed in this header file.

Definition at line 50 of file randbst.h.

---

Function Documentation

cdsa_status_t randbst_new	(	RandBst **	tree,
		cdsa_compare_func_t	compare,
		cdsa_destroy_map_func_t	destroy
	)

Create a new binary search tree using the given compare function for ordering the nodes, setting *tree to the new tree if successful.

Parameters:

	tree	A non-NULL pointer to a RandBst pointer, which will be set to the new tree on success.
	compare	A non-NULL function for comparing the keys of elements in the tree.
	destroy	A function to be applied to every (key, value) pair in the tree when randbst_destroy is called, or NULL.

cdsa_status_t randbst_destroy

(

RandBst **

tree

)

Destroy *tree and free associated memory, setting *tree to NULL on success.

If a destroy function was specified when the tree was created, it will be called on every (key, value) pair in the tree.

Parameters:

tree

A non-NULL pointer to a non-NULL RandBst pointer, which will be set to NULL on success.

cdsa_status_t randbst_is_empty	(	const RandBst *const	tree,
		bool *	is_empty
	)

Answer if the tree contains at least 1 (key, value) pair, recording answer in *is_empty.

Parameters:

	tree	A non-NULL tree.
	is_empty	A non-NULL pointer to a bool variable, to be set to true if tree is empty and false if it contains elements.

cdsa_status_t randbst_size	(	const RandBst *const	tree,
		size_t *	size
	)

Answer the size of tree, recording result in *size.

The size of the tree is the number of (key, value) pairs in the tree.

This function operates in constant time.

Parameters:

	tree	A non-NULL tree.
	size	A pointer to a size_t variable, which will be set to the size on success.

cdsa_status_t randbst_has_key	(	const RandBst *const	tree,
		const void *const	key,
		bool *	has_key
	)

Answer whether tree contains key, recording result in *has_key.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	has_key	A non-NULL pointer to a bool variable for recording answer on success.

Returns:

true if tree and key are both non-NULL and there is a (key, value) pair for the key in the tree.

cdsa_status_t randbst_get	(	const RandBst *const	tree,
		const void *const	key,
		void *	ptr
	)

Answer the value, if any, for the key in tree, recording the value in *ptr if there is a value.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	ptr	A non-NULL pointer to a client pointer for storing the value for the given key on success.

Returns:

If key was in tree and value was retrieved, returns CDSA_SUCCESS; if not in tree, returns CDSA_NO_RESULT; other codes indicate an error. *

cdsa_status_t randbst_put	(	RandBst *const	tree,
		const void *const	key,
		const void *const	value,
		void *	prev_val
	)

Put the (key, value) pair in the tree, setting the *prev_val pointer to the previous value for the given key if there was already a value in the tree for the key.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	value	The value, possibly NULL.
	prev_val	A non-NULL pointer to a client pointer for storing the previous value for the key if there was one.

cdsa_status_t randbst_remove	(	RandBst *const	tree,
		void *const	key,
		void *	prev_val
	)

Remove the (key, value) pair with the given key from the tree, setting *prev_val to the removed value on success.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	prev_val	A non-NULL pointer to a client pointer for storing the value for the key if there was one.

Returns:

If key was in tree and was removed, returns CDSA_SUCCESS; if not in tree, returns CDSA_NO_RESULT; other codes indicate an error.