utl::BinTreeNode Class Reference

Binary tree node. More...

#include <BinTreeNode.h>

Inheritance diagram for utl::BinTreeNode:

Public Member Functions
	BinTreeNode ()
	Constructor. More...
virtual	~BinTreeNode ()
	Destructor. More...
	BinTreeNode (const Object *object)
	Constructor. More...
Object *	get () const
	Get the contained object. More...
bool	isLeaf () const
	Determine whether self is a leaf node. More...
bool	isLeftChild () const
	Determine whether self is a left child. More...
bool	isRightChild () const
	Determine whether self is a right child. More...
bool	isRoot () const
	Determine whether self is the root node. More...
BinTreeNode *	left () const
	Return the left child. More...
const BinTreeNode *	leftMost () const
	Return the left-most child (smallest node reachable from self). More...
BinTreeNode *	leftMost ()
	Return the left-most child (smallest node reachable from self). More...
BinTreeNode *	next () const
	Return the in-order successor. More...
BinTreeNode *	parent () const
	Return the parent node (nullptr if root). More...
BinTreeNode *	prev () const
	Return the in-order predecessor. More...
void	remove (BinTreeNode *&x, BinTreeNode *&y)
	Remove the node from the tree. More...
BinTreeNode *	right () const
	Return the right child. More...
const BinTreeNode *	rightMost () const
	Return the right-most child (largest node reachable from self). More...
BinTreeNode *	rightMost ()
	Return the right-most child (largest node reachable from self). More...
virtual void	addFixup ()=0
	Perform necessary re-balancing following the addition of a node. More...
virtual void	removeFixup (const BinTreeNode *removedNode)=0
	Perform re-balancing following the removal of a node. More...
virtual void	swapWith (BinTreeNode *rhs)
	Trade places with the given node. More...
void	rotateLeft ()
	Perform a left rotation around self. More...
void	rotateRight ()
	Perform a right rotation around self. More...
void	set (const Object *object)
	Set the contained object. More...
void	setLeft (BinTreeNode *node)
	Set the left child. More...
void	setRight (BinTreeNode *node)
	Set the right child. More...
BinTreeNode *	sibling () const
	Return the sibling node (nullptr if self is parent). More...

Detailed Description

Binary tree node.

You shouldn't need to use this class directly.

Attributes

• parent : Parent Node (= nullptr if self is root node).
• left : Left child.
• right : Right Child.
• object : Contained object.

Author

Adam McKee

Definition at line 31 of file BinTreeNode.h.

Constructor & Destructor Documentation

BinTreeNode() [1/2]

utl::BinTreeNode::BinTreeNode ( )

inline

Constructor.

Definition at line 35 of file BinTreeNode.h.

References utl::init().

~BinTreeNode()

virtual utl::BinTreeNode::~BinTreeNode ( )

inlinevirtual

Destructor.

Definition at line 41 of file BinTreeNode.h.

BinTreeNode() [2/2]

utl::BinTreeNode::BinTreeNode ( const Object *  object )

inline

Constructor.

Parameters

object

contained object

Definition at line 49 of file BinTreeNode.h.

References utl::dump(), and utl::init().

Member Function Documentation

get()

Object* utl::BinTreeNode::get ( ) const

inline

Get the contained object.

Definition at line 58 of file BinTreeNode.h.

Referenced by utl::SpanAllocator< T, D >::alloc().

isLeaf()

bool utl::BinTreeNode::isLeaf ( ) const

inline

Determine whether self is a leaf node.

Definition at line 65 of file BinTreeNode.h.

Referenced by utl::SpanAllocator< T, D >::alloc().

isLeftChild()

bool utl::BinTreeNode::isLeftChild ( ) const

inline

Determine whether self is a left child.

Definition at line 72 of file BinTreeNode.h.

isRightChild()

bool utl::BinTreeNode::isRightChild ( ) const

inline

Determine whether self is a right child.

Definition at line 79 of file BinTreeNode.h.

isRoot()

bool utl::BinTreeNode::isRoot ( ) const

inline

Determine whether self is the root node.

Definition at line 86 of file BinTreeNode.h.

left()

BinTreeNode* utl::BinTreeNode::left ( ) const

inline

Return the left child.

Definition at line 93 of file BinTreeNode.h.

Referenced by utl::SpanAllocator< T, D >::alloc().

leftMost() [1/2]

const BinTreeNode* utl::BinTreeNode::leftMost ( ) const

inline

Return the left-most child (smallest node reachable from self).

Definition at line 100 of file BinTreeNode.h.

References const_cast_this.

leftMost() [2/2]

BinTreeNode* utl::BinTreeNode::leftMost

(

)

Return the left-most child (smallest node reachable from self).

next()

BinTreeNode* utl::BinTreeNode::next

(

)

const

Return the in-order successor.

parent()

BinTreeNode* utl::BinTreeNode::parent ( ) const

inline

Return the parent node (nullptr if root).

Definition at line 113 of file BinTreeNode.h.

prev()

BinTreeNode* utl::BinTreeNode::prev

(

)

const

Return the in-order predecessor.

remove()

void utl::BinTreeNode::remove	(	BinTreeNode *&	x,
		BinTreeNode *&	y
	)

Remove the node from the tree.

Parameters

x	y's only child
y	node that should be removed

right()

BinTreeNode* utl::BinTreeNode::right ( ) const

inline

Return the right child.

Definition at line 130 of file BinTreeNode.h.

Referenced by utl::SpanAllocator< T, D >::alloc().

rightMost() [1/2]

const BinTreeNode* utl::BinTreeNode::rightMost ( ) const

inline

Return the right-most child (largest node reachable from self).

Definition at line 137 of file BinTreeNode.h.

References const_cast_this.

rightMost() [2/2]

BinTreeNode* utl::BinTreeNode::rightMost

(

)

Return the right-most child (largest node reachable from self).

addFixup()

virtual void utl::BinTreeNode::addFixup ( )

pure virtual

Perform necessary re-balancing following the addition of a node.

Implemented in utl::RBtreeNode.

removeFixup()

virtual void utl::BinTreeNode::removeFixup ( const BinTreeNode *  removedNode )

pure virtual

Perform re-balancing following the removal of a node.

Implemented in utl::RBtreeNode.

swapWith()

virtual void utl::BinTreeNode::swapWith ( BinTreeNode *  rhs )

virtual

Trade places with the given node.

Reimplemented in utl::RBtreeNode.

rotateLeft()

void utl::BinTreeNode::rotateLeft

(

)

Perform a left rotation around self.

rotateRight()

void utl::BinTreeNode::rotateRight

(

)

Perform a right rotation around self.

set()

void utl::BinTreeNode::set ( const Object *  object )

inline

Set the contained object.

Definition at line 162 of file BinTreeNode.h.

setLeft()

void utl::BinTreeNode::setLeft ( BinTreeNode *  node )

inline

Set the left child.

Definition at line 169 of file BinTreeNode.h.

setRight()

void utl::BinTreeNode::setRight ( BinTreeNode *  node )

inline

Set the right child.

Definition at line 177 of file BinTreeNode.h.

References utl::deInit(), and utl::init().

sibling()

BinTreeNode* utl::BinTreeNode::sibling

(

)

const

Return the sibling node (nullptr if self is parent).

---

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

• BinTreeNode.h