Main Page Modules Class Hierarchy Alphabetical List Compound List File List Compound Members File Members Related Pages Examples

CTBbtreeNode Class Reference

Base class for the implementation of binary tree nodes. More...

#include "CTBbtree.hxx"

Inheritance diagram for CTBbtreeNode:

[legend]Collaboration diagram for CTBbtreeNode:

[legend]List of all members.

Public Methods
	CTBbtreeNode ()
virtual	~CTBbtreeNode ()
virtual CTBbtreeNode *	Clone () const
CTBbtree *	Head () const
CTBbtreeNode *	Left () const
CTBbtreeNode *	Right () const
CTBbtreeNode *	Up () const
CTBbtreeNode *	Next () const
CTBbtreeNode *	Prev () const
CTBbtreeNode *	Skip (CTBint i_offset) const
CTBint	Rank () const
CTBint	LWeight () const
bool	IsRNode () const
bool	IsLeftChild () const
bool	IsRightChild () const
bool	IsBalanced () const
bool	IsLeftHeavy () const
bool	IsRightHeavy () const
void	Insert (CTBbtree &head, CTBbtreeNode *p_parent, int i_ctype)
void	Remove ()
Private Methods
void	LWeight (CTBint i_weight)
void	IncLWeight ()
void	DecLWeight ()
void	SetRNode ()
void	SetLeftChild ()
void	SetRightChild ()
void	SetBalanced ()
void	SetLeftHeavy ()
void	SetRightHeavy ()
void	RotateLeft ()
void	RotateRight ()
void	RotateLeftRight ()
void	RotateRightLeft ()
void	InsertFixup ()
void	RemoveFixup ()
void	SubTreeHeight (int &i_minh, int &i_maxh, double &d_nnode, double &d_ncomp) const
bool	SubTreeCheck (ostream *p_os, int &i_maxh) const
	CTBbtreeNode (const CTBbtreeNode &rhs)
CTBbtreeNode &	operator= (const CTBbtreeNode &rhs)
Private Attributes
CTBbtree *	mp_head
CTBbtreeNode *	mp_up
CTBbtreeNode *	mp_left
CTBbtreeNode *	mp_right
CTBuint32	mi_status
Static Private Attributes
const CTBuint32	status_lchild = 0x2
const CTBuint32	status_rchild = 0x1
const CTBuint32	status_childmask = status_lchild \| status_rchild
const CTBuint32	status_lheavy = 0x8
const CTBuint32	status_rheavy = 0x4
const CTBuint32	status_heavymask = status_lheavy \| status_rheavy
const CTBuint32	status_bitmask = status_childmask\|status_heavymask
const CTBuint32	status_deltaw = 16
Friends
class	CTBbtree

Detailed Description

Base class for the implementation of binary tree nodes.

Definition at line 56 of file CTBbtree.hxx.

Constructor & Destructor Documentation

CTBbtreeNode::CTBbtreeNode ( ) [inline]

Default constructor.

Definition at line 71 of file CTBbtree.icc.
Referenced by Clone().

CTBbtreeNode::~CTBbtreeNode ( ) [virtual]

Virtual destructor.

Definition at line 399 of file CTBbtree.cxx.

CTBbtreeNode::CTBbtreeNode ( const CTBbtreeNode & rhs ) [private]

Member Function Documentation

CTBbtreeNode * CTBbtreeNode::Clone ( ) const [virtual]

Virtual constructor.
Returns the pointer to a new instantiation of CTBbtreeNode. This function must be reimplemented for each derived class and return a pointer to a new instantiation of the derived class initialized as a copy of the current one. By and large this can be achived with a code similar to:
return new T(*this);

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 418 of file CTBbtree.cxx.
Referenced by CTBbtree::operator=().

CTBbtree * CTBbtreeNode::Head ( ) const [inline]

Returns tree header or null of node is unconnected.

Definition at line 82 of file CTBbtree.icc.

