A tree class which holds strings in a binary balanced tree. More...

#include <TreeStringSet.hpp>

Classes
struct	Element

class	Iterator

Public Types
using	iterator = Iterator

Public Member Functions
	TreeStringSet ()
	Constructs empty TreeStringSet. More...

	~TreeStringSet ()
	Destroys the TreeStringSet, and all elements stored on heap.

void	deleteSubTree (Element *root)
	Helper function for Destructor. Recursively deletes each subtree. More...

size_t	size () const
	Returns the size of the entire tree. More...

void	insert (const string &insertee)
	Inserts a new element into the tree. Creates the element from string and inserts it. More...

bool	exists (const string &checkee)
	Checks if a string exists in a tree. More...

void	showStatistics (std::ostream &out)
	Prints statistics about the tree in the format height, size, size of a perfect tree of this height, percent full. More...

int	height ()
	Returns the height of the tree. More...

std::ostream &	print (std::ostream &out)
	Prints the tree. More...

bool	empty () const
	Determines if tree is empty. More...

void	rotateRight (Element *&top)
	Helper function for Insert. Rotates a given subtree to the right. More...

void	rotateLeft (Element *&top)
	Helper function for Insert, rotates subtree left. More...

iterator	begin () const
	Creates an iterator at the begining of the tree. More...

iterator	end () const
	Creates an iterator at the end of the tree. More...

Private Member Functions
bool	existsAt (const Element *element, const string &checkee)
	Helper function for exists. Recursively goes through tree to determine if the string is there. Taken from CS70 Wiki day 12. More...

void	insertRandom (Element &atElement, Element &newElement)
	Helper for insert. Makes the random choice to insert at the root or child of a subtree. More...

void	insertRoot (Element &atElement, Element &newElement)
	Helper for insert. Inserts a new element as the root of a subtree. More...

int	heightHelp (Element *&elem, int height)
	Helper for height. Recursively determines height of each subtree. More...

void	printHelper (Element *&elem, string &result)
	Helper function for print. Recursively goes through the tree, adding each element to the print. More...

Private Attributes
Element *	root_
	Pointer to the root of the tree.

size_t	size_
	Size of the tree.

Detailed Description

A tree class which holds strings in a binary balanced tree.

Class allocates memory dynamically; thus can't use C++'s defaults for copy constructor, assignment operator and destructor.

Constructor & Destructor Documentation

TreeStringSet::TreeStringSet ( )

Constructs empty TreeStringSet.

Returns: Constructor does not return

Member Function Documentation

TreeStringSet::iterator TreeStringSet::begin ( ) const

Creates an iterator at the begining of the tree.

Returns: Iterator at the leftmost leaf of the tree

void TreeStringSet::deleteSubTree ( Element * root )

Helper function for Destructor. Recursively deletes each subtree.

Parameters

root	Pointer to the root of the subtree

bool TreeStringSet::empty ( ) const

Determines if tree is empty.

Returns: True is the tree is empty, false otherwise

TreeStringSet::iterator TreeStringSet::end ( ) const

Creates an iterator at the end of the tree.

Returns: Iterator at the rightmost leaf of the tree

bool TreeStringSet::exists ( const string & checkee )

Checks if a string exists in a tree.

Returns: True if string is in tree, false else

Parameters

checkee String being checked for existence

bool TreeStringSet::existsAt	(	const Element *	element,
		const string &	checkee
	)

private

Helper function for exists. Recursively goes through tree to determine if the string is there.
Taken from CS70 Wiki day 12.

Returns: True if string is in tree, false else

Parameters

element	Pointer to the element in the tree being compared
checkee	String being checked for existence

int TreeStringSet::height ( )

Returns the height of the tree.

Returns: int Height

int TreeStringSet::heightHelp	(	Element *&	elem,
		int	height
	)

private

Helper for height. Recursively determines height of each subtree.

Returns: int of the height of the tallest subtree

Parameters

elem	Pointer to the root of the subtree being checked
height	Current height of the tallest subtree

void TreeStringSet::insert ( const string & insertee )

Inserts a new element into the tree. Creates the element from string and inserts it.

Parameters

insertee Reference to a string to be inserted into the tree

void TreeStringSet::insertRandom	(	Element *&	atElement,
		Element *&	newElement
	)

private

Helper for insert. Makes the random choice to insert at the root or child of a subtree.

Parameters

atElement	Reference to an Element pointer, the root of the subtree on which the random choice is being made
newElement	The element being inserted

void TreeStringSet::insertRoot	(	Element *&	atElement,
		Element *&	newElement
	)

private

Helper for insert. Inserts a new element as the root of a subtree.

Parameters

atElement	Reference to an Element pointer, the root of the subtree on which the random choice is being made
newElement	The element being inserted

std::ostream & TreeStringSet::print ( std::ostream & out )

Prints the tree.

Returns: A reference to an ostream

Parameters

out	Reference to an ostream which the tree will be printed to

void TreeStringSet::printHelper	(	Element *&	elem,
		string &	result
	)

private

Helper function for print. Recursively goes through the tree, adding each element to the print.

Parameters

elem	Reference to an Element of which the subtree will be printed
result	Reference to a string containing the printed tree

void TreeStringSet::rotateLeft ( Element *& top )

Helper function for Insert, rotates subtree left.

Parameters

top	Reference to a pointer to an Element that is the root of the subtree

void TreeStringSet::rotateRight ( Element *& top )

Helper function for Insert. Rotates a given subtree to the right.

Parameters

top	Reference to an Element pointer, that is the root of the subtree

void TreeStringSet::showStatistics ( std::ostream & out )

Prints statistics about the tree in the format height, size, size of a perfect tree of this height, percent full.

Parameters

out	Reference to an ostream to which the stats will be printed

size_t TreeStringSet::size ( ) const

Returns the size of the entire tree.

Returns: Unsigned int of the size of the tree

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

TreeStringSet.hpp
TreeStringSet.cpp

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation