juli (caladri) wrote in dailysrc,
juli
caladri
dailysrc

Getting values from a binary tree within a range.


struct tree {
	struct tree *left;
	struct tree *right;
	int val;
};

struct tree *
tree_create(int val)
{
	struct tree *t;

	t = malloc(sizeof *t);
	t->left = NULL;
	t->right = NULL;
	t->val = val;
	return (t);
}

struct tree *
tree_insert(struct tree *root, int val)
{
	if (root == NULL)
		return (tree_create(val));
	if (val < root->val)
		root->left = tree_insert(root->left, val);
	else
		root->right = tree_insert(root->right, val);
	return (root);
}

void
tree_range_hit(struct tree *t)
{
	/* Do something.  */
}

int
tree_range_recursive(struct tree *root, int min, int max)
{
	int visits;

	visits = 0;

	if (root == NULL)
		return (visits);
	visits++;
	if (min < root->val)
		visits += tree_range_recursive(root->left, min, max);
	else {
		if (min == root->val && root->val <= max)
			tree_range_hit(root);
		visits += tree_range_recursive(root->right, min, max);
		return (visits);
	}
	if (max >= root->val) {
		tree_range_hit(root);
		if (max == root->val)
			return (visits);
		visits += tree_range_recursive(root->right, min, max);
	}
	return (visits);
}



I have a much better approach stuck in my head (which should be a lot faster), but I can't quite work out how to get the code right. Mind, that approach is only faster if you can find the node with the value closest to but not less than min in O(1) time (for example, if you have a pointer to that node already and are finding all nodes which are greater than it but less than some constraint.) It's sort of like what you do to iterate through all items greater than a given starting point, but avoids excess exploration of the left branches of parent nodes.
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 0 comments