summaryrefslogtreecommitdiff
path: root/src/search/tsearch_avl.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/search/tsearch_avl.c')
-rw-r--r--src/search/tsearch_avl.c19
1 files 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;
}