Binary search through quad-tree

I have a quad tree where the leaf nodes represent pixels. There is a method that prunes the quad tree, and another method that calculates the number of leaves that would remain if the tree were to be pruned. The prune method accepts an integer tolerance which is used as a limit in the difference between nodes to check whether to prune or not. Anyway, I want to write a function that takes one argument leavesLeft. What this should do is calculate the minimum tolerance necessary to ensure that upon pruning, no more than leavesLeft remain in the tree. The hint is to use binary search recursively to do this. My question is that I am unable to make the connection between binary search and this function that I need to write. I am not sure how this would be implemented. I know that the maximum tolerance allowable is 256*256*3=196,608, but apart from that, I dont know how to get started. Can anyone gui开发者_如何学JAVAde me in the right direction?

You want to look for Nick's spatial index quadtree and hilbert curve.

1. Write a method that just tries all possible tolerance values and checks if that would leave exactly enough nodes.
2. Write a test case and see if it works.
3. Don't do step 1. Use a binary search in all possible tolerance values to do same as step 1, but quicker.

If you don't know how to implement a binary search, you can better try it on a simple integer array first. Anyway, if you do step 1, just store the number of leaves left in array (with the tolerance as index). And then execute a binary search on that. To turn this into step 3, notice you don't need the entire array. Simply replace the array by a function that calculates the values and you're done.

Say you plugged in tolerance = 0. Then you'd get an extreme answer like zero leaves left or all the leaves left (not sure how it works from your question). Say you plug in tolerance = 196,608. You'd get an answer at the other extreme. You know the answer you're looking for is somewhere in between.

So you plug in a tolerance number halfway between 0 and 196,608: a tolerance of 98,304. If the number of leaves left is too high, then you know the correct tolerance is somewhere between 0 and 98,304; if it's too low, the correct tolerance is somewhere between 98,304 and 196,608. (Or maybe the high/low parts are reversed; I'm not sure from your question.)

That's binary search. You keep cutting the range of possible values in half by checking the one in the middle. Eventually you narrow it down to the correct tolerance. Of course you'll need to look up binary search in order to implement it correctly.