Quick Links: |
#include <bslalg_rbtreenode.h>
Public Types | |
enum | Color { BSLALG_RED = 0, BSLALG_BLACK = 1 } |
Public Member Functions | |
RbTreeNode () | |
RbTreeNode (const RbTreeNode &original) | |
~RbTreeNode () | |
RbTreeNode & | operator= (const RbTreeNode &rhs) |
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 |
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 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 Component bslalg_rbtreenode
bslalg::RbTreeNode::RbTreeNode | ( | ) |
Create a RbTreeNode
object having uninitialized values.
bslalg::RbTreeNode::RbTreeNode | ( | const RbTreeNode & | original | ) |
Create a RbTreeNode
object having the same value as the specified original
object.
bslalg::RbTreeNode::~RbTreeNode | ( | ) |
Destroy this object.
RbTreeNode& bslalg::RbTreeNode::operator= | ( | const RbTreeNode & | rhs | ) |
Assign to this object the value of the specified rhs
object, and return a reference providing modifiable access to this object.
void bslalg::RbTreeNode::makeBlack | ( | ) |
Set the color of this node to black. Note that this operation is at least as fast as (and potentially faster than) setColor
.
void bslalg::RbTreeNode::makeRed | ( | ) |
Set the color of this node to red. Note that this operation is at least as fast as (and potentially faster than) setColor
.
void bslalg::RbTreeNode::setParent | ( | RbTreeNode * | address | ) |
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). The behavior is undefined unless address
is aligned to at least two bytes.
void bslalg::RbTreeNode::setLeftChild | ( | RbTreeNode * | address | ) |
Set the left child of this node to the specified address
. If address
is 0, then this node will not have a left child.
void bslalg::RbTreeNode::setRightChild | ( | RbTreeNode * | address | ) |
Set the right child of this node to the specified address
. If address
is 0, then this node will not have a right child.
void bslalg::RbTreeNode::setColor | ( | Color | value | ) |
Set the color of this node to the specified value
.
void bslalg::RbTreeNode::toggleColor | ( | ) |
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 that this operation is at least as fast as (and potentially faster than) setColor
.
void bslalg::RbTreeNode::reset | ( | RbTreeNode * | parent, | |
RbTreeNode * | leftChild, | |||
RbTreeNode * | rightChild, | |||
Color | color | |||
) |
Reset this object to have the specified parent
, leftChild
, rightChild
, and color
property values.
RbTreeNode* bslalg::RbTreeNode::parent | ( | ) |
Return the address of the (modifiable) parent of this node if one exists, and 0 otherwise.
RbTreeNode* bslalg::RbTreeNode::leftChild | ( | ) |
Return the address of the (modifiable) left child of this node if one exists, and 0 otherwise.
RbTreeNode* bslalg::RbTreeNode::rightChild | ( | ) |
Return the address of the (modifiable) right child of this node if one exists, and 0 otherwise.
const RbTreeNode* bslalg::RbTreeNode::parent | ( | ) | const |
Return the address of the parent of this node if one exists, and 0 otherwise.
bool bslalg::RbTreeNode::isBlack | ( | ) | const |
Return true
if this node is black.
bool bslalg::RbTreeNode::isRed | ( | ) | const |
Return true
if this node is red.
const RbTreeNode* bslalg::RbTreeNode::leftChild | ( | ) | const |
Return the address of the left child of this node if one exists, and 0 otherwise.
const RbTreeNode* bslalg::RbTreeNode::rightChild | ( | ) | const |
Return the address of the right child of this node if one exists, and 0 otherwise.
Color bslalg::RbTreeNode::color | ( | ) | const |
Return the color of this node.