SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches

Detailed Description

binary search tree data structure

Functions

SCIP_RETCODE SCIPbtnodeCreate (SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr)
 
void SCIPbtnodeFree (SCIP_BT *tree, SCIP_BTNODE **node)
 
void * SCIPbtnodeGetData (SCIP_BTNODE *node)
 
SCIP_BTNODESCIPbtnodeGetParent (SCIP_BTNODE *node)
 
SCIP_BTNODESCIPbtnodeGetLeftchild (SCIP_BTNODE *node)
 
SCIP_BTNODESCIPbtnodeGetRightchild (SCIP_BTNODE *node)
 
SCIP_BTNODESCIPbtnodeGetSibling (SCIP_BTNODE *node)
 
SCIP_Bool SCIPbtnodeIsRoot (SCIP_BTNODE *node)
 
SCIP_Bool SCIPbtnodeIsLeaf (SCIP_BTNODE *node)
 
SCIP_Bool SCIPbtnodeIsLeftchild (SCIP_BTNODE *node)
 
SCIP_Bool SCIPbtnodeIsRightchild (SCIP_BTNODE *node)
 
void SCIPbtnodeSetData (SCIP_BTNODE *node, void *dataptr)
 
void SCIPbtnodeSetParent (SCIP_BTNODE *node, SCIP_BTNODE *parent)
 
void SCIPbtnodeSetLeftchild (SCIP_BTNODE *node, SCIP_BTNODE *left)
 
void SCIPbtnodeSetRightchild (SCIP_BTNODE *node, SCIP_BTNODE *right)
 
SCIP_RETCODE SCIPbtCreate (SCIP_BT **tree, BMS_BLKMEM *blkmem)
 
void SCIPbtFree (SCIP_BT **tree)
 
void SCIPbtPrintGml (SCIP_BT *tree, FILE *file)
 
SCIP_Bool SCIPbtIsEmpty (SCIP_BT *tree)
 
SCIP_BTNODESCIPbtGetRoot (SCIP_BT *tree)
 
void SCIPbtSetRoot (SCIP_BT *tree, SCIP_BTNODE *root)
 

Function Documentation

◆ SCIPbtnodeCreate()

SCIP_RETCODE SCIPbtnodeCreate ( SCIP_BT * tree,
SCIP_BTNODE ** node,
void * dataptr )

creates a binary tree node with sorting value and user data

creates a tree node with (optinal) user data

Parameters
treebinary tree
nodepointer to store the created node
dataptruser node data pointer, or NULL

Definition at line 8680 of file misc.c.

References assert(), btnodeCreateEmpty(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by checkOverloadViaThetaTree(), and insertThetanode().

◆ SCIPbtnodeFree()

void SCIPbtnodeFree ( SCIP_BT * tree,
SCIP_BTNODE ** node )

frees the binary node including the rooted subtree

Note
The user pointer (object) is not freed. If needed, it has to be done by the user.

frees the node including the rooted subtree

Note
The user pointer (object) is not freed. If needed, it has to be done by the user.
Parameters
treebinary tree
nodenode to be freed

Definition at line 8744 of file misc.c.

References assert(), btnodeFreeLeaf(), NULL, and SCIPbtnodeFree().

Referenced by deleteLambdaLeaf(), SCIPbtFree(), and SCIPbtnodeFree().

◆ SCIPbtnodeGetData()

◆ SCIPbtnodeGetParent()

SCIP_BTNODE * SCIPbtnodeGetParent ( SCIP_BTNODE * node)

returns the parent which can be NULL if the given node is the root

Parameters
nodenode

Definition at line 8799 of file misc.c.

References assert(), NULL, and SCIP_BtNode::parent.

Referenced by deleteLambdaLeaf(), insertThetanode(), SCIPbtnodeGetSibling(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), updateEnvelope(), and updateKeyOnTrace().

◆ SCIPbtnodeGetLeftchild()

◆ SCIPbtnodeGetRightchild()

◆ SCIPbtnodeGetSibling()

SCIP_BTNODE * SCIPbtnodeGetSibling ( SCIP_BTNODE * node)

returns the sibling of the node or NULL if does not exist

Parameters
nodenode

Definition at line 8829 of file misc.c.

References assert(), NULL, SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), and SCIPbtnodeGetRightchild().

◆ SCIPbtnodeIsRoot()

SCIP_Bool SCIPbtnodeIsRoot ( SCIP_BTNODE * node)

returns whether the node is a root node

Parameters
nodenode

Definition at line 8849 of file misc.c.

References assert(), NULL, and SCIP_BtNode::parent.

Referenced by deleteLambdaLeaf(), inferboundsEdgeFinding(), SCIPbtnodeIsLeftchild(), SCIPbtnodeIsRightchild(), and updateKeyOnTrace().

◆ SCIPbtnodeIsLeaf()

◆ SCIPbtnodeIsLeftchild()

SCIP_Bool SCIPbtnodeIsLeftchild ( SCIP_BTNODE * node)

returns TRUE if the given node is left child

Parameters
nodenode

Definition at line 8869 of file misc.c.

