summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2019-01-12 19:20:52 +0100
committerDavid Robillard <d@drobilla.net>2019-01-12 19:20:52 +0100
commit9d60178afeea839b51a04ae4429e946515005da4 (patch)
tree0f2750f77d48b9410ea23d961603d55ef8346f83
parent8489a1a91e254f8bc987c2a5b65791dee1120c5c (diff)
downloadzix-9d60178afeea839b51a04ae4429e946515005da4.tar.gz
zix-9d60178afeea839b51a04ae4429e946515005da4.tar.bz2
zix-9d60178afeea839b51a04ae4429e946515005da4.zip
Improve zix_btree_remove()
-rw-r--r--zix/btree.c15
1 files changed, 10 insertions, 5 deletions
diff --git a/zix/btree.c b/zix/btree.c
index 69e7575..03f0aa9 100644
--- a/zix/btree.c
+++ b/zix/btree.c
@@ -526,21 +526,26 @@ zix_btree_remove(ZixBTree* const t,
}
} else if (equal) {
// Found in internal node
- if (!zix_btree_node_is_minimal(n->children[i])) {
+ const size_t l_size = n->children[i]->n_vals;
+ const size_t r_size = n->children[i + 1]->n_vals;
+ if (zix_btree_node_is_minimal(n->children[i]) &&
+ zix_btree_node_is_minimal(n->children[i + 1])) {
+ // Both preceding and succeeding child are minimal
+ n = zix_btree_merge(t, n, i);
+ } else if (l_size >= r_size) {
// Left child can remove without merge
+ assert(!zix_btree_node_is_minimal(n->children[i]));
*out = n->vals[i];
n->vals[i] = zix_btree_remove_max(t, n->children[i]);
--t->size;
return ZIX_STATUS_SUCCESS;
- } else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
+ } else {
// Right child can remove without merge
+ assert(!zix_btree_node_is_minimal(n->children[i + 1]));
*out = n->vals[i];
n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
--t->size;
return ZIX_STATUS_SUCCESS;
- } else {
- // Both preceding and succeeding child are minimal
- n = zix_btree_merge(t, n, i);
}
} else {
// Not found in internal node, key is in/under children[i]