CTBbtreeNode * CTBbtreeNode::Left ( ) const [inline]

Returns left child of node (or null if none).

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 90 of file CTBbtree.icc.
Referenced by CTBmapNode::Left(), and CTBgsetNode::Left().

CTBbtreeNode * CTBbtreeNode::Right ( ) const [inline]

Returns right child of node (or null if none).

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 98 of file CTBbtree.icc.
Referenced by CTBmapNode::Right(), and CTBgsetNode::Right().

CTBbtreeNode * CTBbtreeNode::Up ( ) const [inline]

Returns parent node or null if in root node.

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 106 of file CTBbtree.icc.
Referenced by CTBmapNode::Up(), and CTBgsetNode::Up().

CTBbtreeNode * CTBbtreeNode::Next ( ) const

Returns pointer to next node (or null if in last).

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 428 of file CTBbtree.cxx.
Referenced by CTBbtree::Dump(), CTBmapNode::Next(), CTBgsetNode::Next(), Remove(), and Skip().

CTBbtreeNode * CTBbtreeNode::Prev ( ) const

Returns pointer to previous node (or null if in last).

Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 461 of file CTBbtree.cxx.
Referenced by CTBmapNode::Prev(), CTBgsetNode::Prev(), Remove(), and Skip().

CTBbtreeNode * CTBbtreeNode::Skip ( CTBint i_offset ) const

Skip i_offset nodes.
Returns the pointer to the node i_offset steps away from the current one. The function moves to the left (previous) if i_offset is < 0 and to the right is i_offset is > 0. A null is returned when the offset is too large.
This functions is substantially more efficient than a simple iteration of Next() or Prev() and completes always on O(lg(N)) time.
Reimplemented in CTBgsetNode, and CTBmapNode.
Definition at line 499 of file CTBbtree.cxx.
Referenced by CTBmapNode::Skip(), and CTBgsetNode::Skip().

CTBint CTBbtreeNode::Rank ( ) const

Returns rank of node.

Definition at line 552 of file CTBbtree.cxx.
Referenced by CTBmapBrowser::Rank(), and CTBgsetBrowser::Rank().

CTBint CTBbtreeNode::LWeight ( ) const [inline]

Returns weight of left subtree.
LWeight() returns the number of nodes in the left subtree including itself. Therefore, it returns 1 in case there are no left childs !
Definition at line 117 of file CTBbtree.icc.
Referenced by CTBbtree::Dump(), Rank(), RotateLeft(), RotateRight(), Skip(), and CTBbtree::operator[]().

bool CTBbtreeNode::IsRNode ( ) const [inline]

Returns true if node is root node.

Definition at line 125 of file CTBbtree.icc.
Referenced by Remove(), RotateLeft(), RotateRight(), Skip(), and CTBbtree::operator=().

bool CTBbtreeNode::IsLeftChild ( ) const [inline]

Returns true if node is a left child.

Definition at line 133 of file CTBbtree.icc.
Referenced by CTBbtree::Clear(), CTBbtree::Dump(), InsertFixup(), Prev(), Remove(), RemoveFixup(), RotateLeft(), RotateRight(), Skip(), and CTBbtree::operator=().

bool CTBbtreeNode::IsRightChild ( ) const [inline]

Returns true if node is a right child.

Definition at line 141 of file CTBbtree.icc.
Referenced by CTBbtree::Clear(), CTBbtree::Dump(), InsertFixup(), Next(), Rank(), Remove(), and Skip().

bool CTBbtreeNode::IsBalanced ( ) const [inline]

Returns true if left and right subtrees are balanced.

Definition at line 149 of file CTBbtree.icc.
Referenced by InsertFixup(), RemoveFixup(), and SubTreeCheck().

bool CTBbtreeNode::IsLeftHeavy ( ) const [inline]

Returns true if left subtree is one level higher than right subtree.

