AbstractTree Class Reference

#include <elm/avl/GenTree.h>

Inheritance diagram for AbstractTree:

Classes
class	Node
class	Stack

Public Member Functions
int	count (void) const

Protected Types
enum	dir_t { LEFT = -1, NONE = 0, RIGHT = +1 }
typedef signed char	balance_t

Protected Member Functions
	AbstractTree (void)
Node **	link (const Stack &s)
void	exchange (Node *n, Node *m)
void	insert (Stack &stack, Node *node)
void	rotateRight (Stack &s)
void	rotateLeft (Stack &s)
void	remove (Stack &stack, Node *n)
Node *	leftMost (Stack &s, Node *n)

Protected Attributes
Node *	_root
int	_cnt

Static Protected Attributes
static const int	MAX_HEIGHT = 32

Member Typedef Documentation

balance_t

typedef signed char balance_t

protected

Member Enumeration Documentation

dir_t

enum dir_t

protected

Enumerator
LEFT
NONE
RIGHT

Constructor & Destructor Documentation

AbstractTree()

AbstractTree ( void  )

inlineprotected

Member Function Documentation

count()

int count ( void  ) const

inline

Count the number of nodes.

Returns

Number of nodes.

References AbstractTree::_cnt.

exchange()

void exchange ( Node *  n, Node *  m  )

protected

Exchange two nodes values (does not update the parent link).

Parameters

n	First node.
m	Second node.

References AbstractTree::Node::_bal, AbstractTree::Node::_left, and AbstractTree::Node::_right.

insert()

void insert ( Stack &  s, Node *  node  )

protected

Perform actual insertion and re-balancing of a new value.

Parameters

s	Tree traversal stack.
node	Added node.

References AbstractTree::Node::_bal, AbstractTree::Node::_left, AbstractTree::Node::_right, StaticStack< T, N >::isEmpty(), elm::io::LEFT, StaticStack< T, N >::pop(), AbstractTree::Stack::push(), elm::io::RIGHT, AbstractTree::Stack::topDir(), and AbstractTree::Stack::topNode().

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::add().

leftMost()

AbstractTree::Node * leftMost ( Stack &  s, Node *  n  )

protected

Find the left node starting at this point.

Parameters

s	Stack containing parents of n and to fill with parent of leftmost node.
n	Current node.

Returns

Leftmost node.

References AbstractTree::Node::_left, elm::io::LEFT, and AbstractTree::Stack::push().

Referenced by Queue< T, C, A >::get(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::remove().

link()

AbstractTree::Node ** link ( const Stack &  s )

protected

Get the link to the pointer of the top-node corresponding to the followed path (basically used to relink nodes).

Parameters

s	Stack to the concerned node.

References AbstractTree::Node::_left, AbstractTree::Node::_right, StaticStack< T, N >::isEmpty(), elm::io::LEFT, AbstractTree::Stack::topDir(), and AbstractTree::Stack::topNode().

remove()

void remove ( Stack &  s, Node *  n  )

protected

Perform removal and re-balance operation.

Parameters

s	Parent stack.
n	Replacing node.

References StaticStack< T, N >::isEmpty(), elm::io::LEFT, elm::io::NONE, elm::io::p(), StaticStack< T, N >::pop(), AbstractTree::Stack::push(), elm::io::RIGHT, AbstractTree::Stack::topDir(), and AbstractTree::Stack::topNode().

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::remove().

rotateLeft()

void rotateLeft ( Stack &  s )

protected

Perform left-balancing of the node at the top of the stack.

Parameters

s	Stack which top-node must be balanced.

References AbstractTree::Node::_bal, AbstractTree::Node::_left, AbstractTree::Node::_right, elm::max(), elm::min(), StaticStack< T, N >::pop(), and AbstractTree::Stack::topNode().

rotateRight()

void rotateRight ( Stack &  s )

protected

Perform right-balancing of the node at the top of the stack.

Parameters

s	Stack which top-node must be balanced.

References AbstractTree::Node::_bal, AbstractTree::Node::_left, AbstractTree::Node::_right, elm::max(), elm::min(), StaticStack< T, N >::pop(), and AbstractTree::Stack::topNode().

Member Data Documentation

_cnt

int _cnt

protected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::clear(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::copy(), AbstractTree::count(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::count(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::isEmpty().

_root

Node* _root

protected

Referenced by GenTree< T, IdAdapter< T >, elm::Comparator< T > >::clear(), GenTree< T, IdAdapter< T >, elm::Comparator< T > >::copy(), and GenTree< T, IdAdapter< T >, elm::Comparator< T > >::root().

MAX_HEIGHT

const int MAX_HEIGHT = 32

staticprotected

Referenced by AbstractTree::Stack::push().

---

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

• include/elm/avl/GenTree.h
• src/avl_GenTree.cpp