RBTree Class Reference

Header file for the RBTree class and RbtNode class. More...

#include <redblack_tree.hpp>

Collaboration diagram for RBTree:

Public Member Functions
	RBTree ()
	Constructs a new RBTree object.
int	ColorFlipCount ()
	Returns the number of color flips performed during tree operations.
rbtnode *	begin ()
	Returns a pointer to the first node in the red-black tree.
rbtnode *	end ()
	Returns a pointer to the end of the red-black tree.
void	add (book book_info)
	Adds a new book to the red-black tree.
void	remove (int key)
	Removes a book from the red-black tree based on the given key.
rbtnode *	find (int key) const
	Finds a book in the red-black tree based on the given key.
std::vector< int >	findclosest (int targetId) const
	Finds the closest book IDs to the given target ID in the red-black tree.
rbtnode *	operator[] (int key) const
	Overloads the subscript operator to find a book in the red-black tree based on the given key.
bool	empty () const
	Checks if the red-black tree is empty.

Private Member Functions
void	rotate_left (rbtnode *&, rbtnode *&)
void	rotate_right (rbtnode *&, rbtnode *&)
void	fix_colorviolation (rbtnode *&, rbtnode *&)
rbtnode *	insert_node (rbtnode *root_node, rbtnode *node)
void	remove (rbtnode *node)
rbtnode *	BSTreplace (rbtnode *x)
rbtnode *	successor (rbtnode *x)
void	fix_double_black (rbtnode *node)

Private Attributes
rbtnode *	root
int	color_flip_count

Detailed Description

Header file for the RBTree class and RbtNode class.

Represents a red-black tree data structure.

This file defines the RBTree class and RbtNode class, which implement a red-black tree data structure. The RBTree class provides methods for adding, removing, and finding nodes in the red-black tree. The RbtNode class represents a node in the red-black tree and stores a key-value pair.

The RBTree class represents a red-black tree data structure. It provides methods for adding, removing, and finding nodes in the red-black tree.

Constructor & Destructor Documentation

RBTree()

RBTree::RBTree

(

)

Constructs a new RBTree object.

Member Function Documentation

add()

void RBTree::add

(

book

book_info

)

Adds a new book to the red-black tree.

Parameters

book_info

The book to add.

Here is the call graph for this function:

begin()

rbtnode * RBTree::begin

(

)

Returns a pointer to the first node in the red-black tree.

Returns

Pointer to the first node.

BSTreplace()

rbtnode * RBTree::BSTreplace ( rbtnode *  x )

private

Finds the node that can replace the given node in the red-black tree.

Here is the call graph for this function:

Here is the caller graph for this function:

ColorFlipCount()

int RBTree::ColorFlipCount

(

)

Returns the number of color flips performed during tree operations.

Returns

The number of color flips.

empty()

bool RBTree::empty

(

)

const

Checks if the red-black tree is empty.

Returns

True if the tree is empty, false otherwise.

end()

rbtnode * RBTree::end

(

)

Returns a pointer to the end of the red-black tree.

Returns

Pointer to the end.

find()

rbtnode * RBTree::find

(

int

key

)

const

Finds a book in the red-black tree based on the given key.

Parameters

key	The key of the book to find.

Returns

Pointer to the node containing the book, or nullptr if not found.

Here is the caller graph for this function:

findclosest()

std::vector< int > RBTree::findclosest

(

int

targetId

)

const

Finds the closest book IDs to the given target ID in the red-black tree.

Parameters

targetId

The target book ID.

Returns

A vector of closest book IDs.

fix_colorviolation()

void RBTree::fix_colorviolation ( rbtnode *&  rootnode, rbtnode *&  node  )

private

Fixes the color violation after inserting a node.

Here is the call graph for this function:

Here is the caller graph for this function:

fix_double_black()

void RBTree::fix_double_black ( rbtnode *  node )

private

Fixes the double black violation after removing a node.

Here is the call graph for this function:

Here is the caller graph for this function:

insert_node()

rbtnode * RBTree::insert_node ( rbtnode *  root_node, rbtnode *  node  )

private

Inserts a node into the red-black tree.

Here is the call graph for this function:

Here is the caller graph for this function:

operator[]()

rbtnode * RBTree::operator[]

(

int

key

)

const

Overloads the subscript operator to find a book in the red-black tree based on the given key.

Parameters

key	The key of the book to find.

Returns

Pointer to the node containing the book, or nullptr if not found.

Here is the call graph for this function:

remove() [1/2]

void RBTree::remove

(

int

key

)

Removes a book from the red-black tree based on the given key.

Parameters

key	The key of the book to remove.

Here is the call graph for this function:

remove() [2/2]

void RBTree::remove ( rbtnode *  node )

private

Removes a node from the red-black tree.

Here is the call graph for this function:

Here is the caller graph for this function:

rotate_left()

void RBTree::rotate_left ( rbtnode *&  root, rbtnode *&  pt  )

private

Performs a left rotation on the given nodes.

Here is the caller graph for this function:

rotate_right()

void RBTree::rotate_right ( rbtnode *&  root, rbtnode *&  pt  )

private

Performs a right rotation on the given nodes.

Here is the caller graph for this function:

successor()

rbtnode * RBTree::successor ( rbtnode *  x )

private

Finds the successor of the given node in the red-black tree.

Here is the caller graph for this function:

Member Data Documentation

color_flip_count

int RBTree::color_flip_count

private

The number of color flips performed during tree operations.

root

rbtnode* RBTree::root

private

Pointer to the root node of the red-black tree.

---

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

• redblack_tree.hpp
• redblack_tree.cpp