Definition at line 157 of file CTBbtree.icc.
Referenced by CTBbtree::Dump(), InsertFixup(), RemoveFixup(), and SubTreeCheck().

bool CTBbtreeNode::IsRightHeavy ( ) const [inline]

Returns true if right subtree is one level higher than left subtree.

Definition at line 165 of file CTBbtree.icc.
Referenced by CTBbtree::Dump(), InsertFixup(), RemoveFixup(), and SubTreeCheck().

void CTBbtreeNode::Insert ( CTBbtree & head,

CTBbtreeNode * p_parent,

int i_ctype

)

Insert node into tree.
The node is inserted in the tree given by header head as a child of the node p_parent. If i_ctype<0 the node will be inserted as left child, if i_ctype>0 as right child. If i_ctype==0 and p_parent==0 the node is inserted as root node.
Definition at line 573 of file CTBbtree.cxx.
Referenced by CTBmap::InsertNode(), and CTBgset::InsertNode().

void CTBbtreeNode::Remove ( )

Remove node from tree.

Implementation Notes:

For deletion of a node use Algorithm 6.2.3D from Knuth Vol. III:

if leave has only one child, just unlink
in case of inner node (with two childs), unlink Next() node (which always has no left child) and insert the next node in the place of this.

Definition at line 634 of file CTBbtree.cxx.
Referenced by CTBmap::RemoveNode(), CTBgset::RemoveNode(), and ~CTBbtreeNode().

void CTBbtreeNode::LWeight ( CTBint i_weight ) [inline, private]

Definition at line 171 of file CTBbtree.icc.

void CTBbtreeNode::IncLWeight ( ) [inline, private]

Definition at line 179 of file CTBbtree.icc.
Referenced by InsertFixup().

void CTBbtreeNode::DecLWeight ( ) [inline, private]

Definition at line 186 of file CTBbtree.icc.
Referenced by RemoveFixup().

void CTBbtreeNode::SetRNode ( ) [inline, private]

Definition at line 193 of file CTBbtree.icc.

void CTBbtreeNode::SetLeftChild ( ) [inline, private]

Definition at line 200 of file CTBbtree.icc.
Referenced by RotateLeft(), and RotateRight().

void CTBbtreeNode::SetRightChild ( ) [inline, private]

Definition at line 208 of file CTBbtree.icc.
Referenced by RotateLeft(), and RotateRight().

void CTBbtreeNode::SetBalanced ( ) [inline, private]

Definition at line 216 of file CTBbtree.icc.
Referenced by InsertFixup(), and RemoveFixup().

void CTBbtreeNode::SetLeftHeavy ( ) [inline, private]

Definition at line 223 of file CTBbtree.icc.
Referenced by InsertFixup(), and RemoveFixup().

void CTBbtreeNode::SetRightHeavy ( ) [inline, private]

Definition at line 230 of file CTBbtree.icc.
Referenced by InsertFixup(), and RemoveFixup().

void CTBbtreeNode::RotateLeft ( ) [private]

Single rotation, left.
The subtree below this node is rotated left:
| | New weights: this-> B C / \ ==> / \ A' = A / \ B de B' = B A C / \ C' = C + B / \ / \ A ga al be ga de / \ al be

Definition at line 719 of file CTBbtree.cxx.
Referenced by InsertFixup(), RemoveFixup(), RotateLeftRight(), and RotateRightLeft().

void CTBbtreeNode::RotateRight ( ) [private]

Single rotation, right.
The subtree below this node is rotated right:
| | New weights: this-> B A / \ ==> / \ A' = A / \ al B B' = B - A A C / \ C' = C / \ / \ be C al be ga de / \ ga de

Definition at line 778 of file CTBbtree.cxx.
Referenced by InsertFixup(), RemoveFixup(), RotateLeftRight(), and RotateRightLeft().

void CTBbtreeNode::RotateLeftRight ( ) [private]

