![]() |
Elm
2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
|
#include <elm/avl/GenTree.h>
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 |
|
protected |
|
protected |
|
inlineprotected |
|
inline |
Exchange two nodes values (does not update the parent link).
n | First node. |
m | Second node. |
References AbstractTree::Node::_bal, AbstractTree::Node::_left, and AbstractTree::Node::_right.
Perform actual insertion and re-balancing of a new value.
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().
|
protected |
Find the left node starting at this point.
s | Stack containing parents of n and to fill with parent of leftmost node. |
n | Current 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().
|
protected |
Get the link to the pointer of the top-node corresponding to the followed path (basically used to relink nodes).
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().
Perform removal and re-balance operation.
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().
Perform left-balancing of the node at the top of the stack.
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().
Perform right-balancing of the node at the top of the stack.
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().
|
protected |
|
protected |
|
staticprotected |
Referenced by AbstractTree::Stack::push().