From e4f9d811684011d8a67e363827de39d5f2d3ae5a Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Sat, 5 Dec 2015 21:02:34 +0100 Subject: [PATCH] fix tdelete to properly balance the tree 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 86200928..08644607 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.25.1