Double rotation, left-right.
Two rotations are performed on the subtree below this node:

left subtree is rotated left around A
the subtree is rotated right around B
| | New weights: this-> B X / \ ==> / \ A' = A / \ / \ B' = B - A - X A C A B C' = C / \ / \ / \ / \ X' = X + A al X de ep al be ga C / \ / \ be ga de ep

Definition at line 834 of file CTBbtree.cxx.
Referenced by InsertFixup(), and RemoveFixup().

void CTBbtreeNode::RotateRightLeft ( ) [private]

Double rotation, right-left.
Two rotations are performed on the subtree below this node:

right subtree is rotated right around C
the subtree is rotated left around B
| | New weights: this-> B X / \ ==> / \ A' = A / \ / \ B' = B A C B C C' = C - X / \ / \ / \ / \ X' = X + B al be X ep A ga de ep / \ / \ ga de al be

Definition at line 866 of file CTBbtree.cxx.
Referenced by InsertFixup(), and RemoveFixup().

void CTBbtreeNode::InsertFixup ( ) [private]

All fixup's after insertion.

Definition at line 882 of file CTBbtree.cxx.
Referenced by Insert().

void CTBbtreeNode::RemoveFixup ( ) [private]

All fixup's after removal.

Definition at line 978 of file CTBbtree.cxx.
Referenced by Remove().

void CTBbtreeNode::SubTreeHeight ( int & i_minh,

int & i_maxh,

double & d_nnode,

double & d_ncomp

) const [private]

Determine subtree properties.
Scans the sub-tree and returns
Parameters:

i_minh minimal height to leave node

i_maxh maximal height to leave node

d_nnode number of nodes

d_ncomp number of compares

Definition at line 1094 of file CTBbtree.cxx.
Referenced by CTBbtree::TreeHeight().

bool CTBbtreeNode::SubTreeCheck ( ostream * p_os,

int & i_maxh

) const [private]

Check whether subtree is balanced.

Definition at line 1140 of file CTBbtree.cxx.
Referenced by CTBbtree::TreeCheck().

CTBbtreeNode& CTBbtreeNode::operator= ( const CTBbtreeNode & rhs ) [private]

Friends And Related Function Documentation

friend class CTBbtree [friend]

Definition at line 58 of file CTBbtree.hxx.

Member Data Documentation

const CTBuint32 CTBbtreeNode::status_lchild = 0x2 [static, private]

Definition at line 131 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_rchild = 0x1 [static, private]

Definition at line 132 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_childmask = status_lchild | status_rchild [static, private]

Definition at line 133 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_lheavy = 0x8 [static, private]

Definition at line 134 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_rheavy = 0x4 [static, private]

Definition at line 135 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_heavymask = status_lheavy | status_rheavy [static, private]

Definition at line 136 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_bitmask = status_childmask|status_heavymask [static, private]

Definition at line 137 of file CTBbtree.hxx.

const CTBuint32 CTBbtreeNode::status_deltaw = 16 [static, private]

Definition at line 138 of file CTBbtree.hxx.

CTBbtree* CTBbtreeNode::mp_head [private]

tree header.

Definition at line 140 of file CTBbtree.hxx.

CTBbtreeNode* CTBbtreeNode::mp_up [private]

up (parent).

Definition at line 141 of file CTBbtree.hxx.

CTBbtreeNode* CTBbtreeNode::mp_left [private]

left child.

Definition at line 142 of file CTBbtree.hxx.

CTBbtreeNode* CTBbtreeNode::mp_right [private]

right child.

Definition at line 143 of file CTBbtree.hxx.

CTBuint32 CTBbtreeNode::mi_status [private]

see Note 1.

Definition at line 144 of file CTBbtree.hxx.

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

Generated at Fri Oct 24 18:13:10 2003 for CTBbase by

CTBbtreeNode Class Reference

Public Methods

Private Methods

Private Attributes

Static Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation