![]() |
Elm
2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
|
#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 |
|
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, K, C, A >::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, K, C, A >::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, K, C, A >::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 |
Referenced by GenTree< T, K, C, A >::clear(), GenTree< T, K, C, A >::copy(), and GenTree< T, K, C, A >::root().
|
staticprotected |
Referenced by AbstractTree::Stack::push().