RBTree< T > Class Template Reference

A red-black tree implementation. More...

#include <rbtree.hpp>

Public Member Functions
	RBTree (int(*comparator)(const T &a, const T &b))
	Construct a new RBTree object.
	~RBTree ()
	Destroy the RBTree object.
void	insert (T data)
	Insert an element into the tree.
void	remove (std::shared_ptr< Node > node)
	Remove an element from the tree.
size_t	size ()
	Check if the tree contains an element.
T	extractMin ()
	Extract the minimum element from the tree.
void	printPreorder () const
	Print preorder traversal of the tree.
void	printInorder () const
	Print inorder traversal of the tree.
void	printPostorder () const
	Print postorder traversal of the tree.

Detailed Description

template<typename T>
class RBTree< T >

A red-black tree implementation.

References:

1. https://www.programiz.com/dsa/red-black-tree
2. Cormen, Leiserson, Rivest, and Stein; Introduction to Algorithms (MIT Press, 2009)
3. https://www.boost.org/doc/libs/1_81_0/doc/html/intrusive/reference.html#header.boost.intrusive.rbtree_hpp

Template Parameters

T	The type of the elements in the tree

Constructor & Destructor Documentation

RBTree()

template<typename T >

RBTree< T >::RBTree

(

int(*)(const T &a, const T &b)

comparator

)

Construct a new RBTree object.

Parameters

comparator

A function pointer to a function that compares two elements

~RBTree()

template<typename T >

RBTree< T >::~RBTree

(

)

Destroy the RBTree object.

Member Function Documentation

extractMin()

template<typename T >

T RBTree< T >::extractMin

(

)

Extract the minimum element from the tree.

Returns

T The minimum element

insert()

template<typename T >

void RBTree< T >::insert

(

T

data

)

Insert an element into the tree.

Insert a new node into the tree.

Parameters

data	The element to insert

Template Parameters

T

Parameters

data

printInorder()

template<typename T >

void RBTree< T >::printInorder

(

)

const

Print inorder traversal of the tree.

printPostorder()

template<typename T >

void RBTree< T >::printPostorder

(

)

const

Print postorder traversal of the tree.

printPreorder()

template<typename T >

void RBTree< T >::printPreorder

(

)

const

Print preorder traversal of the tree.

remove()

template<typename T >

void RBTree< T >::remove

(

std::shared_ptr< Node >

node

)

Remove an element from the tree.

Remove a node from the tree.

Parameters

node	The element to remove

Template Parameters

T

Parameters

node

size()

template<typename T >

size_t RBTree< T >::size ( )

inline

Check if the tree contains an element.

Parameters

data	The element to check for

Returns

true If the tree contains the element

false If the tree does not contain the element

Get the number of elements in the tree

Returns

size_t The number of elements in the tree

---

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

• src/rbtree.hpp
• src/rbtree.cpp