intrusive red black tree datastructure
Definition in file rbtree.h.
Go to the source code of this file.
Data Structures | |
struct | SCIP_RBTreeNode |
Macros | |
#define | SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode |
#define | SCIPrbtreeFirst(root) |
#define | SCIPrbtreeLast(root) |
#define | SCIPrbtreeSuccessor(x) |
#define | SCIPrbtreePredecessor(x) |
#define | SCIPrbtreeDelete(root, node) |
#define | SCIPrbtreeInsert(r, p, c, n) |
#define | SCIPrbtreeFindInt(r, k, n) |
#define | SCIPrbtreeFindReal(r, k, n) |
#define | SCIPrbtreeFindPtr(c, r, k, n) |
#define | SCIPrbtreeFindElem(c, r, k, n) |
#define | FOR_EACH_NODE(type, n, r, body) |
#define | SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT) |
Functions | |
SCIP_RBTREENODE * | SCIPrbtreeFirst_call (SCIP_RBTREENODE *root) |
SCIP_RBTREENODE * | SCIPrbtreeLast_call (SCIP_RBTREENODE *root) |
SCIP_RBTREENODE * | SCIPrbtreeSuccessor_call (SCIP_RBTREENODE *x) |
SCIP_RBTREENODE * | SCIPrbtreePredecessor_call (SCIP_RBTREENODE *x) |
void | SCIPrbtreeDelete_call (SCIP_RBTREENODE **root, SCIP_RBTREENODE *node) |
void | SCIPrbtreeInsert_call (SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node) |
#define SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode |
#define SCIPrbtreeFirst | ( | root | ) |
Definition at line 65 of file rbtree.h.
Referenced by SCIPrbtreeDelete_call().
#define SCIPrbtreeLast | ( | root | ) |
#define SCIPrbtreeSuccessor | ( | x | ) |
#define SCIPrbtreePredecessor | ( | x | ) |
#define SCIPrbtreeDelete | ( | root, | |
node ) |
Definition at line 69 of file rbtree.h.
Referenced by unlinkChunk().
Definition at line 70 of file rbtree.h.
Referenced by linkChunk().
#define SCIPrbtreeFindInt | ( | r, | |
k, | |||
n ) |
#define SCIPrbtreeFindReal | ( | r, | |
k, | |||
n ) |
#define FOR_EACH_NODE | ( | type, | |
n, | |||
r, | |||
body ) |
Definition at line 77 of file rbtree.h.
Referenced by BMScheckEmptyBlockMemory_call(), BMSdisplayBlockMemory_call(), and clearChkmem().
#define SCIP_DEF_RBTREE_FIND | ( | NAME, | |
KEYTYPE, | |||
NODETYPE, | |||
LT, | |||
GT ) |
typedef struct SCIP_RBTreeNode SCIP_RBTREENODE |
SCIP_RBTREENODE * SCIPrbtreeFirst_call | ( | SCIP_RBTREENODE * | root | ) |
get first element in tree with respect to sorting key
root | root of the tree |
Definition at line 227 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, and NULL.
Referenced by SCIPrbtreeSuccessor_call().
SCIP_RBTREENODE * SCIPrbtreeLast_call | ( | SCIP_RBTREENODE * | root | ) |
get last element in tree with respect to sorting key
root | root of the tree |
Definition at line 241 of file rbtree.c.
References SCIP_RBTreeNode::child, NULL, and RIGHT.
Referenced by SCIPrbtreePredecessor_call().
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call | ( | SCIP_RBTREENODE * | x | ) |
SCIP_RBTREENODE * SCIPrbtreePredecessor_call | ( | SCIP_RBTREENODE * | x | ) |
void SCIPrbtreeDelete_call | ( | SCIP_RBTREENODE ** | root, |
SCIP_RBTREENODE * | node ) |
delete the given node from the tree given by it's root node. The node must be contained in the tree rooted at root.
root | root of the tree |
node | node to delete from tree |
Definition at line 297 of file rbtree.c.
References BLACK, SCIP_RBTreeNode::child, COLOR, LEFT, NULL, PARENT, SCIP_RBTreeNode::parent, rbDeleteFixup(), rbTransplant(), RIGHT, SCIPrbtreeFirst, SET_COLOR, SET_PARENT, x, and y.
void SCIPrbtreeInsert_call | ( | SCIP_RBTREENODE ** | root, |
SCIP_RBTREENODE * | parent, | ||
int | pos, | ||
SCIP_RBTREENODE * | node ) |
insert node into the tree given by it's root. Requires the future parent and the position of the parent as returned by the tree's find function defined using the SCIP_DEF_RBTREE_FIND macro.
root | root of the tree |
parent | future parent of node to be inserted |
pos | position of parent with respect to node, i.e. -1 if the parent's key comes before node and 1 if the parent's key comes after the node |
node | node to insert into the tree |
Definition at line 352 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, NULL, SCIP_RBTreeNode::parent, rbInsertFixup(), RED, and RIGHT.