1 /* Ordered {set,map} data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* An AVL tree is a binary tree where
19 1. The height of each node is calculated as
20 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
21 2. The heights of the subtrees of each node differ by at most 1:
22 | heightof(right) - heightof(left) | <= 1.
23 3. The index of the elements in the node.left subtree are smaller than
24 the index of node.
25 The index of the elements in the node.right subtree are larger than
26 the index of node.
27 */
28
29 /* Tree node implementation, valid for this file only. */
30 struct NODE_IMPL
31 {
32 struct NODE_IMPL *left; /* left branch, or NULL */
33 struct NODE_IMPL *right; /* right branch, or NULL */
34 /* Parent pointer, or NULL. The parent pointer is not needed for most
35 operations. It is needed so that a NODE_T can be returned without
36 memory allocation, on which the functions <container>_remove_node,
37 <container>_add_before, <container>_add_after can be implemented. */
38 struct NODE_IMPL *parent;
39 int balance; /* heightof(right) - heightof(left),
40 always = -1 or 0 or 1 */
41 NODE_PAYLOAD_FIELDS
42 };
43 typedef struct NODE_IMPL * NODE_T;
44
45 /* Concrete CONTAINER_IMPL type, valid for this file only. */
46 struct CONTAINER_IMPL
47 {
48 struct CONTAINER_IMPL_BASE base;
49 struct NODE_IMPL *root; /* root node or NULL */
50 size_t count; /* number of nodes */
51 };
52
53 /* An AVL tree of height h has at least F_(h+2) - 1 [Fibonacci number] and at
54 most 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would
55 have at least F_87 - 1 elements, and because even on 64-bit machines,
56 sizeof (NODE_IMPL) * (F_87 - 1) > 2^64
57 this would exceed the address space of the machine. */
58 #define MAXHEIGHT 83
59
60 /* Ensures the tree is balanced, after an insertion or deletion operation.
61 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
62 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
63 Rotation operations are performed starting at PARENT (not NODE itself!). */
64 static void
65 rebalance (CONTAINER_T container,
66 NODE_T node, int height_diff, NODE_T parent)
67 {
68 for (;;)
69 {
70 NODE_T child;
71 int previous_balance;
72 int balance_diff;
73 NODE_T nodeleft;
74 NODE_T noderight;
75
76 child = node;
77 node = parent;
78
79 previous_balance = node->balance;
80
81 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
82 branch's height has increased by 1 or the left branch's height has
83 decreased by 1, -1 if the right branch's height has decreased by 1 or
84 the left branch's height has increased by 1, 0 if no height change. */
85 if (node->left != NULL || node->right != NULL)
86 balance_diff = (child == node->right ? height_diff : -height_diff);
87 else
88 /* Special case where above formula doesn't work, because the caller
89 didn't tell whether node's left or right branch shrunk from height 1
90 to NULL. */
91 balance_diff = - previous_balance;
92
93 node->balance += balance_diff;
94 if (balance_diff == previous_balance)
95 {
96 /* node->balance is outside the range [-1,1]. Must rotate. */
97 NODE_T *nodep;
98
99 if (node->parent == NULL)
100 /* node == container->root */
101 nodep = &container->root;
102 else if (node->parent->left == node)
103 nodep = &node->parent->left;
104 else if (node->parent->right == node)
105 nodep = &node->parent->right;
106 else
107 abort ();
108
109 nodeleft = node->left;
110 noderight = node->right;
111
112 if (balance_diff < 0)
113 {
114 /* node->balance = -2. The subtree is heavier on the left side.
115 Rotate from left to right:
116
117 *
118 / \
119 h+2 h
120 */
121 NODE_T nodeleftright = nodeleft->right;
122 if (nodeleft->balance <= 0)
123 {
124 /*
125 * h+2|h+3
126 / \ / \
127 h+2 h --> / h+1|h+2
128 / \ | / \
129 h+1 h|h+1 h+1 h|h+1 h
130 */
131 node->left = nodeleftright;
132 nodeleft->right = node;
133
134 nodeleft->parent = node->parent;
135 node->parent = nodeleft;
136 if (nodeleftright != NULL)
137 nodeleftright->parent = node;
138
139 nodeleft->balance += 1;
140 node->balance = - nodeleft->balance;
141
142 *nodep = nodeleft;
143 height_diff = (height_diff < 0
144 ? /* noderight's height had been decremented from
145 h+1 to h. The subtree's height changes from
146 h+3 to h+2|h+3. */
147 nodeleft->balance - 1
148 : /* nodeleft's height had been incremented from
149 h+1 to h+2. The subtree's height changes from
150 h+2 to h+2|h+3. */
151 nodeleft->balance);
152 }
153 else
154 {
155 /*
156 * h+2
157 / \ / \
158 h+2 h --> h+1 h+1
159 / \ / \ / \
160 h h+1 h L R h
161 / \
162 L R
163
164 */
165 NODE_T L = nodeleft->right = nodeleftright->left;
166 NODE_T R = node->left = nodeleftright->right;
167 nodeleftright->left = nodeleft;
168 nodeleftright->right = node;
169
170 nodeleftright->parent = node->parent;
171 if (L != NULL)
172 L->parent = nodeleft;
173 if (R != NULL)
174 R->parent = node;
175 nodeleft->parent = nodeleftright;
176 node->parent = nodeleftright;
177
178 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
179 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
180 nodeleftright->balance = 0;
181
182 *nodep = nodeleftright;
183 height_diff = (height_diff < 0
184 ? /* noderight's height had been decremented from
185 h+1 to h. The subtree's height changes from
186 h+3 to h+2. */
187 -1
188 : /* nodeleft's height had been incremented from
189 h+1 to h+2. The subtree's height changes from
190 h+2 to h+2. */
191 0);
192 }
193 }
194 else
195 {
196 /* node->balance = 2. The subtree is heavier on the right side.
197 Rotate from right to left:
198
199 *
200 / \
201 h h+2
202 */
203 NODE_T noderightleft = noderight->left;
204 if (noderight->balance >= 0)
205 {
206 /*
207 * h+2|h+3
208 / \ / \
209 h h+2 --> h+1|h+2 \
210 / \ / \ |
211 h|h+1 h+1 h h|h+1 h+1
212 */
213 node->right = noderightleft;
214 noderight->left = node;
215
216 noderight->parent = node->parent;
217 node->parent = noderight;
218 if (noderightleft != NULL)
219 noderightleft->parent = node;
220
221 noderight->balance -= 1;
222 node->balance = - noderight->balance;
223
224 *nodep = noderight;
225 height_diff = (height_diff < 0
226 ? /* nodeleft's height had been decremented from
227 h+1 to h. The subtree's height changes from
228 h+3 to h+2|h+3. */
229 - noderight->balance - 1
230 : /* noderight's height had been incremented from
231 h+1 to h+2. The subtree's height changes from
232 h+2 to h+2|h+3. */
233 - noderight->balance);
234 }
235 else
236 {
237 /*
238 * h+2
239 / \ / \
240 h h+2 --> h+1 h+1
241 / \ / \ / \
242 h+1 h h L R h
243 / \
244 L R
245
246 */
247 NODE_T L = node->right = noderightleft->left;
248 NODE_T R = noderight->left = noderightleft->right;
249 noderightleft->left = node;
250 noderightleft->right = noderight;
251
252 noderightleft->parent = node->parent;
253 if (L != NULL)
254 L->parent = node;
255 if (R != NULL)
256 R->parent = noderight;
257 node->parent = noderightleft;
258 noderight->parent = noderightleft;
259
260 node->balance = (noderightleft->balance > 0 ? -1 : 0);
261 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
262 noderightleft->balance = 0;
263
264 *nodep = noderightleft;
265 height_diff = (height_diff < 0
266 ? /* nodeleft's height had been decremented from
267 h+1 to h. The subtree's height changes from
268 h+3 to h+2. */
269 -1
270 : /* noderight's height had been incremented from
271 h+1 to h+2. The subtree's height changes from
272 h+2 to h+2. */
273 0);
274 }
275 }
276 node = *nodep;
277 }
278 else
279 {
280 /* No rotation needed. Only propagation of the height change to the
281 next higher level. */
282 if (height_diff < 0)
283 height_diff = (previous_balance == 0 ? 0 : -1);
284 else
285 height_diff = (node->balance == 0 ? 0 : 1);
286 }
287
288 if (height_diff == 0)
289 break;
290
291 parent = node->parent;
292 if (parent == NULL)
293 break;
294 }
295 }
296
297 static NODE_T
298 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
299 {
300 /* Create new node. */
301 NODE_T new_node =
302 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
303
304 if (new_node == NULL)
305 return NULL;
306
307 new_node->left = NULL;
308 new_node->right = NULL;
309 new_node->balance = 0;
310 NODE_PAYLOAD_ASSIGN(new_node)
311
312 /* Add it to the tree. */
313 if (container->root == NULL)
314 {
315 container->root = new_node;
316 new_node->parent = NULL;
317 }
318 else
319 {
320 NODE_T node;
321
322 for (node = container->root; node->left != NULL; )
323 node = node->left;
324
325 node->left = new_node;
326 new_node->parent = node;
327 node->balance--;
328
329 /* Rebalance. */
330 if (node->right == NULL && node->parent != NULL)
331 rebalance (container, node, 1, node->parent);
332 }
333
334 container->count++;
335 return new_node;
336 }
337
338 /* Adds the already allocated NEW_NODE to the tree, right before NODE. */
339 static void
340 gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node)
341 {
342 bool height_inc;
343
344 new_node->left = NULL;
345 new_node->right = NULL;
346 new_node->balance = 0;
347
348 /* Add it to the tree. */
349 if (node->left == NULL)
350 {
351 node->left = new_node;
352 node->balance--;
353 height_inc = (node->right == NULL);
354 }
355 else
356 {
357 for (node = node->left; node->right != NULL; )
358 node = node->right;
359 node->right = new_node;
360 node->balance++;
361 height_inc = (node->left == NULL);
362 }
363 new_node->parent = node;
364
365 /* Rebalance. */
366 if (height_inc && node->parent != NULL)
367 rebalance (container, node, 1, node->parent);
368
369 container->count++;
370 }
371
372 static NODE_T
373 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
374 {
375 /* Create new node. */
376 NODE_T new_node =
377 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
378
379 if (new_node == NULL)
380 return NULL;
381
382 NODE_PAYLOAD_ASSIGN(new_node)
383
384 gl_tree_add_node_before (container, node, new_node);
385 return new_node;
386 }
387
388 /* Adds the already allocated NEW_NODE to the tree, right after NODE. */
389 static void
390 gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node)
391 {
392 bool height_inc;
393
394 new_node->left = NULL;
395 new_node->right = NULL;
396 new_node->balance = 0;
397
398 /* Add it to the tree. */
399 if (node->right == NULL)
400 {
401 node->right = new_node;
402 node->balance++;
403 height_inc = (node->left == NULL);
404 }
405 else
406 {
407 for (node = node->right; node->left != NULL; )
408 node = node->left;
409 node->left = new_node;
410 node->balance--;
411 height_inc = (node->right == NULL);
412 }
413 new_node->parent = node;
414
415 /* Rebalance. */
416 if (height_inc && node->parent != NULL)
417 rebalance (container, node, 1, node->parent);
418
419 container->count++;
420 }
421
422 static NODE_T
423 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
424 {
425 /* Create new node. */
426 NODE_T new_node =
427 (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
428
429 if (new_node == NULL)
430 return NULL;
431
432 NODE_PAYLOAD_ASSIGN(new_node)
433
434 gl_tree_add_node_after (container, node, new_node);
435 return new_node;
436 }
437
438 static void
439 gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node)
440 {
441 NODE_T parent = node->parent;
442
443 if (node->left == NULL)
444 {
445 /* Replace node with node->right. */
446 NODE_T child = node->right;
447
448 if (child != NULL)
449 child->parent = parent;
450 if (parent == NULL)
451 container->root = child;
452 else
453 {
454 if (parent->left == node)
455 parent->left = child;
456 else /* parent->right == node */
457 parent->right = child;
458
459 rebalance (container, child, -1, parent);
460 }
461 }
462 else if (node->right == NULL)
463 {
464 /* It is not absolutely necessary to treat this case. But the more
465 general case below is more complicated, hence slower. */
466 /* Replace node with node->left. */
467 NODE_T child = node->left;
468
469 child->parent = parent;
470 if (parent == NULL)
471 container->root = child;
472 else
473 {
474 if (parent->left == node)
475 parent->left = child;
476 else /* parent->right == node */
477 parent->right = child;
478
479 rebalance (container, child, -1, parent);
480 }
481 }
482 else
483 {
484 /* Replace node with the rightmost element of the node->left subtree. */
485 NODE_T subst;
486 NODE_T subst_parent;
487 NODE_T child;
488
489 for (subst = node->left; subst->right != NULL; )
490 subst = subst->right;
491
492 subst_parent = subst->parent;
493
494 child = subst->left;
495
496 /* The case subst_parent == node is special: If we do nothing special,
497 we get confusion about node->left, subst->left and child->parent.
498 subst_parent == node
499 <==> The 'for' loop above terminated immediately.
500 <==> subst == subst_parent->left
501 [otherwise subst == subst_parent->right]
502 In this case, we would need to first set
503 child->parent = node; node->left = child;
504 and later - when we copy subst into node's position - again
505 child->parent = subst; subst->left = child;
506 Altogether a no-op. */
507 if (subst_parent != node)
508 {
509 if (child != NULL)
510 child->parent = subst_parent;
511 subst_parent->right = child;
512 }
513
514 /* Copy subst into node's position.
515 (This is safer than to copy subst's value into node, keep node in
516 place, and free subst.) */
517 if (subst_parent != node)
518 {
519 subst->left = node->left;
520 subst->left->parent = subst;
521 }
522 subst->right = node->right;
523 subst->right->parent = subst;
524 subst->balance = node->balance;
525 subst->parent = parent;
526 if (parent == NULL)
527 container->root = subst;
528 else if (parent->left == node)
529 parent->left = subst;
530 else /* parent->right == node */
531 parent->right = subst;
532
533 /* Rebalancing starts at child's parent, that is subst_parent -
534 except when subst_parent == node. In this case, we need to use
535 its replacement, subst. */
536 rebalance (container, child, -1, subst_parent != node ? subst_parent : subst);
537 }
538
539 container->count--;
540 }
541
542 static bool
543 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
544 {
545 gl_tree_remove_node_no_free (container, node);
546 NODE_PAYLOAD_DISPOSE (container, node)
547 free (node);
548 return true;
549 }
550
551 /* For debugging. */
552 static unsigned int
553 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
554 {
555 unsigned int left_height =
556 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
557 unsigned int right_height =
558 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
559 int balance = (int)right_height - (int)left_height;
560
561 if (!(node->parent == parent))
562 abort ();
563 if (!(balance >= -1 && balance <= 1))
564 abort ();
565 if (!(node->balance == balance))
566 abort ();
567
568 (*counterp)++;
569
570 return 1 + (left_height > right_height ? left_height : right_height);
571 }