Mercurial > libjeffpc
changeset 506:40b86e73a91c
tree: extend node removal to return child & parent pointers
These pointers will be useful for rebalancing in red-black and AVL trees.
Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
| author | Josef 'Jeff' Sipek <jeffpc@josefsipek.net> |
|---|---|
| date | Wed, 25 Jul 2018 10:27:34 -0400 |
| parents | 88468ed13408 |
| children | 4cb72cb51d62 |
| files | bst.c tree.c tree_impl.h |
| diffstat | 3 files changed, 36 insertions(+), 17 deletions(-) [+] |
line wrap: on
line diff
--- a/bst.c Tue Jul 24 16:01:10 2018 -0400 +++ b/bst.c Wed Jul 25 10:27:34 2018 -0400 @@ -64,5 +64,7 @@ void bst_remove(struct bst_tree *tree, void *item) { - tree_remove(&tree->tree, item); + struct tree_node *p, *c; + + tree_remove(&tree->tree, item, &p, &c); }
--- a/tree.c Tue Jul 24 16:01:10 2018 -0400 +++ b/tree.c Wed Jul 25 10:27:34 2018 -0400 @@ -184,10 +184,10 @@ } } -static inline void __remove_node(struct tree_tree *tree, - struct tree_node *parent, - struct tree_node *node, - struct tree_node *child) +static inline void __promote_node_child(struct tree_tree *tree, + struct tree_node *parent, + struct tree_node *node, + struct tree_node *child) { if (parent) parent->children[which_dir(parent, node)] = child; @@ -198,8 +198,19 @@ child->parent = parent; } -void tree_remove(struct tree_tree *tree, void *item) +/* + * Remove @item from @tree. + * + * @parent_r: the parent node of @child_r (may be NULL) + * @child_r: the node that ultimately took @item's new place in the tree + * (may be NULL) + */ +void tree_remove(struct tree_tree *tree, void *item, + struct tree_node **parent_r, + struct tree_node **child_r) { + struct tree_node *parent; + struct tree_node *child; struct tree_node *node; ASSERT3P(tree, !=, NULL); @@ -207,11 +218,11 @@ node = obj2node(tree, item); + /* + * Two children: exchange it with a leaf-ish node greater than this + * node. + */ if (node->children[TREE_LEFT] && node->children[TREE_RIGHT]) - /* - * Two children: exchange it with a leaf-ish node greater - * than this node. - */ __swap_nodes(tree, node, firstlast(node->children[TREE_RIGHT], TREE_LEFT), TREE_LEFT); @@ -219,20 +230,24 @@ /* now, we have zero or one child */ ASSERT(!node->children[TREE_LEFT] || !node->children[TREE_RIGHT]); + parent = node->parent; if (node->children[TREE_LEFT]) - __remove_node(tree, node->parent, node, - node->children[TREE_LEFT]); - else if (node->children[TREE_RIGHT]) - __remove_node(tree, node->parent, node, - node->children[TREE_RIGHT]); + child = node->children[TREE_LEFT]; else - __remove_node(tree, node->parent, node, NULL); + child = node->children[TREE_RIGHT]; + __promote_node_child(tree, parent, node, child); + + /* clear out the removed node */ node->parent = NULL; node->children[TREE_LEFT] = NULL; node->children[TREE_RIGHT] = NULL; tree->num_nodes--; + + /* return various info */ + *parent_r = parent; + *child_r = child; } void *tree_first(struct tree_tree *tree)
--- a/tree_impl.h Tue Jul 24 16:01:10 2018 -0400 +++ b/tree_impl.h Wed Jul 25 10:27:34 2018 -0400 @@ -27,7 +27,9 @@ extern void *tree_insert_here(struct tree_tree *tree, void *newitem, struct tree_cookie *cookie); -extern void tree_remove(struct tree_tree *tree, void *item); +extern void tree_remove(struct tree_tree *tree, void *item, + struct tree_node **parent_r, + struct tree_node **child_r); static inline void *node2obj(struct tree_tree *tree, struct tree_node *node) {