Detailed Description
intrusive red black tree datastructure
Definition in file rbtree.c.
#include "scip/rbtree.h"
Go to the source code of this file.
Macros | |
#define | RED ((uintptr_t)0x1u) |
#define | BLACK ((uintptr_t)0x0u) |
#define | COLOR(node) ((node)->parent & RED) |
#define | IS_RED(node) ( (node) != NULL && COLOR(node) ) |
#define | IS_BLACK(node) ( (node) == NULL || !COLOR(node) ) |
#define | MAKE_RED(node) do { (node)->parent |= RED; } while(0) |
#define | MAKE_BLACK(node) do { (node)->parent &= ~RED; } while(0) |
#define | LEFT 0 |
#define | RIGHT 1 |
#define | OPPOSITE(dir) ( 1 - (dir) ) |
#define | PARENT(node) ( (SCIP_RBTREENODE*)((node)->parent & ~RED) ) |
#define | SET_PARENT(n, p) do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0) |
#define | SET_COLOR(n, c) do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0) |
Functions | |
static void | rbRotate (SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, int dir) |
static void | rbInsertFixup (SCIP_RBTREENODE **root, SCIP_RBTREENODE *z) |
static void | rbDeleteFixup (SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, SCIP_RBTREENODE *nil) |
static void | rbTransplant (SCIP_RBTREENODE **root, SCIP_RBTREENODE *u, SCIP_RBTREENODE *v, SCIP_RBTREENODE *nil) |
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) |
Macro Definition Documentation
◆ RED
#define RED ((uintptr_t)0x1u) |
Definition at line 35 of file rbtree.c.
Referenced by rbDeleteFixup().
◆ BLACK
#define BLACK ((uintptr_t)0x0u) |
Definition at line 36 of file rbtree.c.
Referenced by SCIPrbtreeDelete_call().
◆ COLOR
#define COLOR | ( | node | ) | ((node)->parent & RED) |
Definition at line 37 of file rbtree.c.
Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().
◆ IS_RED
Definition at line 38 of file rbtree.c.
Referenced by rbInsertFixup().
◆ IS_BLACK
Definition at line 39 of file rbtree.c.
Referenced by rbDeleteFixup().
◆ MAKE_RED
#define MAKE_RED | ( | node | ) | do { (node)->parent |= RED; } while(0) |
Definition at line 40 of file rbtree.c.
Referenced by rbDeleteFixup(), rbInsertFixup(), and SCIPrbtreeInsert_call().
◆ MAKE_BLACK
#define MAKE_BLACK | ( | node | ) | do { (node)->parent &= ~RED; } while(0) |
Definition at line 41 of file rbtree.c.
Referenced by rbDeleteFixup(), and rbInsertFixup().
◆ LEFT
#define LEFT 0 |
Definition at line 42 of file rbtree.c.
Referenced by rbDeleteFixup(), rbInsertFixup(), rbTransplant(), SCIPrbtreeDelete_call(), SCIPrbtreeFirst_call(), SCIPrbtreeInsert_call(), and SCIPrbtreePredecessor_call().
◆ RIGHT
#define RIGHT 1 |
Definition at line 43 of file rbtree.c.
Referenced by addScenarioVarsAndConsToProb(), rbDeleteFixup(), rbInsertFixup(), rbTransplant(), SCIPrbtreeDelete_call(), SCIPrbtreeInsert_call(), SCIPrbtreeLast_call(), and SCIPrbtreeSuccessor_call().
◆ OPPOSITE
#define OPPOSITE | ( | dir | ) | ( 1 - (dir) ) |
Definition at line 44 of file rbtree.c.
Referenced by rbDeleteFixup(), rbInsertFixup(), and rbRotate().
◆ PARENT
#define PARENT | ( | node | ) | ( (SCIP_RBTREENODE*)((node)->parent & ~RED) ) |
Definition at line 45 of file rbtree.c.
Referenced by rbDeleteFixup(), rbInsertFixup(), rbRotate(), rbTransplant(), SCIPrbtreeDelete_call(), SCIPrbtreePredecessor_call(), and SCIPrbtreeSuccessor_call().
◆ SET_PARENT
#define SET_PARENT | ( | n, | |
p | |||
) | do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0) |
Definition at line 46 of file rbtree.c.
Referenced by rbRotate(), rbTransplant(), SCIPrbtreeDelete_call(), and SCIPrbtreeInsert_call().
◆ SET_COLOR
#define SET_COLOR | ( | n, | |
c | |||
) | do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0) |
Definition at line 47 of file rbtree.c.
Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().
Function Documentation
◆ rbRotate()
|
static |
rotate the tree in the given direction
- Parameters
-
root pointer to store new root of the tree x node to perform rotation for dir direction of rotation
Definition at line 53 of file rbtree.c.
References SCIP_RBTreeNode::child, NULL, OPPOSITE, PARENT, SET_PARENT, x, and y.
Referenced by rbDeleteFixup(), and rbInsertFixup().
◆ rbInsertFixup()
|
static |
restores the red-black tree property after an insert
- Parameters
-
root pointer to store new root of the tree z inserted node
Definition at line 83 of file rbtree.c.
References SCIP_RBTreeNode::child, IS_RED, LEFT, MAKE_BLACK, MAKE_RED, OPPOSITE, PARENT, rbRotate(), RIGHT, and y.
Referenced by SCIPrbtreeInsert_call().
◆ rbDeleteFixup()
|
static |
restores the red-black tree property after an insert
- Parameters
-
root pointer to store new root of the tree x start node for fixup nil fake node representing NULL to properly reassemble the tree
Definition at line 131 of file rbtree.c.
References SCIP_RBTreeNode::child, COLOR, IS_BLACK, LEFT, MAKE_BLACK, MAKE_RED, NULL, OPPOSITE, PARENT, rbRotate(), RED, RIGHT, SET_COLOR, and w.
Referenced by SCIPrbtreeDelete_call().
◆ rbTransplant()
|
static |
replaces the subtree rooted at node u with the subtree rooted at node v
- Parameters
-
root pointer to store the new root u node u v node v nil fake node representing NULL to properly reassemble the tree
Definition at line 190 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, NULL, PARENT, RIGHT, and SET_PARENT.
Referenced by SCIPrbtreeDelete_call().
◆ SCIPrbtreeFirst_call()
SCIP_RBTREENODE* SCIPrbtreeFirst_call | ( | SCIP_RBTREENODE * | root | ) |
get first element in tree with respect to sorting key
- Parameters
-
root root of the tree
Definition at line 215 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, and NULL.
Referenced by SCIPrbtreeSuccessor_call().
◆ SCIPrbtreeLast_call()
SCIP_RBTREENODE* SCIPrbtreeLast_call | ( | SCIP_RBTREENODE * | root | ) |
get last element in tree with respect to sorting key
- Parameters
-
root root of the tree
Definition at line 229 of file rbtree.c.
References SCIP_RBTreeNode::child, NULL, and RIGHT.
Referenced by SCIPrbtreePredecessor_call().
◆ SCIPrbtreeSuccessor_call()
SCIP_RBTREENODE* SCIPrbtreeSuccessor_call | ( | SCIP_RBTREENODE * | x | ) |
get successor of given element in the tree
- Parameters
-
x element to get successor for
Definition at line 243 of file rbtree.c.
References SCIP_RBTreeNode::child, NULL, PARENT, RIGHT, SCIPrbtreeFirst_call(), and y.
◆ SCIPrbtreePredecessor_call()
SCIP_RBTREENODE* SCIPrbtreePredecessor_call | ( | SCIP_RBTREENODE * | x | ) |
get predecessor of given element in the tree
- Parameters
-
x element to get predecessor for
Definition at line 263 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, NULL, PARENT, SCIPrbtreeLast_call(), and y.
◆ SCIPrbtreeDelete_call()
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.
- Parameters
-
root root of the tree node node to delete from tree
Definition at line 285 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.
◆ SCIPrbtreeInsert_call()
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.
- Parameters
-
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 340 of file rbtree.c.
References SCIP_RBTreeNode::child, LEFT, MAKE_RED, NULL, rbInsertFixup(), RIGHT, and SET_PARENT.