Balanced binary search trees class. More...

#include <BalBstSet.h>

Inheritance diagram for grafalgo::BalBstSet:

Collaboration diagram for grafalgo::BalBstSet:

Public Member Functions
	BalBstSet (int)
	Constructor for BalBstSet class.
	~BalBstSet ()
	Destructor for BalBstSet class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a BalBstSet object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const BalBstSet &)
	Copy another object to this one.
bool	insert (index, bst &)
	Insert a singleton tree into a bst (bst) in the collection.
void	remove (index, bst &)
	Remove an item from a bst.
bst	join (bst, index, bst)
	Join two bsts at an item.
BstSet::BstPair	split (index, bst)
	Divide a bst on an item (not implemented at this time).
Protected Member Functions
void	swap (index, index)
	Swap the positions of two nodes in the same tree.
string &	node2string (index, string &) const
	Create a string representing an item.
void	makeSpace (int)
	Allocate and initialize space for BalBstSet.
void	freeSpace ()
	Free dynamic storage used by BalBstSet.
Protected Attributes
int *	rvec
	rvec[x] is the "rank" of node x

Detailed Description

Balanced binary search trees class.

Represents a collection of balanced BSTs, defined on indexes 1..n. Each BST corresponds to a "sorted set" and each node corresponds to an "item", where each item can appear in only one set at a time (possibly a singleton set).

Inherits some methods from the SortedSets class.

Definition at line 23 of file BalBstSet.h.

Constructor & Destructor Documentation

grafalgo::BalBstSet::BalBstSet ( int size )

Constructor for BalBstSet class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 21 of file BalBstSet.cpp.

Here is the call graph for this function:

grafalgo::BalBstSet::~BalBstSet ( )

Destructor for BalBstSet class.

Definition at line 26 of file BalBstSet.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::BalBstSet::clear ( ) [virtual]

Reinitialize data structure, creating single node trees.

Reimplemented from grafalgo::BstSet.

Definition at line 50 of file BalBstSet.cpp.

Here is the caller graph for this function:

void grafalgo::BalBstSet::copyFrom ( const BalBstSet & source )

Copy another object to this one.

Parameters:

source is object to be copied to this one

Definition at line 82 of file BalBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::BalBstSet::expand ( int size ) [virtual]

Expand the space available for this ojbect.

Rebuilds old value in new space.

Parameters:

size	is the size of the expanded object.

Reimplemented from grafalgo::BstSet.

Definition at line 74 of file BalBstSet.cpp.

Here is the call graph for this function:

void grafalgo::BalBstSet::freeSpace ( ) [protected]

Free dynamic storage used by BalBstSet.

Reimplemented from grafalgo::BstSet.

Definition at line 45 of file BalBstSet.cpp.

Here is the caller graph for this function:

bool grafalgo::BalBstSet::insert	(	index	i,
		bst &	t
	)

Insert a singleton tree into a bst (bst) in the collection.

Parameters:

i	is an item (node) to be inserted; it must be a singleton
t	is a reference to the root of the bst that i is to be added to; if the operation changes the root then t will be changed

Returns:: true on success, false on failure

Reimplemented from grafalgo::BstSet.

Definition at line 111 of file BalBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bst grafalgo::BalBstSet::join	(	bst	t1,
		index	i,
		bst	t2
	)

Join two bsts at an item.

Parameters:

t1	is the root of some bst
t2	is the root of some bst
i	is a singleton i whose key is larger than that of the keys in t1 and smaller than that of the keys in t2

Returns:: the new bst that results from merging t1, i and t2

Reimplemented from grafalgo::BstSet.

Definition at line 213 of file BalBstSet.cpp.

void grafalgo::BalBstSet::makeSpace ( int size ) [protected]

Allocate and initialize space for BalBstSet.

Parameters:

size	is number of index values to provide space for

Reimplemented from grafalgo::BstSet.

Definition at line 31 of file BalBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::BalBstSet::node2string	(	index	i,
		string &	s
	)		const `[protected, virtual]`

Create a string representing an item.

Parameters:

i	is an item in some bst
s	is a string in which the result is to be returned

Returns:: a reference to s

Reimplemented from grafalgo::BstSet.

Definition at line 235 of file BalBstSet.cpp.

Here is the call graph for this function:

void grafalgo::BalBstSet::remove	(	index	i,
		bst &	t
	)

Remove an item from a bst.

Parameters:

i	is the item to be removed
t	is a reference to the root of the bst containing i; if the operation changes the root, s will be changed to reflect that

Reimplemented from grafalgo::BstSet.

Definition at line 136 of file BalBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::BalBstSet::resize ( int size ) [virtual]

Resize a BalBstSet object, discarding old value.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::BstSet.

Definition at line 61 of file BalBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

BstSet::BstPair grafalgo::BalBstSet::split	(	index	i,
		bst	t
	)

Divide a bst on an item (not implemented at this time).

Parameters:

i	is an item in some bst
t	is the root of the bst containing i

Returns:: the pair of bst that results from splitting t into three parts; the part with keys smaller than i, i itself, and the part with keys larger than i

Reimplemented from grafalgo::BstSet.

Definition at line 225 of file BalBstSet.cpp.

void grafalgo::BalBstSet::swap	(	index	i,
		index	j
	)		`[protected, virtual]`

Swap the positions of two nodes in the same tree.

Parameters:

i	is a node in a search tree
j	is another node in the same tree, which is not the parent of i; this is a helper method for the remove method; it exchanges the positions of the nodes in the tree

Reimplemented from grafalgo::BstSet.

Definition at line 99 of file BalBstSet.cpp.

Here is the caller graph for this function:

The documentation for this class was generated from the following files:

/Users/jst/src/grafalgo/cpp/include/BalBstSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/BalBstSet.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation