RedBlackTree< Key, Data > Class Template Reference

A very fast red-black tree implementation. More...

#include <rbtree.h>

List of all members.

Public Member Functions
	RedBlackTree ()
	The constructor.
	~RedBlackTree ()
	The destructor.
bool	insert (Key const &_key, Data const &_rec)
	Inserts data into the tree.
bool	replace (Key const &_key, Data const &_rec)
	Change the data at the given node.
bool	erase (Key const &_key)
	Deletes a node from the tree, specified by the node's key.
bool	erase (Key const &_key, Data const &_rec)
	Deletes a node from the tree, specified by the node's key and data.
bool	find (Key const &_key, Data &_data) const
	Finds a node in the tree and copies the data from that node to a specified location.
Data	find (Key const &_key) const
	Finds a node in the tree and returns the data at that node.
void	empty ()
	Empties the entire tree.
size_t	size () const
	Indicates the size of the tree.
bool	exists (Key const &_key) const
	Tests whether a key is in the tree or not.
DArray< Data > *	ConvertToDArray () const
	Converts the tree data into a linearized DArray.
DArray< Key > *	ConvertIndexToDArray () const
	Converts the tree keys into a linearized DArray.
size_t	mem_usage () const
	Returns the overhead caused by the data structure.
Protected Member Functions
bool	valid (const RedBlackNode< Key, Data > *_node) const
	Verifies that a node is valid.
Protected Attributes
RedBlackNode< Key, Data > *	rootNode
	The root node at the top of the tree.
RedBlackNode< Key, Data > *	nullNode
	The "null" node. Added so we don't need special cases to check for null pointers.
size_t	m_cachedSize
	The cached size() return value. Changes on each tree modification (insertions and deletions).
Private Member Functions
	RedBlackTree (const RedBlackTree< Key, Data > &)
	Private copy constructor.
RedBlackTree< Key, Data > &	operator= (const RedBlackTree< Key, Data > &)
	Private assignment operator.
Friends
class	RedBlackNode

---

Detailed Description

template<class Key, class Data>
class CrissCross::Data::RedBlackTree< Key, Data >

A very fast red-black tree implementation.

Red-black trees are complex, but have good worst-case running time for their operations and are efficient in practice: they can search, insert, and delete in O(log n) time, where n is total number of elements in the tree.

---

Constructor & Destructor Documentation

RedBlackTree

(

const RedBlackTree< Key, Data > &

)

[private]

Private copy constructor.

If your code needs to invoke the copy constructor, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

---

Member Function Documentation

DArray<Key>* ConvertIndexToDArray

(

)

const

Converts the tree keys into a linearized DArray.

Returns:

A DArray containing the keys in the tree.

Warning:

Delete the returned DArray when done with it.

DArray<Data>* ConvertToDArray

(

)

const

Converts the tree data into a linearized DArray.

Returns:

A DArray containing the data of the tree.

Warning:

Delete the returned DArray when done with it.

void empty

(

)

[inline]

Empties the entire tree.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately. The preferred way to do this is to serialize the data into a DArray with ConvertToDArray() and then iterate through it to delete the data in whatever way is proper.

bool erase	(	Key const &	_key,
		Data const &	_rec
	)

Deletes a node from the tree, specified by the node's key and data.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately.

Parameters:

	_key	The key of the node to delete.
	_rec	The data of the node to delete.

Returns:

True on success, false on failure.

bool erase

(

Key const &

_key

)

Deletes a node from the tree, specified by the node's key.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately.

Parameters:

_key

The key of the node to delete.

Returns:

True on success, false on failure

bool exists

(

Key const &

_key

)

const

Tests whether a key is in the tree or not.

Parameters:

_key

The key of the node to find.

Returns:

True if the key is in the tree, false if not.

Data find

(

Key const &

_key

)

const

Finds a node in the tree and returns the data at that node.

Parameters:

_key

The key of the node to find.

Returns:

The data at the node. NULL if not found.

Deprecated:

The return value of this function could be unpredictable if the contents of the table was anything but pointers or integers.

See also:

find

bool find	(	Key const &	_key,
		Data &	_data
	)			const

Finds a node in the tree and copies the data from that node to a specified location.

Parameters:

	_key	The key of the node to find.
	_data	On return, will contain the data at the node. If not found, _data does not change.

Returns:

True on success, false on failure.

bool insert	(	Key const &	_key,
		Data const &	_rec
	)

Inserts data into the tree.

Parameters:

	_key	The key of the data.
	_rec	The data to insert.

Returns:

True on success, false on failure.

size_t mem_usage

(

)

const

Returns the overhead caused by the data structure.

Returns:

Memory usage in bytes.

RedBlackTree<Key, Data>& operator=

(

const RedBlackTree< Key, Data > &

)

[private]

Private assignment operator.

If your code needs to invoke the assignment operator, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

bool replace	(	Key const &	_key,
		Data const &	_rec
	)

Change the data at the given node.

Parameters:

	_key	The key of the node to be modified.
	_rec	The data to insert.

Returns:

True on success, false on failure.

size_t size

(

)

const [inline]

Indicates the size of the tree.

Returns:

Size of the tree.

bool valid

(

const RedBlackNode< Key, Data > *

_node

)

const [inline, protected]

Verifies that a node is valid.

Parameters:

_node

A node pointer.

Returns:

True if the node is a valid node, false otherwise.

---

Friends And Related Function Documentation

friend class RedBlackNode [friend]