1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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.
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.
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/>. */
21 #include "gl_avltree_oset.h"
25 /* An AVL tree is a binary tree where
26 1. The height of each node is calculated as
27 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
28 2. The heights of the subtrees of each node differ by at most 1:
29 | heightof(right) - heightof(left) | <= 1.
30 3. The index of the elements in the node.left subtree are smaller than
32 The index of the elements in the node.right subtree are larger than
36 /* -------------------------- gl_oset_t Data Type -------------------------- */
38 /* Tree node implementation, valid for this file only. */
39 struct gl_oset_node_impl
41 struct gl_oset_node_impl
*left
; /* left branch, or NULL */
42 struct gl_oset_node_impl
*right
; /* right branch, or NULL */
43 /* Parent pointer, or NULL. The parent pointer is not needed for most
44 operations. It is needed so that a gl_oset_node_t can be returned
45 without memory allocation, on which the functions gl_oset_remove_node,
46 gl_oset_add_before, gl_oset_add_after can be implemented. */
47 struct gl_oset_node_impl
*parent
;
48 int balance
; /* heightof(right) - heightof(left),
49 always = -1 or 0 or 1 */
52 typedef struct gl_oset_node_impl
* gl_oset_node_t
;
54 /* Concrete gl_oset_impl type, valid for this file only. */
57 struct gl_oset_impl_base base
;
58 struct gl_oset_node_impl
*root
; /* root node or NULL */
59 size_t count
; /* number of nodes */
62 /* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
63 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would have
64 at least F_87 elements, and because even on 64-bit machines,
65 sizeof (gl_oset_node_impl) * F_87 > 2^64
66 this would exceed the address space of the machine. */
69 /* Ensure the tree is balanced, after an insertion or deletion operation.
70 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
71 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
72 Rotation operations are performed starting at PARENT (not NODE itself!). */
74 rebalance (gl_oset_t set
,
75 gl_oset_node_t node
, int height_diff
, gl_oset_node_t parent
)
82 gl_oset_node_t nodeleft
;
83 gl_oset_node_t noderight
;
88 previous_balance
= node
->balance
;
90 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
91 branch's height has increased by 1 or the left branch's height has
92 decreased by 1, -1 if the right branch's height has decreased by 1 or
93 the left branch's height has increased by 1, 0 if no height change. */
94 if (node
->left
!= NULL
|| node
->right
!= NULL
)
95 balance_diff
= (child
== node
->right
? height_diff
: -height_diff
);
97 /* Special case where above formula doesn't work, because the caller
98 didn't tell whether node's left or right branch shrunk from height 1
100 balance_diff
= - previous_balance
;
102 node
->balance
+= balance_diff
;
103 if (balance_diff
== previous_balance
)
105 /* node->balance is outside the range [-1,1]. Must rotate. */
106 gl_oset_node_t
*nodep
;
108 if (node
->parent
== NULL
)
109 /* node == set->root */
111 else if (node
->parent
->left
== node
)
112 nodep
= &node
->parent
->left
;
113 else if (node
->parent
->right
== node
)
114 nodep
= &node
->parent
->right
;
118 nodeleft
= node
->left
;
119 noderight
= node
->right
;
121 if (balance_diff
< 0)
123 /* node->balance = -2. The subtree is heavier on the left side.
124 Rotate from left to right:
130 gl_oset_node_t nodeleftright
= nodeleft
->right
;
131 if (nodeleft
->balance
<= 0)
138 h+1 h|h+1 h+1 h|h+1 h
140 node
->left
= nodeleftright
;
141 nodeleft
->right
= node
;
143 nodeleft
->parent
= node
->parent
;
144 node
->parent
= nodeleft
;
145 if (nodeleftright
!= NULL
)
146 nodeleftright
->parent
= node
;
148 nodeleft
->balance
+= 1;
149 node
->balance
= - nodeleft
->balance
;
152 height_diff
= (height_diff
< 0
153 ? /* noderight's height had been decremented from
154 h+1 to h. The subtree's height changes from
156 nodeleft
->balance
- 1
157 : /* nodeleft's height had been incremented from
158 h+1 to h+2. The subtree's height changes from
174 gl_oset_node_t L
= nodeleft
->right
= nodeleftright
->left
;
175 gl_oset_node_t R
= node
->left
= nodeleftright
->right
;
176 nodeleftright
->left
= nodeleft
;
177 nodeleftright
->right
= node
;
179 nodeleftright
->parent
= node
->parent
;
181 L
->parent
= nodeleft
;
184 nodeleft
->parent
= nodeleftright
;
185 node
->parent
= nodeleftright
;
187 nodeleft
->balance
= (nodeleftright
->balance
> 0 ? -1 : 0);
188 node
->balance
= (nodeleftright
->balance
< 0 ? 1 : 0);
189 nodeleftright
->balance
= 0;
191 *nodep
= nodeleftright
;
192 height_diff
= (height_diff
< 0
193 ? /* noderight's height had been decremented from
194 h+1 to h. The subtree's height changes from
197 : /* nodeleft's height had been incremented from
198 h+1 to h+2. The subtree's height changes from
205 /* node->balance = 2. The subtree is heavier on the right side.
206 Rotate from right to left:
212 gl_oset_node_t noderightleft
= noderight
->left
;
213 if (noderight
->balance
>= 0)
220 h|h+1 h+1 h h|h+1 h+1
222 node
->right
= noderightleft
;
223 noderight
->left
= node
;
225 noderight
->parent
= node
->parent
;
226 node
->parent
= noderight
;
227 if (noderightleft
!= NULL
)
228 noderightleft
->parent
= node
;
230 noderight
->balance
-= 1;
231 node
->balance
= - noderight
->balance
;
234 height_diff
= (height_diff
< 0
235 ? /* nodeleft's height had been decremented from
236 h+1 to h. The subtree's height changes from
238 - noderight
->balance
- 1
239 : /* noderight's height had been incremented from
240 h+1 to h+2. The subtree's height changes from
242 - noderight
->balance
);
256 gl_oset_node_t L
= node
->right
= noderightleft
->left
;
257 gl_oset_node_t R
= noderight
->left
= noderightleft
->right
;
258 noderightleft
->left
= node
;
259 noderightleft
->right
= noderight
;
261 noderightleft
->parent
= node
->parent
;
265 R
->parent
= noderight
;
266 node
->parent
= noderightleft
;
267 noderight
->parent
= noderightleft
;
269 node
->balance
= (noderightleft
->balance
> 0 ? -1 : 0);
270 noderight
->balance
= (noderightleft
->balance
< 0 ? 1 : 0);
271 noderightleft
->balance
= 0;
273 *nodep
= noderightleft
;
274 height_diff
= (height_diff
< 0
275 ? /* nodeleft's height had been decremented from
276 h+1 to h. The subtree's height changes from
279 : /* noderight's height had been incremented from
280 h+1 to h+2. The subtree's height changes from
289 /* No rotation needed. Only propagation of the height change to the
290 next higher level. */
292 height_diff
= (previous_balance
== 0 ? 0 : -1);
294 height_diff
= (node
->balance
== 0 ? 0 : 1);
297 if (height_diff
== 0)
300 parent
= node
->parent
;
306 static gl_oset_node_t
307 gl_tree_nx_add_first (gl_oset_t set
, const void *elt
)
309 /* Create new node. */
310 gl_oset_node_t new_node
=
311 (struct gl_oset_node_impl
*) malloc (sizeof (struct gl_oset_node_impl
));
313 if (new_node
== NULL
)
316 new_node
->left
= NULL
;
317 new_node
->right
= NULL
;
318 new_node
->balance
= 0;
319 new_node
->value
= elt
;
321 /* Add it to the tree. */
322 if (set
->root
== NULL
)
324 set
->root
= new_node
;
325 new_node
->parent
= NULL
;
331 for (node
= set
->root
; node
->left
!= NULL
; )
334 node
->left
= new_node
;
335 new_node
->parent
= node
;
339 if (node
->right
== NULL
&& node
->parent
!= NULL
)
340 rebalance (set
, node
, 1, node
->parent
);
347 static gl_oset_node_t
348 gl_tree_nx_add_before (gl_oset_t set
, gl_oset_node_t node
, const void *elt
)
350 /* Create new node. */
351 gl_oset_node_t new_node
=
352 (struct gl_oset_node_impl
*) malloc (sizeof (struct gl_oset_node_impl
));
355 if (new_node
== NULL
)
358 new_node
->left
= NULL
;
359 new_node
->right
= NULL
;
360 new_node
->balance
= 0;
361 new_node
->value
= elt
;
363 /* Add it to the tree. */
364 if (node
->left
== NULL
)
366 node
->left
= new_node
;
368 height_inc
= (node
->right
== NULL
);
372 for (node
= node
->left
; node
->right
!= NULL
; )
374 node
->right
= new_node
;
376 height_inc
= (node
->left
== NULL
);
378 new_node
->parent
= node
;
381 if (height_inc
&& node
->parent
!= NULL
)
382 rebalance (set
, node
, 1, node
->parent
);
388 static gl_oset_node_t
389 gl_tree_nx_add_after (gl_oset_t set
, gl_oset_node_t node
, const void *elt
)
391 /* Create new node. */
392 gl_oset_node_t new_node
=
393 (struct gl_oset_node_impl
*) malloc (sizeof (struct gl_oset_node_impl
));
396 if (new_node
== NULL
)
399 new_node
->left
= NULL
;
400 new_node
->right
= NULL
;
401 new_node
->balance
= 0;
402 new_node
->value
= elt
;
404 /* Add it to the tree. */
405 if (node
->right
== NULL
)
407 node
->right
= new_node
;
409 height_inc
= (node
->left
== NULL
);
413 for (node
= node
->right
; node
->left
!= NULL
; )
415 node
->left
= new_node
;
417 height_inc
= (node
->right
== NULL
);
419 new_node
->parent
= node
;
422 if (height_inc
&& node
->parent
!= NULL
)
423 rebalance (set
, node
, 1, node
->parent
);
430 gl_tree_remove_node (gl_oset_t set
, gl_oset_node_t node
)
432 gl_oset_node_t parent
= node
->parent
;
434 if (node
->left
== NULL
)
436 /* Replace node with node->right. */
437 gl_oset_node_t child
= node
->right
;
440 child
->parent
= parent
;
445 if (parent
->left
== node
)
446 parent
->left
= child
;
447 else /* parent->right == node */
448 parent
->right
= child
;
450 rebalance (set
, child
, -1, parent
);
453 else if (node
->right
== NULL
)
455 /* It is not absolutely necessary to treat this case. But the more
456 general case below is more complicated, hence slower. */
457 /* Replace node with node->left. */
458 gl_oset_node_t child
= node
->left
;
460 child
->parent
= parent
;
465 if (parent
->left
== node
)
466 parent
->left
= child
;
467 else /* parent->right == node */
468 parent
->right
= child
;
470 rebalance (set
, child
, -1, parent
);
475 /* Replace node with the rightmost element of the node->left subtree. */
476 gl_oset_node_t subst
;
477 gl_oset_node_t subst_parent
;
478 gl_oset_node_t child
;
480 for (subst
= node
->left
; subst
->right
!= NULL
; )
481 subst
= subst
->right
;
483 subst_parent
= subst
->parent
;
487 /* The case subst_parent == node is special: If we do nothing special,
488 we get confusion about node->left, subst->left and child->parent.
490 <==> The 'for' loop above terminated immediately.
491 <==> subst == subst_parent->left
492 [otherwise subst == subst_parent->right]
493 In this case, we would need to first set
494 child->parent = node; node->left = child;
495 and later - when we copy subst into node's position - again
496 child->parent = subst; subst->left = child;
497 Altogether a no-op. */
498 if (subst_parent
!= node
)
501 child
->parent
= subst_parent
;
502 subst_parent
->right
= child
;
505 /* Copy subst into node's position.
506 (This is safer than to copy subst's value into node, keep node in
507 place, and free subst.) */
508 if (subst_parent
!= node
)
510 subst
->left
= node
->left
;
511 subst
->left
->parent
= subst
;
513 subst
->right
= node
->right
;
514 subst
->right
->parent
= subst
;
515 subst
->balance
= node
->balance
;
516 subst
->parent
= parent
;
519 else if (parent
->left
== node
)
520 parent
->left
= subst
;
521 else /* parent->right == node */
522 parent
->right
= subst
;
524 /* Rebalancing starts at child's parent, that is subst_parent -
525 except when subst_parent == node. In this case, we need to use
526 its replacement, subst. */
527 rebalance (set
, child
, -1, subst_parent
!= node
? subst_parent
: subst
);
531 if (set
->base
.dispose_fn
!= NULL
)
532 set
->base
.dispose_fn (node
->value
);
537 /* Generic binary tree code. */
538 #include "gl_anytree_oset.h"
542 check_invariants (gl_oset_node_t node
, gl_oset_node_t parent
, size_t *counterp
)
544 unsigned int left_height
=
545 (node
->left
!= NULL
? check_invariants (node
->left
, node
, counterp
) : 0);
546 unsigned int right_height
=
547 (node
->right
!= NULL
? check_invariants (node
->right
, node
, counterp
) : 0);
548 int balance
= (int)right_height
- (int)left_height
;
550 if (!(node
->parent
== parent
))
552 if (!(balance
>= -1 && balance
<= 1))
554 if (!(node
->balance
== balance
))
559 return 1 + (left_height
> right_height
? left_height
: right_height
);
562 gl_avltree_oset_check_invariants (gl_oset_t set
)
565 if (set
->root
!= NULL
)
566 check_invariants (set
->root
, NULL
, &counter
);
567 if (!(set
->count
== counter
))
571 const struct gl_oset_implementation gl_avltree_oset_implementation
=
573 gl_tree_nx_create_empty
,
576 gl_tree_search_atleast
,
581 gl_tree_iterator_next
,
582 gl_tree_iterator_free