SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
rbtree.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file rbtree.c
26 * @ingroup OTHER_CFILES
27 * @brief intrusive red black tree datastructure
28 * @author Leona Gottwald
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#include "scip/rbtree.h"
34
35#define RED ((uintptr_t)0x1u)
36#define BLACK ((uintptr_t)0x0u)
37#define COLOR(node) ((node)->parent & RED)
38#define IS_RED(node) ( (node) != NULL && COLOR(node) )
39#define IS_BLACK(node) ( (node) == NULL || !COLOR(node) )
40#define MAKE_RED(node) do { (node)->parent |= RED; } while(0)
41#define MAKE_BLACK(node) do { (node)->parent &= ~RED; } while(0)
42#define LEFT 0
43#define RIGHT 1
44#define OPPOSITE(dir) ( 1 - (dir) )
45#define PARENT(node) ( (SCIP_RBTREENODE*)((node)->parent & ~RED) )
46#define SET_PARENT(n, p) do { (n)->parent = (uintptr_t)(p) | COLOR(n); } while(0)
47#define SET_COLOR(n, c) do { if( c == RED ) { MAKE_RED(n); } else { MAKE_BLACK(n); } } while(0)
48
49/* functions for red black tree management; see Cormen, Thomas H. Introduction to algorithms. MIT press, 2009. */
50
51/** rotate the tree in the given direction */
52static
54 SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
55 SCIP_RBTREENODE* x, /**< node to perform rotation for */
56 int dir /**< direction of rotation */
57 )
58{
60 SCIP_RBTREENODE* y = x->child[OPPOSITE(dir)];
61 x->child[OPPOSITE(dir)] = y->child[dir];
62 if( y->child[dir] != NULL )
63 {
64 SET_PARENT(y->child[dir], x);
65 }
66
67 p = PARENT(x);
68 SET_PARENT(y, p);
69
70 if( p == NULL )
71 *root = y;
72 else if( x == p->child[dir] )
73 p->child[dir] = y;
74 else
75 p->child[OPPOSITE(dir)] = y;
76
77 y->child[dir] = x;
78 SET_PARENT(x, y);
79}
80
81/** restores the red-black tree property after an insert */
82static
84 SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
85 SCIP_RBTREENODE* z /**< inserted node */
86 )
87{
89 p = PARENT(z);
90
91 while( IS_RED(p) )
92 {
95 int dir;
96
97 pp = PARENT(p);
98 dir = p == pp->child[LEFT] ? RIGHT : LEFT;
99
100 y = pp->child[dir];
101 if( IS_RED(y) )
102 {
103 MAKE_BLACK(p);
104 MAKE_BLACK(y);
105 MAKE_RED(pp);
106 z = pp;
107 }
108 else
109 {
110 if( z == p->child[dir] )
111 {
112 z = p;
113 rbRotate(root, z, OPPOSITE(dir));
114 p = PARENT(z);
115 pp = PARENT(p);
116 }
117
118 MAKE_BLACK(p);
119 MAKE_RED(pp);
120 rbRotate(root, pp, dir);
121 }
122
123 p = PARENT(z);
124 }
125
126 MAKE_BLACK(*root);
127}
128
129/** restores the red-black tree property after an insert */
130static
132 SCIP_RBTREENODE** root, /**< pointer to store new root of the tree */
133 SCIP_RBTREENODE* x, /**< start node for fixup */
134 SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
135 )
136{
137 while( x != *root && IS_BLACK(x) )
138 {
141 int dir;
142
143 p = PARENT(x == NULL ? nil : x);
144 dir = x == p->child[LEFT] ? RIGHT : LEFT;
145
146 w = p->child[dir];
147 assert(w != NULL);
148
149 if( COLOR(w) == RED )
150 {
151 MAKE_BLACK(w);
152 MAKE_RED(p);
153 rbRotate(root, p, OPPOSITE(dir));
154 assert(p == PARENT(x == NULL ? nil : x));
155 w = p->child[dir];
156 assert(w != NULL);
157 }
158
159 if( IS_BLACK(w->child[LEFT]) && IS_BLACK(w->child[RIGHT]) )
160 {
161 MAKE_RED(w);
162 x = p;
163 }
164 else
165 {
166 if( IS_BLACK(w->child[dir]) )
167 {
168 MAKE_BLACK(w->child[OPPOSITE(dir)]);
169 MAKE_RED(w);
170 rbRotate(root, w, dir);
171 assert(p == PARENT(x == NULL ? nil : x));
172 w = p->child[dir];
173 }
174 SET_COLOR(w, COLOR(p));
175 MAKE_BLACK(p);
176 MAKE_BLACK(w->child[dir]);
177 rbRotate(root, p, OPPOSITE(dir));
178 x = *root;
179 }
180 }
181
182 if( x != NULL )
183 {
184 MAKE_BLACK(x);
185 }
186}
187
188/** replaces the subtree rooted at node u with the subtree rooted at node v */
189static
191 SCIP_RBTREENODE** root, /**< pointer to store the new root */
192 SCIP_RBTREENODE* u, /**< node u */
193 SCIP_RBTREENODE* v, /**< node v */
194 SCIP_RBTREENODE* nil /**< fake node representing NULL to properly reassemble the tree */
195 )
196{
198
199 up = PARENT(u);
200
201 if( up == NULL )
202 *root = v;
203 else if( u == up->child[LEFT] )
204 up->child[LEFT] = v;
205 else
206 up->child[RIGHT] = v;
207
208 if( v == NULL )
209 v = nil;
210
211 SET_PARENT(v, up);
212}
213
214/** get first element in tree with respect to sorting key */
216 SCIP_RBTREENODE* root /**< root of the tree */
217 )
218{
219 if( root == NULL )
220 return NULL;
221
222 while(root->child[LEFT] != NULL)
223 root = root->child[LEFT];
224
225 return root;
226}
227
228/** get last element in tree with respect to sorting key */
230 SCIP_RBTREENODE* root /**< root of the tree */
231 )
232{
233 if( root == NULL )
234 return NULL;
235
236 while(root->child[RIGHT] != NULL)
237 root = root->child[RIGHT];
238
239 return root;
240}
241
242/** get successor of given element in the tree */
244 SCIP_RBTREENODE* x /**< element to get successor for */
245 )
246{
248 if( x->child[RIGHT] != NULL )
249 return SCIPrbtreeFirst_call(x->child[RIGHT]);
250
251 y = PARENT(x);
252
253 while( y != NULL && x == y->child[RIGHT] )
254 {
255 x = y;
256 y = PARENT(y);
257 }
258
259 return y;
260}
261
262/** get predecessor of given element in the tree */
264 SCIP_RBTREENODE* x /**< element to get predecessor for */
265 )
266{
268 if( x->child[LEFT] != NULL )
269 return SCIPrbtreeLast_call(x->child[LEFT]);
270
271 y = PARENT(x);
272
273 while( y != NULL && x == y->child[LEFT] )
274 {
275 x = y;
276 y = PARENT(y);
277 }
278
279 return y;
280}
281
282/** delete the given node from the tree given by it's root node.
283 * The node must be contained in the tree rooted at root.
284 */
286 SCIP_RBTREENODE** root, /**< root of the tree */
287 SCIP_RBTREENODE* node /**< node to delete from tree */
288 )
289{
293 unsigned int yorigcolor;
294
295 nil.parent = 0;
296
297 y = node;
298 yorigcolor = COLOR(y);
299
300 if( node->child[LEFT] == NULL )
301 {
302 x = node->child[RIGHT];
303 rbTransplant(root, node, x, &nil);
304 }
305 else if( node->child[RIGHT] == NULL )
306 {
307 x = node->child[LEFT];
308 rbTransplant(root, node, x, &nil);
309 }
310 else
311 {
312 y = SCIPrbtreeFirst(node->child[RIGHT]);
313 yorigcolor = COLOR(y);
314 x = y->child[RIGHT];
315 if( PARENT(y) == node )
316 {
317 SET_PARENT(x == NULL ? &nil : x, y);
318 }
319 else
320 {
321 rbTransplant(root, y, y->child[RIGHT], &nil);
322 y->child[RIGHT] = node->child[RIGHT];
323 SET_PARENT(y->child[RIGHT], y);
324 }
325 rbTransplant(root, node, y, &nil);
326 y->child[LEFT] = node->child[LEFT];
327 SET_PARENT(y->child[LEFT], y);
328 SET_COLOR(y, COLOR(node));
329 }
330
331 if( yorigcolor == BLACK )
332 rbDeleteFixup(root, x, &nil);
333}
334
335/** insert node into the tree given by it's root. Requires the
336 * future parent and the position of the parent as returned by
337 * the tree's find function defined using the SCIP_DEF_RBTREE_FIND
338 * macro.
339 */
341 SCIP_RBTREENODE** root, /**< root of the tree */
342 SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */
343 int pos, /**< position of parent with respect to node, i.e.
344 * -1 if the parent's key comes before node and 1
345 * if the parent's key comes after the node
346 */
347 SCIP_RBTREENODE* node /**< node to insert into the tree */
348 )
349{
350 SET_PARENT(node, parent);
351 if( parent == NULL )
352 *root = node;
353 else if( pos > 0 )
354 parent->child[LEFT] = node;
355 else
356 parent->child[RIGHT] = node;
357
358 node->child[LEFT] = NULL;
359 node->child[RIGHT] = NULL;
360 MAKE_RED(node);
361 rbInsertFixup(root, node);
362}
SCIP_VAR * w
SCIP_VAR ** y
SCIP_VAR ** x
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
#define MAKE_RED(node)
Definition rbtree.c:40
void SCIPrbtreeDelete_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *node)
Definition rbtree.c:285
#define PARENT(node)
Definition rbtree.c:45
void SCIPrbtreeInsert_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node)
Definition rbtree.c:340
#define IS_BLACK(node)
Definition rbtree.c:39
#define IS_RED(node)
Definition rbtree.c:38
#define SET_COLOR(n, c)
Definition rbtree.c:47
#define LEFT
Definition rbtree.c:42
SCIP_RBTREENODE * SCIPrbtreeFirst_call(SCIP_RBTREENODE *root)
Definition rbtree.c:215
#define SET_PARENT(n, p)
Definition rbtree.c:46
static void rbRotate(SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, int dir)
Definition rbtree.c:53
#define BLACK
Definition rbtree.c:36
#define RIGHT
Definition rbtree.c:43
#define MAKE_BLACK(node)
Definition rbtree.c:41
static void rbInsertFixup(SCIP_RBTREENODE **root, SCIP_RBTREENODE *z)
Definition rbtree.c:83
#define RED
Definition rbtree.c:35
#define OPPOSITE(dir)
Definition rbtree.c:44
static void rbTransplant(SCIP_RBTREENODE **root, SCIP_RBTREENODE *u, SCIP_RBTREENODE *v, SCIP_RBTREENODE *nil)
Definition rbtree.c:190
SCIP_RBTREENODE * SCIPrbtreePredecessor_call(SCIP_RBTREENODE *x)
Definition rbtree.c:263
#define COLOR(node)
Definition rbtree.c:37
SCIP_RBTREENODE * SCIPrbtreeLast_call(SCIP_RBTREENODE *root)
Definition rbtree.c:229
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)
Definition rbtree.c:243
static void rbDeleteFixup(SCIP_RBTREENODE **root, SCIP_RBTREENODE *x, SCIP_RBTREENODE *nil)
Definition rbtree.c:131
intrusive red black tree datastructure
#define SCIPrbtreeFirst(root)
Definition rbtree.h:65
SCIP_RBTREENODE * child[2]
Definition rbtree.h:47