1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2013 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 <http://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