Assume a binary tree with a data structure like this:
typedef struct binary_node BINARY_NODE;
#define BINARY_NODE BINARY_NODE
struct binary_node {
BINARY_NODE *next[2]; /* 0 -> left */
};
Assume insertions maintain a relevant order, but there is no balancing criteria.
removeBinaryNode()
takes a node and its parent as input, and removes the provided node.
BINARY_NODE *
findLeftmostBinaryNode (BINARY_NODE *node)
{
assert(node);
while (node->next[0]) {
node = node->next[0];
}
return node;
}
/* Returns the removed node (caller frees if needed). */
BINARY_NODE *
removeBinaryNode (BINARY_NODE *node, BINARY_NODE *parent)
{
assert(node && parent);
assert(parent->next[0] == node || parent->next[1] == node);
int from = (parent->next[1] == node);
/* At most one child. The node's child takes node's place. */
if (node->next[0] == NULL || node->next[1] == NULL) {
int next = (node->next[0] == NULL);
parent->next[from] = node->next[next];
node->next[0] = node->next[1] = NULL;
return node;
}
/* Merge left subtree with right subtree, reduces problem
to previous case. */
BINARY_NODE *leftmost = findLeftmostBinaryNode(node->next[1]);
assert(leftmost->next[0] == NULL);
leftmost->next[0] = node->next[0];
parent->next[from] = node->next[1];
node->next[0] = node->next[1] = NULL;
return node;
}
The following data structure provides a stateful predicate mechanism.
typedef struct binary_node_predicate BINARY_NODE_PREDICATE;
#define BINARY_NODE_PREDICATE BINARY_NODE_PREDICATE
struct binary_node_predicate {
bool (*test)(BINARY_NODE_PREDICATE *, BINARY_NODE *);
};
pruneBothSidesBinaryNode()
assumes the current node is already discounted for pruning, and prunes each of the left and right subtrees of the current node.
void pruneOneSideBinaryNode (
int, BINARY_NODE *, BINARY_NODE_PREDICATE *);
void
pruneBothSidesBinaryNode (BINARY_NODE *current, BINARY_NODE_PREDICATE *pred)
{
/* current's removal already ruled out */
if (current == NULL) return;
pruneOneSideBinaryNode(0, current, pred);
pruneOneSideBinaryNode(1, current, pred);
}
void
pruneOneSideBinaryNode (
int side, BINARY_NODE *parent, BINARY_NODE_PREDICATE *pred)
{
while (parent->next[side] && pred->test(pred, parent->next[side])) {
free(removeBinaryNode(parent->next[side], parent));
}
pruneBothSidesBinaryNode(parent->next[side], pred);
}
The root of the binary tree is actually just another BINARY_NODE
. The removeAllIfBinaryNode()
wraps a BINARY_NODE
with a dummy parent so that the root can be treated as the child of a parent.
void
removeAllIfBinaryNode (BINARY_NODE **root, BINARY_NODE_PREDICATE *pred)
{
BINARY_NODE dummy = { { (root ? *root : NULL), NULL } };
assert(root);
if (*root == NULL) return;
pruneOneSideBinaryNode(0, &dummy, pred);
*root = dummy.next[0];
}
Example
This is a generic binary tree interface. The usage would use membership of BINARY_NODE
into the client's data structure.
struct my_node {
BINARY_NODE base;
int key;
int value;
};
We can then hypothetically assume the existence of APIs that allowed a binary tree consisting of my_node
s to be created, even though the APIs manipulate BINARY_NODE
.
BINARY_NODE_PREDICATE
can be used to implement a stateful callback. It is not as useful for a stateless callback where a simple callback function pointer would have been sufficient. However, consider the case where there was a threshold to decide whether or not to delete an element, and the threshold was decided at runtime.
struct meets_threshold_predicate {
BINARY_NODE_PREDICATE base;
int threshold;
};
bool
meetsThreshold (BINARY_NODE_PREDICATE *pred, BINARY_NODE *node)
{
struct meets_threshold_predicate *p = (void *)pred;
struct my_node *n = (void *)node;
return n->value > p->threshold;
}
void
removeMyNodesAboveThreshold (struct my_node **root, int threshold)
{
struct meets_threshold_predicate p = {
{ meetsThreshold },
threshold
};
BINARY_NODE *base = &(*root)->base;
removeAllIfBinaryNode(&base, &p.base);
*root = (void *)base;
}