1 /* Ordered set data type implemented by a binary tree.
2 Copyright (C) 2006 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
22 #include "gl_avltree_oset.h"
28 /* An AVL tree is a binary tree where
29 1. The height of each node is calculated as
30 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
31 2. The heights of the subtrees of each node differ by at most 1:
32 | heightof(right) - heightof(left) | <= 1.
33 3. The index of the elements in the node.left subtree are smaller than
35 The index of the elements in the node.right subtree are larger than
39 /* -------------------------- gl_oset_t Data Type -------------------------- */
41 /* Tree node implementation, valid for this file only. */
42 struct gl_oset_node_impl
44 struct gl_oset_node_impl *left; /* left branch, or NULL */
45 struct gl_oset_node_impl *right; /* right branch, or NULL */
46 /* Parent pointer, or NULL. The parent pointer is not needed for most
47 operations. It is needed so that a gl_oset_node_t can be returned
48 without memory allocation, on which the functions gl_oset_remove_node,
49 gl_oset_add_before, gl_oset_add_after can be implemented. */
50 struct gl_oset_node_impl *parent;
51 int balance; /* heightof(right) - heightof(left),
52 always = -1 or 0 or 1 */
55 typedef struct gl_oset_node_impl * gl_oset_node_t;
57 /* Concrete gl_oset_impl type, valid for this file only. */
60 struct gl_oset_impl_base base;
61 struct gl_oset_node_impl *root; /* root node or NULL */
62 size_t count; /* number of nodes */
65 /* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
66 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would have
67 at least F_87 elements, and because even on 64-bit machines,
68 sizeof (gl_oset_node_impl) * F_87 > 2^64
69 this would exceed the address space of the machine. */
72 /* Ensure the tree is balanced, after an insertion or deletion operation.
73 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
74 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
75 Rotation operations are performed starting at PARENT (not NODE itself!). */
77 rebalance (gl_oset_t set,
78 gl_oset_node_t node, int height_diff, gl_oset_node_t parent)
85 gl_oset_node_t nodeleft;
86 gl_oset_node_t noderight;
91 previous_balance = node->balance;
93 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
94 branch's height has increased by 1 or the left branch's height has
95 decreased by 1, -1 if the right branch's height has decreased by 1 or
96 the left branch's height has increased by 1, 0 if no height change. */
97 if (node->left != NULL || node->right != NULL)
98 balance_diff = (child == node->right ? height_diff : -height_diff);
100 /* Special case where above formula doesn't work, because the caller
101 didn't tell whether node's left or right branch shrunk from height 1
103 balance_diff = - previous_balance;
105 node->balance += balance_diff;
106 if (balance_diff == previous_balance)
108 /* node->balance is outside the range [-1,1]. Must rotate. */
109 gl_oset_node_t *nodep;
111 if (node->parent == NULL)
112 /* node == set->root */
114 else if (node->parent->left == node)
115 nodep = &node->parent->left;
116 else if (node->parent->right == node)
117 nodep = &node->parent->right;
121 nodeleft = node->left;
122 noderight = node->right;
124 if (balance_diff < 0)
126 /* node->balance = -2. The subtree is heavier on the left side.
127 Rotate from left to right:
133 gl_oset_node_t nodeleftright = nodeleft->right;
134 if (nodeleft->balance <= 0)
141 h+1 h|h+1 h+1 h|h+1 h
143 node->left = nodeleftright;
144 nodeleft->right = node;
146 nodeleft->parent = node->parent;
147 node->parent = nodeleft;
148 if (nodeleftright != NULL)
149 nodeleftright->parent = node;
151 nodeleft->balance += 1;
152 node->balance = - nodeleft->balance;
155 height_diff = (height_diff < 0
156 ? /* noderight's height had been decremented from
157 h+1 to h. The subtree's height changes from
159 nodeleft->balance - 1
160 : /* nodeleft's height had been incremented from
161 h+1 to h+2. The subtree's height changes from
177 gl_oset_node_t L = nodeleft->right = nodeleftright->left;
178 gl_oset_node_t R = node->left = nodeleftright->right;
179 nodeleftright->left = nodeleft;
180 nodeleftright->right = node;
182 nodeleftright->parent = node->parent;
184 L->parent = nodeleft;
187 nodeleft->parent = nodeleftright;
188 node->parent = nodeleftright;
190 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
191 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
192 nodeleftright->balance = 0;
194 *nodep = nodeleftright;
195 height_diff = (height_diff < 0
196 ? /* noderight's height had been decremented from
197 h+1 to h. The subtree's height changes from
200 : /* nodeleft's height had been incremented from
201 h+1 to h+2. The subtree's height changes from
208 /* node->balance = 2. The subtree is heavier on the right side.
209 Rotate from right to left:
215 gl_oset_node_t noderightleft = noderight->left;
216 if (noderight->balance >= 0)
223 h|h+1 h+1 h h|h+1 h+1
225 node->right = noderightleft;
226 noderight->left = node;
228 noderight->parent = node->parent;
229 node->parent = noderight;
230 if (noderightleft != NULL)
231 noderightleft->parent = node;
233 noderight->balance -= 1;
234 node->balance = - noderight->balance;
237 height_diff = (height_diff < 0
238 ? /* nodeleft's height had been decremented from
239 h+1 to h. The subtree's height changes from
241 - noderight->balance - 1
242 : /* noderight's height had been incremented from
243 h+1 to h+2. The subtree's height changes from
245 - noderight->balance);
259 gl_oset_node_t L = node->right = noderightleft->left;
260 gl_oset_node_t R = noderight->left = noderightleft->right;
261 noderightleft->left = node;
262 noderightleft->right = noderight;
264 noderightleft->parent = node->parent;
268 R->parent = noderight;
269 node->parent = noderightleft;
270 noderight->parent = noderightleft;
272 node->balance = (noderightleft->balance > 0 ? -1 : 0);
273 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
274 noderightleft->balance = 0;
276 *nodep = noderightleft;
277 height_diff = (height_diff < 0
278 ? /* nodeleft's height had been decremented from
279 h+1 to h. The subtree's height changes from
282 : /* noderight's height had been incremented from
283 h+1 to h+2. The subtree's height changes from
292 /* No rotation needed. Only propagation of the height change to the
293 next higher level. */
295 height_diff = (previous_balance == 0 ? 0 : -1);
297 height_diff = (node->balance == 0 ? 0 : 1);
300 if (height_diff == 0)
303 parent = node->parent;
309 static gl_oset_node_t
310 gl_tree_add_first (gl_oset_t set, const void *elt)
312 /* Create new node. */
313 gl_oset_node_t new_node =
314 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
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_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 *) xmalloc (sizeof (struct gl_oset_node_impl));
355 new_node->left = NULL;
356 new_node->right = NULL;
357 new_node->balance = 0;
358 new_node->value = elt;
360 /* Add it to the tree. */
361 if (node->left == NULL)
363 node->left = new_node;
365 height_inc = (node->right == NULL);
369 for (node = node->left; node->right != NULL; )
371 node->right = new_node;
373 height_inc = (node->left == NULL);
375 new_node->parent = node;
378 if (height_inc && node->parent != NULL)
379 rebalance (set, node, 1, node->parent);
385 static gl_oset_node_t
386 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
388 /* Create new node. */
389 gl_oset_node_t new_node =
390 (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
393 new_node->left = NULL;
394 new_node->right = NULL;
395 new_node->balance = 0;
396 new_node->value = elt;
398 /* Add it to the tree. */
399 if (node->right == NULL)
401 node->right = new_node;
403 height_inc = (node->left == NULL);
407 for (node = node->right; node->left != NULL; )
409 node->left = new_node;
411 height_inc = (node->right == NULL);
413 new_node->parent = node;
416 if (height_inc && node->parent != NULL)
417 rebalance (set, node, 1, node->parent);
424 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
426 gl_oset_node_t parent = node->parent;
428 if (node->left == NULL)
430 /* Replace node with node->right. */
431 gl_oset_node_t child = node->right;
434 child->parent = parent;
439 if (parent->left == node)
440 parent->left = child;
441 else /* parent->right == node */
442 parent->right = child;
444 rebalance (set, child, -1, parent);
447 else if (node->right == NULL)
449 /* It is not absolutely necessary to treat this case. But the more
450 general case below is more complicated, hence slower. */
451 /* Replace node with node->left. */
452 gl_oset_node_t child = node->left;
454 child->parent = parent;
459 if (parent->left == node)
460 parent->left = child;
461 else /* parent->right == node */
462 parent->right = child;
464 rebalance (set, child, -1, parent);
469 /* Replace node with the rightmost element of the node->left subtree. */
470 gl_oset_node_t subst;
471 gl_oset_node_t subst_parent;
472 gl_oset_node_t child;
474 for (subst = node->left; subst->right != NULL; )
475 subst = subst->right;
477 subst_parent = subst->parent;
481 /* The case subst_parent == node is special: If we do nothing special,
482 we get confusion about node->left, subst->left and child->parent.
484 <==> The 'for' loop above terminated immediately.
485 <==> subst == subst_parent->left
486 [otherwise subst == subst_parent->right]
487 In this case, we would need to first set
488 child->parent = node; node->left = child;
489 and later - when we copy subst into node's position - again
490 child->parent = subst; subst->left = child;
491 Altogether a no-op. */
492 if (subst_parent != node)
495 child->parent = subst_parent;
496 subst_parent->right = child;
499 /* Copy subst into node's position.
500 (This is safer than to copy subst's value into node, keep node in
501 place, and free subst.) */
502 if (subst_parent != node)
504 subst->left = node->left;
505 subst->left->parent = subst;
507 subst->right = node->right;
508 subst->right->parent = subst;
509 subst->balance = node->balance;
510 subst->parent = parent;
513 else if (parent->left == node)
514 parent->left = subst;
515 else /* parent->right == node */
516 parent->right = subst;
518 /* Rebalancing starts at child's parent, that is subst_parent -
519 except when subst_parent == node. In this case, we need to use
520 its replacement, subst. */
521 rebalance (set, child, -1, subst_parent != node ? subst_parent : subst);
529 /* Generic binary tree code. */
530 #include "gl_anytree_oset.h"
534 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
536 unsigned int left_height =
537 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
538 unsigned int right_height =
539 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
540 int balance = (int)right_height - (int)left_height;
542 if (!(node->parent == parent))
544 if (!(balance >= -1 && balance <= 1))
546 if (!(node->balance == balance))
551 return 1 + (left_height > right_height ? left_height : right_height);
554 gl_avltree_oset_check_invariants (gl_oset_t set)
557 if (set->root != NULL)
558 check_invariants (set->root, NULL, &counter);
559 if (!(set->count == counter))
563 const struct gl_oset_implementation gl_avltree_oset_implementation =
565 gl_tree_create_empty,
568 gl_tree_search_atleast,
573 gl_tree_iterator_next,
574 gl_tree_iterator_free