[PATCH 1/3] fix tdelete to properly balance the tree

[PATCH 1/3] fix tdelete to properly balance the tree

[Szabolcs Nagy]

the tsearch data structure is an avl tree, but it did not implement
the deletion operation correctly so the tree could become unbalanced.

reported by Ed Schouten.
---
 src/search/tsearch_avl.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
index 8620092..0864460 100644
--- a/src/search/tsearch_avl.c
+++ b/src/search/tsearch_avl.c
@@ -105,10 +105,13 @@ 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);
+static struct node *remove_rightmost(struct node *n, struct node **rightmost)
+{
+	if (!n->right) {
+		*rightmost = n;
+		return n->left;
+	}
+	n->right = remove_rightmost(n->right, rightmost);
 	return balance(n);
 }
 
@@ -122,7 +125,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) {
+			r->left = remove_rightmost(r->left, n);
+			(*n)->left = r->left;
+			(*n)->right = r->right;
+			*n = balance(*n);
+		} else
+			*n = r->right;
 		free(r);
 		return parent;
 	}
-- 
2.4.1