BF::RBTree< T, S > Class Template Reference

#include <rbtree.hpp>

Inheritance diagram for BF::RBTree< T, S >:

Collaboration diagram for BF::RBTree< T, S >:

Classes
class	Iterator
class	RBNode
class	RBNodeNonnull
class	RBNodeNull

Public Member Functions
	RBTree ()
virtual	~RBTree ()
virtual const RBNode *	root () const
virtual const RBNode *	getNodeForObject (T obj)
virtual int	insert (T obj)
virtual int	remove (T obj)
virtual void	print ()
virtual void	print (bool printNullNodes)
int	deleteNode (const RBNode *node)
virtual const RBNode *	minNode () const
virtual const RBNode *	maxNode () const
virtual int	createIterator (Iterator **itr)
Public Member Functions inherited from BF::BinTree< T, int >
	BinTree ()
virtual	~BinTree ()
void	setCompareCallback (int(*cb)(T a, T b))
int	insert (T obj)
int	count () const
bool	contains (T obj)
T	max () const
T	min () const
virtual int	deleteNode (BinNode *node)
int	removeAll ()
int	leafValues (List< T > *list)
virtual int	createIterator (Iterator **itr)
int	runCompare (T a, T b) const
Public Member Functions inherited from BF::Object
	Object ()
	Object (Object &obj)
virtual	~Object ()

Additional Inherited Members
Static Public Member Functions inherited from BF::Object
static void	retain (Object *obj)
static void	release (Object *obj)
static int	retainCount (Object *obj)
static int	retainCount (Object &obj)
Protected Member Functions inherited from BF::BinTree< T, int >
virtual int	insert (BinNode *newNode, BinNode *parent)
virtual void	print (BinNode *node)
virtual const BinNode *	minNode (const BinNode *node) const
	Returns the leaf node
virtual const BinNode *	maxNode (const BinNode *node) const
	Returns the leaf node
BinNode *	getNodeForObject (T obj, BinNode *node)
BinNode **	rootAddr ()
	Root accessors.
void	setRoot (BinNode *node)
BinNode **	getNodeLocation (const BinNode *node)
void	setNodeLocation (BinNode *node, BinNode **location)
BinNode *	getNodeParent (const BinNode *node)
void	setNodeParent (BinNode *node, BinNode *parent)
virtual bool	canNewNodeTakeNewLocation (BinNode **newLocation)
virtual int	replaceNodeWithTheOnlyChild (BinNode *node)
virtual int	replaceNodeWithNode (BinNode *node, BinNode *replacement)
int	removeNode (BinNode *node)
Protected Attributes inherited from BF::BinTree< T, int >
int	_count

Detailed Description

template<typename T, typename S = int>
class BF::RBTree< T, S >

Red Black Binary Tree

Left most node is the least value comparison

Constructor & Destructor Documentation

RBTree()

template<typename T , typename S = int>

BF::RBTree< T, S >::RBTree ( )

inline

~RBTree()

template<typename T , typename S = int>

virtual BF::RBTree< T, S >::~RBTree ( )

inlinevirtual

Member Function Documentation

createIterator()

template<typename T , typename S = int>

virtual int BF::RBTree< T, S >::createIterator ( Iterator ** itr )

inlinevirtual

Here is the call graph for this function:

deleteNode()

template<typename T , typename S = int>

int BF::RBTree< T, S >::deleteNode ( const RBNode * node )

inline

Removes node from tree and deletes the memory

This is was made so that caller does not have to cast RBNode to BinNode

Here is the call graph for this function:

getNodeForObject()

template<typename T , typename S = int>

virtual const RBNode * BF::RBTree< T, S >::getNodeForObject ( T obj )

inlinevirtual

Returns nonnull pointer to BinNode

Returns NULL if node with obj could not be found

Caller does not own node

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

insert()

template<typename T , typename S = int>

virtual int BF::RBTree< T, S >::insert ( T obj )

inlinevirtual

inserts object into tree

Here is the call graph for this function:

maxNode()

template<typename T , typename S = int>

virtual const RBNode * BF::RBTree< T, S >::maxNode ( ) const

inlinevirtual

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

minNode()

template<typename T , typename S = int>

virtual const RBNode * BF::RBTree< T, S >::minNode ( ) const

inlinevirtual

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

print() [1/2]

template<typename T , typename S = int>

virtual void BF::RBTree< T, S >::print ( )

inlinevirtual

Prints tree with root at the left most positions and the leafs at the right most, start from the top the right leaves

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

print() [2/2]

template<typename T , typename S = int>

virtual void BF::RBTree< T, S >::print ( bool printNullNodes )

inlinevirtual

param printNullNodes: If true, then null nodes will be shown

Here is the call graph for this function:

remove()

template<typename T , typename S = int>

virtual int BF::RBTree< T, S >::remove ( T obj )

inlinevirtual

Removes object from tree

refs: https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/

notes: When a black node is deleted and replaced by a black child, the child is marked as double black

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

root()

template<typename T , typename S = int>

virtual const RBNode * BF::RBTree< T, S >::root ( ) const

inlinevirtual

Reimplemented from BF::BinTree< T, int >.

Here is the call graph for this function:

---

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

• rbtree.hpp