tdelete() may break the AVL tree balance property?

tdelete() may break the AVL tree balance property?

[Ed Schouten]

Hi there,

If my interpretation of tsearch_avl.c is correct, it seems to be the
case that the implementation of tdelete() is different from how
removal of nodes in AVL trees is described in literature.

It looks as if the removal of a node in the middle of a tree is
implemented by attaching its right subtree to the rightmost node of
the left subtree (its predecessor) through the movr() function. Though
this maintains order correctly, the problem with this approach is that
it yields trees that have an absolute balance factor greater than 2.
As far as I know, the rotation operations are not sufficient to
rebalance in those situations.

The conventional approach of implementing deletion is not by attaching
the two subtrees to another, but by completely extracting the
predecessor from the left subtree. This predecessor can then be used
to join both subtrees together, as shown in this image:

https://en.wikipedia.org/wiki/AVL_tree#/media/File:Binary_search_tree_delete.svg

As the left subtree has its height decreased by at most one, the
absolute balance factor should be at most 2, meaning that rebalancing
should always be possible.

Best regards,
-- 
Ed Schouten <ed@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717

Re: tdelete() may break the AVL tree balance property?

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 1412 bytes --]

* Ed Schouten <ed@nuxi.nl> [2015-12-04 23:55:30 +0100]:
> If my interpretation of tsearch_avl.c is correct, it seems to be the
> case that the implementation of tdelete() is different from how
> removal of nodes in AVL trees is described in literature.
> 
> It looks as if the removal of a node in the middle of a tree is
> implemented by attaching its right subtree to the rightmost node of
> the left subtree (its predecessor) through the movr() function. Though
> this maintains order correctly, the problem with this approach is that
> it yields trees that have an absolute balance factor greater than 2.
> As far as I know, the rotation operations are not sufficient to
> rebalance in those situations.
> 

thanks for the report
yes it's wrong (this code is from me)
i attached a fix, but i'll have to
look at it again tomorrow in case
there is a better approach.

> The conventional approach of implementing deletion is not by attaching
> the two subtrees to another, but by completely extracting the
> predecessor from the left subtree. This predecessor can then be used
> to join both subtrees together, as shown in this image:
> 
> https://en.wikipedia.org/wiki/AVL_tree#/media/File:Binary_search_tree_delete.svg
> 
> As the left subtree has its height decreased by at most one, the
> absolute balance factor should be at most 2, meaning that rebalancing
> should always be possible.
> 
> Best regards,

[-- Attachment #2: avl.diff --]
[-- Type: text/x-diff, Size: 1048 bytes --]

diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 8620092..e53cf32 100644
--- a/src/search/tsearch_avl.c
+++ b/src/search/tsearch_avl.c
@@ -105,11 +105,17 @@ static struct node *insert(struct node **n, const void *k,
 	return r;
 }
 
-static struct node *movr(struct node *n, struct node *r) {
-	if (!n)
-		return r;
-	n->right = movr(n->right, r);
-	return balance(n);
+static struct node *poprightmost(struct node **p, struct node *n)
+{
+	struct node *r;
+
+	if (!n->right) {
+		*p = n->left;
+		return n;
+	}
+	r = poprightmost(&n->right, n->right);
+	*p = balance(n);
+	return r;
 }
 
 static struct node *remove(struct node **n, const void *k,
@@ -122,7 +128,13 @@ static struct node *remove(struct node **n, const void *k,
 	c = cmp(k, (*n)->key);
 	if (c == 0) {
 		struct node *r = *n;
-		*n = movr(r->left, r->right);
+		if (r->left) {
+			*n = poprightmost(&r->left, r->left);
+			(*n)->left = r->left;
+			(*n)->right = r->right;
+			*n = balance(*n);
+		} else
+			*n = r->right;
 		free(r);
 		return parent;
 	}

Re: tdelete() may break the AVL tree balance property?

[Ed Schouten]

Hi Szabolcs,

2015-12-05 4:19 GMT+01:00 Szabolcs Nagy <nsz@port70.net>:
> thanks for the report
> yes it's wrong (this code is from me)
> i attached a fix, but i'll have to
> look at it again tomorrow in case
> there is a better approach.

Though I haven't tested the patch personally, I think that is the
correct way to solve it indeed.

By the way, it should be possible to easily detect these kinds of
imbalances by looking at the value by delta(). It should always be
between [-2, +2]. I don't know what musl's policy on assertions is,
but it may be worth adding such a check to prevent this from
regressing.

Thanks,
-- 
Ed Schouten <ed@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717