bslalg::RbTreeNode Class Reference

#include <bslalg_rbtreenode.h>

Inheritance diagram for bslalg::RbTreeNode:

Detailed Description

This POD-like class describes a node suitable for use in a red-black binary search tree, holding the addresses of the parent, left-child, and right-child nodes (any of which may be 0), as well as a "color" (red or black). This class is a "POD-like" to facilitate efficient allocation and use in the context of a container implementation. In order to meet the essential requirements of a POD type, this class does not define a constructor or destructor. However its data members are private. Since this class will be aligned to a word boundary, a pointer type will be a multiple of 4. This class use this property to reduce its size by storing the color information in the least significant bit of the parent pointer.

Note

Note that this type does not contain any "payload" member data: Clients creating a red-black binary search tree must define an appropriate node type that incorporates RbTreeNode (generally via inheritance), and that holds the "key" value and any associated data.

See bslalg_rbtreenode

Public Types
enum	Color { BSLALG_RED = 0 , BSLALG_BLACK = 1 }

Public Member Functions
	RbTreeNode ()=default
	RbTreeNode (const RbTreeNode &original)=default
	~RbTreeNode ()=default
RbTreeNode &	operator= (const RbTreeNode &rhs)=default
void	makeBlack ()
void	makeRed ()
void	setParent (RbTreeNode *address)
void	setLeftChild (RbTreeNode *address)
void	setRightChild (RbTreeNode *address)
void	setColor (Color value)
void	toggleColor ()
void	reset (RbTreeNode *parent, RbTreeNode *leftChild, RbTreeNode *rightChild, Color color)
RbTreeNode *	parent ()
RbTreeNode *	leftChild ()
RbTreeNode *	rightChild ()
const RbTreeNode *	parent () const
bool	isBlack () const
bool	isRed () const
const RbTreeNode *	leftChild () const
const RbTreeNode *	rightChild () const
Color	color () const

Member Enumeration Documentation

Color

enum bslalg::RbTreeNode::Color

Enumerator
BSLALG_RED
BSLALG_BLACK

Constructor & Destructor Documentation

RbTreeNode() [1/2]

bslalg::RbTreeNode::RbTreeNode ( )

default

RbTreeNode() [2/2]

bslalg::RbTreeNode::RbTreeNode ( const RbTreeNode &  original )

default

~RbTreeNode()

bslalg::RbTreeNode::~RbTreeNode ( )

default

Member Function Documentation

color()

RbTreeNode::Color bslalg::RbTreeNode::color ( ) const

inline

Return the color of this node.

isBlack()

bool bslalg::RbTreeNode::isBlack ( ) const

inline

Return true if this node is black.

isRed()

bool bslalg::RbTreeNode::isRed ( ) const

inline

Return true if this node is red.

leftChild() [1/2]

RbTreeNode * bslalg::RbTreeNode::leftChild ( )

inline

Return the address of the (modifiable) left child of this node if one exists, and 0 otherwise.

leftChild() [2/2]

const RbTreeNode * bslalg::RbTreeNode::leftChild ( ) const

inline

Return the address of the left child of this node if one exists, and 0 otherwise.

makeBlack()

void bslalg::RbTreeNode::makeBlack ( )

inline

Set the color of this node to black.

Note

Note that this operation is at least as fast as (and potentially faster than) setColor.

makeRed()

void bslalg::RbTreeNode::makeRed ( )

inline

Set the color of this node to red.

Note

Note that this operation is at least as fast as (and potentially faster than) setColor.

operator=()

RbTreeNode & bslalg::RbTreeNode::operator= ( const RbTreeNode &  rhs )

default

parent() [1/2]

RbTreeNode * bslalg::RbTreeNode::parent ( )

inline

Return the address of the (modifiable) parent of this node if one exists, and 0 otherwise.

parent() [2/2]

const RbTreeNode * bslalg::RbTreeNode::parent ( ) const

inline

Return the address of the parent of this node if one exists, and 0 otherwise.

reset()

void bslalg::RbTreeNode::reset ( RbTreeNode *  parent, RbTreeNode *  leftChild, RbTreeNode *  rightChild, Color  color  )

inline

Reset this object to have the specified parent, leftChild, rightChild, and color property values.

rightChild() [1/2]

RbTreeNode * bslalg::RbTreeNode::rightChild ( )

inline

Return the address of the (modifiable) right child of this node if one exists, and 0 otherwise.

rightChild() [2/2]

const RbTreeNode * bslalg::RbTreeNode::rightChild ( ) const

inline

Return the address of the right child of this node if one exists, and 0 otherwise.

setColor()

void bslalg::RbTreeNode::setColor ( Color  value )

inline

Set the color of this node to the specified value.

setLeftChild()

void bslalg::RbTreeNode::setLeftChild ( RbTreeNode *  address )

inline

Set the left child of this node to the specified address. If address is 0, then this node will not have a left child.

setParent()

void bslalg::RbTreeNode::setParent ( RbTreeNode *  address )

inline

Set the parent of this node to the specified address. If address is 0, then this node will have not have a parent node (i.e., it will be the root node).

Precondition

The behavior is undefined unless address is aligned to at least two bytes.

setRightChild()

void bslalg::RbTreeNode::setRightChild ( RbTreeNode *  address )

inline

Set the right child of this node to the specified address. If address is 0, then this node will not have a right child.

toggleColor()

void bslalg::RbTreeNode::toggleColor ( )

inline

Set the color of this node to the alternative color. If this node's color is red, set it to black, and set it to red otherwise.

Note

Note that this operation is at least as fast as (and potentially faster than) setColor.

---

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

• bslalg_rbtreenode.h