References FALSE, SCIPbtnodeGetLeftchild(), SCIPbtnodeGetParent(), SCIPbtnodeIsRoot(), and TRUE.

Referenced by deleteLambdaLeaf(), and updateKeyOnTrace().

◆ SCIPbtnodeIsRightchild()

SCIP_Bool SCIPbtnodeIsRightchild ( SCIP_BTNODE * node)

returns TRUE if the given node is right child

Parameters
nodenode

Definition at line 8887 of file misc.c.

References FALSE, SCIPbtnodeGetParent(), SCIPbtnodeGetRightchild(), SCIPbtnodeIsRoot(), and TRUE.

Referenced by deleteLambdaLeaf().

◆ SCIPbtnodeSetData()

void SCIPbtnodeSetData ( SCIP_BTNODE * node,
void * dataptr )

sets the give node data

Note
The old user pointer is not freed.
Parameters
nodenode
dataptrnode user data pointer

Definition at line 8908 of file misc.c.

References assert(), SCIP_BtNode::dataptr, and NULL.

◆ SCIPbtnodeSetParent()

void SCIPbtnodeSetParent ( SCIP_BTNODE * node,
SCIP_BTNODE * parent )

sets parent node

Note
The old parent including the rooted subtree is not delete.
Parameters
nodenode
parentnew parent node, or NULL

Definition at line 8922 of file misc.c.

References assert(), NULL, and SCIP_BtNode::parent.

Referenced by deleteLambdaLeaf(), and insertThetanode().

◆ SCIPbtnodeSetLeftchild()

void SCIPbtnodeSetLeftchild ( SCIP_BTNODE * node,
SCIP_BTNODE * left )

sets left child

Note
The old left child including the rooted subtree is not delete.
Parameters
nodenode
leftnew left child, or NULL

Definition at line 8936 of file misc.c.

References assert(), SCIP_BtNode::left, and NULL.

Referenced by deleteLambdaLeaf(), and insertThetanode().

◆ SCIPbtnodeSetRightchild()

void SCIPbtnodeSetRightchild ( SCIP_BTNODE * node,
SCIP_BTNODE * right )

sets right child

Note
The old right child including the rooted subtree is not delete.
Parameters
nodenode
rightnew right child, or NULL

Definition at line 8950 of file misc.c.

References assert(), NULL, and SCIP_BtNode::right.

Referenced by deleteLambdaLeaf(), and insertThetanode().

◆ SCIPbtCreate()

SCIP_RETCODE SCIPbtCreate ( SCIP_BT ** tree,
BMS_BLKMEM * blkmem )

creates an binary tree

Parameters
treepointer to store the created binary tree
blkmemblock memory used to createnode

Definition at line 8961 of file misc.c.

References assert(), BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by checkOverloadViaThetaTree().

◆ SCIPbtFree()

void SCIPbtFree ( SCIP_BT ** tree)

frees binary tree

Note
The user pointers (object) of the search nodes are not freed. If needed, it has to be done by the user.

frees binary tree

Note
The user pointers (object) of the nodes are not freed. If needed, it has to be done by the user.
Parameters
treepointer to binary tree

Definition at line 8980 of file misc.c.

References assert(), BMSfreeBlockMemory, NULL, and SCIPbtnodeFree().

Referenced by checkOverloadViaThetaTree().

◆ SCIPbtPrintGml()

void SCIPbtPrintGml ( SCIP_BT * tree,
FILE * file )

prints the binary tree in GML format into the given file

Parameters
treebinary tree
filefile to write to

Definition at line 9032 of file misc.c.

References assert(), btPrintSubtree(), nnodes, NULL, SCIPbtGetRoot(), SCIPbtIsEmpty(), SCIPgmlWriteClosing(), SCIPgmlWriteOpening(), and TRUE.

◆ SCIPbtIsEmpty()

SCIP_Bool SCIPbtIsEmpty ( SCIP_BT * tree)

returns whether the binary tree is empty (has no nodes)

Parameters
treebinary tree

Definition at line 9062 of file misc.c.

References assert(), NULL, and SCIP_Bt::root.

Referenced by checkOverloadViaThetaTree(), inferboundsEdgeFinding(), insertThetanode(), and SCIPbtPrintGml().

◆ SCIPbtGetRoot()

SCIP_BTNODE * SCIPbtGetRoot ( SCIP_BT * tree)

returns the root node of the binary tree or NULL if the binary tree is empty

returns the the root node of the binary or NULL if the binary tree is empty

Parameters
treetree to be evaluated

Definition at line 9072 of file misc.c.

References assert(), NULL, and SCIP_Bt::root.

Referenced by checkOverloadViaThetaTree(), inferboundsEdgeFinding(), insertThetanode(), and SCIPbtPrintGml().

◆ SCIPbtSetRoot()

void SCIPbtSetRoot ( SCIP_BT * tree,
SCIP_BTNODE * root )

sets root node

Note
The old root including the rooted subtree is not delete.
Parameters
treetree to be evaluated
rootnew root, or NULL

Definition at line 9085 of file misc.c.

References assert(), NULL, and SCIP_Bt::root.

Referenced by deleteLambdaLeaf(), and insertThetanode().