---

CTBbtree Class Reference

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

#include "CTBbtree.hxx"

Inheritance diagram for CTBbtree:

[legend]Collaboration diagram for CTBbtree:

[legend]List of all members.

Public Methods
	CTBbtree ()
	CTBbtree (const CTBbtree &rhs)
virtual	~CTBbtree ()
CTBbtreeNode *	RNode () const
CTBbtreeNode *	First () const
CTBbtreeNode *	Last () const
CTBsize	Size () const
void	Clear ()
void	TreeHeight (int &i_minh, int &i_maxh, float &f_avrp) const
bool	TreeCheck (ostream *p_os=0) const
void	Dump (int i_indent=0, ostream &os=cout, const char *p_text=0) const
CTBbtreeNode *	operator[] (CTBint i_ind) const
CTBbtree &	operator= (const CTBbtree &rhs)
Private Attributes
CTBbtreeNode *	mp_rnode
CTBbtreeNode *	mp_first
CTBbtreeNode *	mp_last
CTBint	mi_size
Friends
class	CTBbtreeNode

---

Detailed Description

Base class for the implementation of binary tree headers.

The class CTBbtree implements together with CTBbtreeNode all the base functionality of a binary tree. Both classes are usually used as base classes for the implementation of associative containers, like CTBmap, but are also useful for the implementation of some types of queue containers.

The class pair CTBbtree and CTBbtreeNode implements AVL-Trees first proposed by Adel'son-Vel'skil and Landis and described in great detail in chapter 6.2.3 of Knuth Volume III. In particular, it uses for

• rebalancing after insertion: Algorithm 6.2.3A
• rebalancing after removal: the `Foster algorithm'
• deletion: Algorithm 6.2.3D
• access by rank: Algorithm 6.2.3B

Definition at line 20 of file CTBbtree.hxx.

---

Constructor & Destructor Documentation

CTBbtree::CTBbtree (  )  [inline]

Default constructor. Definition at line 17 of file CTBbtree.icc.

CTBbtree::CTBbtree (  const CTBbtree & rhs )  [inline]

Copy constructor. Definition at line 27 of file CTBbtree.icc.

CTBbtree::~CTBbtree (  )  [virtual]

Virtual destructor. Definition at line 45 of file CTBbtree.cxx.

---

Member Function Documentation

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

Returns the root node. Definition at line 39 of file CTBbtree.icc. Referenced by CTBmap::LocateMatchOrBound(), and CTBgset::LocateMatchOrBound().

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

Returns the first (left most) node. Reimplemented in CTBgset, and CTBmap. Definition at line 47 of file CTBbtree.icc. Referenced by CTBmap::First(), and CTBgset::First().

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

Returns the last (right most) node. Reimplemented in CTBgset, and CTBmap. Definition at line 55 of file CTBbtree.icc. Referenced by CTBmap::Last(), and CTBgset::Last().

CTBsize CTBbtree::Size (  )  const [inline]

Returns the number of nodes in the tree (see size). Reimplemented in CTBgset, and CTBmap. Definition at line 63 of file CTBbtree.icc. Referenced by CTBmap::Size(), CTBgset::Size(), CTBmap::operator bool(), and CTBgset::operator bool().

void CTBbtree::Clear (  )

Delete all nodes. The Clear() function will delete all nodes of the tree. Size() will return 0 after Clear() has been called. This function is substantially faster than an explicit node-by-node deletion with the CTBbtreeNode::Remove() function because it avoids all rebalancing. Reimplemented in CTBgset, and CTBmap. Definition at line 60 of file CTBbtree.cxx. Referenced by CTBmap::Clear(), CTBgset::Clear(), operator=(), and ~CTBbtree().

void CTBbtree::TreeHeight (  int & i_minh, int & i_maxh, float & f_avrp )  const

Determine tree properties. Scans the tree and returns Parameters: i_minh   the minimal height (length of shortest path to a leave). i_maxh   the maximal height (length of longest path to a leave). f_avrp   the average path length to a node (equals the average number of compare operations needed to locate a node in a tree search). Definition at line 132 of file CTBbtree.cxx. Referenced by Dump().

bool CTBbtree::TreeCheck (  ostream * p_os = 0 )  const

Check whether tree is balanced. Traverses the tree and checks whether it is balanced at each node and returns true if balanced and false in case of an imbalance. If p_os is non-null, an error message is written to p_os for each unbalanced node. Definition at line 157 of file CTBbtree.cxx. Referenced by Dump().

void CTBbtree::Dump (  int i_indent = 0, ostream & os = cout, const char * p_text = 0 )  const

Dump tree structure. Dumps the tree header to os in the usual manner and prints in addition a one line summary for each node of the form: rank lvl bc this up left right location 0 2 +l 804e670 804e648 - 804e710 l^ 1 3 0r 804e710 804e670 - - Rl^ 2 1 +^ 804e648 - 804e670 804e6c0 ^ 3 3 0l 804e6e8 804e6c0 - - Lr^ 4 2 +r 804e6c0 804e648 804e6e8 804e738 r^ 5 4 0l 804e698 804e738 - - Lrr^ 6 3 0r 804e738 804e6c0 804e698 804e760 rr^ 7 4 0r 804e760 804e738 - - Rrr^ where the columns contain rank: Rank() of the node lvl: Distance from root node b: Balance factor (- left heavy, + right heavy, 0 balanced) c: Child mode (l left child, r right child, ^ root node) location: Indicates linkage path from node to root, where l/r indicate left or right child and ^ inicates root node. An uppercase L/R inicates a left or right leave child. Reimplemented in CTBgset, and CTBmap. Definition at line 200 of file CTBbtree.cxx. Referenced by CTBmap::Dump(), and CTBgset::Dump().

CTBbtreeNode * CTBbtree::operator[] (  CTBint i_ind )  const

Locate a node by rank. Locates the node with rank i_ind and returns a pointer to this node or null if i_ind < 0 or i_ind >= Size(). Definition at line 290 of file CTBbtree.cxx.

CTBbtree & CTBbtree::operator= (  const CTBbtree & rhs )

Assignment operator. The assignment operator is substantially faster than a node-by-node copy using CTBbtreeNode::Insert(). It produces an exact copy of the source tree rhs with all its balacing properties and thus avoids all rebalancing. To `copy' a CTBbtreeNode the CTBbtreeNode::Clone() function is used, which acts as a virtual constructor. Definition at line 321 of file CTBbtree.cxx. Referenced by CTBbtree(), CTBmap::operator=(), and CTBgset::operator=().

---

Friends And Related Function Documentation

friend class CTBbtreeNode [friend]

Definition at line 22 of file CTBbtree.hxx.

---

Member Data Documentation

CTBbtreeNode* CTBbtree::mp_rnode [private]

root node. Definition at line 50 of file CTBbtree.hxx.

CTBbtreeNode* CTBbtree::mp_first [private]

first node. Definition at line 51 of file CTBbtree.hxx.

CTBbtreeNode* CTBbtree::mp_last [private]

last node. Definition at line 52 of file CTBbtree.hxx.

CTBint CTBbtree::mi_size [private]

number of nodes. Definition at line 53 of file CTBbtree.hxx.

---

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

• CTBbtree.cxx
• CTBbtree.hxx
• CTBbtree.icc

---