diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index 12310d3fa771d528fabc5ac313f76d42ed71aef6..a9b3862c0ecf4ba5533d0676c3fcdc3d9363a141 100644 (file)
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
{
c_avl_node_t *root;
int (*compare) (const void *, const void *);
+ int size;
};
struct c_avl_iterator_s
c_avl_node_t *y;
c_avl_node_t *b;
+ assert (x != NULL);
+ assert (x->left != NULL);
+
p = x->parent;
y = x->left;
b = y->right;
y->height = calc_height (y);
return (y);
-} /* void rotate_left */
+} /* void rotate_right */
/*
* (x) (y)
c_avl_node_t *y;
c_avl_node_t *b;
+ assert (x != NULL);
+ assert (x->right != NULL);
+
p = x->parent;
y = x->right;
b = y->left;
{
assert (n->right != NULL);
b_bottom = BALANCE (n->right);
- assert ((b_bottom >= -1) || (b_bottom <= 1));
+ assert ((b_bottom >= -1) && (b_bottom <= 1));
if (b_bottom == 1)
n = rotate_right_left (t, n);
else
{
assert (n->left != NULL);
b_bottom = BALANCE (n->left);
- assert ((b_bottom >= -1) || (b_bottom <= 1));
+ assert ((b_bottom >= -1) && (b_bottom <= 1));
if (b_bottom == -1)
n = rotate_left_right (t, n);
else
t->root = NULL;
t->compare = compare;
+ t->size = 0;
return (t);
}
{
new->parent = NULL;
t->root = new;
+ t->size = 1;
return (0);
}
} /* while (42) */
verify_tree (t->root);
+ ++t->size;
return (0);
} /* int c_avl_insert */
status = _remove (t, n);
verify_tree (t->root);
+ --t->size;
return (status);
} /* void *c_avl_remove */
n = t->root;
while ((n->left != NULL) || (n->right != NULL))
{
- int height_left = (n->left == NULL) ? 0 : n->left->height;
- int height_right = (n->right == NULL) ? 0 : n->right->height;
+ if (n->left == NULL)
+ {
+ n = n->right;
+ continue;
+ }
+ else if (n->right == NULL)
+ {
+ n = n->left;
+ continue;
+ }
- if (height_left > height_right)
+ if (n->left->height > n->right->height)
n = n->left;
else
n = n->right;
*value = n->value;
free_node (n);
+ --t->size;
rebalance (t, p);
return (0);
{
free (iter);
}
+
+int c_avl_size (c_avl_tree_t *t)
+{
+ if (t == NULL)
+ return (0);
+ return (t->size);
+}