Detailed Description

intrusive red black tree datastructure

Author: Robert Lion Gottwald

Definition in file rbtree.c.

#include "scip/rbtree.h"

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 25 of file rbtree.c.

Referenced by rbDeleteFixup().

◆ BLACK

#define BLACK ((uintptr_t)0x0u)

Definition at line 26 of file rbtree.c.

Referenced by SCIPrbtreeDelete_call().

◆ COLOR

#define COLOR ( node ) ((node)->parent & RED)

Definition at line 27 of file rbtree.c.

Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().

◆ IS_RED

#define IS_RED ( node ) ( (node) != NULL && COLOR(node) )

Definition at line 28 of file rbtree.c.

Referenced by rbInsertFixup().

◆ IS_BLACK

#define IS_BLACK ( node ) ( (node) == NULL || !COLOR(node) )

Definition at line 29 of file rbtree.c.

Referenced by rbDeleteFixup().

◆ MAKE_RED

#define MAKE_RED ( node ) do { (node)->parent |= RED; } while(0)

Definition at line 30 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 31 of file rbtree.c.

Referenced by rbDeleteFixup(), and rbInsertFixup().

◆ LEFT

#define LEFT 0

Definition at line 32 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 33 of file rbtree.c.

Referenced by rbDeleteFixup(), rbInsertFixup(), rbTransplant(), SCIPrbtreeDelete_call(), SCIPrbtreeInsert_call(), SCIPrbtreeLast_call(), and SCIPrbtreeSuccessor_call().

◆ OPPOSITE

#define OPPOSITE ( dir ) ( 1 - (dir) )

Definition at line 34 of file rbtree.c.

Referenced by rbDeleteFixup(), rbInsertFixup(), and rbRotate().

◆ PARENT

#define PARENT ( node ) ( (SCIP_RBTREENODE*)((node)->parent & ~RED) )

Definition at line 35 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 36 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 37 of file rbtree.c.

Referenced by rbDeleteFixup(), and SCIPrbtreeDelete_call().

Function Documentation

◆ rbRotate()

static void rbRotate	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	x,
		int	dir
	)

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 43 of file rbtree.c.

References SCIP_RBTreeNode::child, OPPOSITE, PARENT, and SET_PARENT.

Referenced by rbDeleteFixup(), and rbInsertFixup().

◆ rbInsertFixup()

static void rbInsertFixup	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	z
	)

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 73 of file rbtree.c.

References SCIP_RBTreeNode::child, IS_RED, LEFT, MAKE_BLACK, MAKE_RED, OPPOSITE, PARENT, rbRotate(), and RIGHT.

Referenced by SCIPrbtreeInsert_call().

◆ rbDeleteFixup()

static void rbDeleteFixup	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	x,
		SCIP_RBTREENODE *	nil
	)

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 121 of file rbtree.c.

References SCIP_RBTreeNode::child, COLOR, IS_BLACK, LEFT, MAKE_BLACK, MAKE_RED, OPPOSITE, PARENT, rbRotate(), RED, RIGHT, and SET_COLOR.

Referenced by SCIPrbtreeDelete_call().

◆ rbTransplant()

static void rbTransplant	(	SCIP_RBTREENODE **	root,
		SCIP_RBTREENODE *	u,
		SCIP_RBTREENODE *	v,
		SCIP_RBTREENODE *	nil
	)

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 180 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, 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 205 of file rbtree.c.

References SCIP_RBTreeNode::child, and LEFT.

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 219 of file rbtree.c.

References SCIP_RBTreeNode::child, 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 233 of file rbtree.c.

References SCIP_RBTreeNode::child, PARENT, RIGHT, and SCIPrbtreeFirst_call().

◆ 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 253 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, PARENT, and SCIPrbtreeLast_call().

◆ 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 275 of file rbtree.c.

References BLACK, SCIP_RBTreeNode::child, COLOR, LEFT, PARENT, SCIP_RBTreeNode::parent, rbDeleteFixup(), rbTransplant(), RIGHT, SCIPrbtreeFirst, SET_COLOR, and SET_PARENT.

◆ 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 330 of file rbtree.c.

References SCIP_RBTreeNode::child, LEFT, MAKE_RED, rbInsertFixup(), RIGHT, and SET_PARENT.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ RED

◆ BLACK

◆ COLOR

◆ IS_RED

◆ IS_BLACK

◆ MAKE_RED

◆ MAKE_BLACK

◆ LEFT

◆ RIGHT

◆ OPPOSITE

◆ PARENT

◆ SET_PARENT

◆ SET_COLOR

Function Documentation

◆ rbRotate()

◆ rbInsertFixup()

◆ rbDeleteFixup()

◆ rbTransplant()

◆ SCIPrbtreeFirst_call()

◆ SCIPrbtreeLast_call()

◆ SCIPrbtreeSuccessor_call()

◆ SCIPrbtreePredecessor_call()

◆ SCIPrbtreeDelete_call()

◆ SCIPrbtreeInsert_call()