Range query over binary search tree?

Okay, so does anyone know or can think of an efficient way to complete a range query over a given number range ie (x, y) in a standard binary search tree, using a minimum number of key comparisons? I wrote one that finds the minimum value <= x and then traverses the tree value by value until it finds a value that is above y, but I just realised that it would be a lot more efficient if it was recursive, and did not provide the range query's response in a sorted order.

Unfortunately, I have writer's block. Still getting used to getting my head in algorithm-space. Can anyone give me some pointers to get me started?

hahahahahahaha

haskell, sicp?

sicp, haskell, erlang

1) Find where x would be (or is) in the tree.

2) Traverse from x towards y, throwing the found values by-reference (depending on your desired semantics) into an ordered list. This can be done in linear space -- there was a thread about iterating a tree (check subjects.txt)

3) Hit y (or a value otherwise not in the range) and return the list.

Can anyone give me some pointers to get me started?
FFFDC980
8193A72E
00401000

>>4
FFFDC980
You sick fuck. Reported.

>>5
DEADBEEF
Take this then.

DFCDFCDFC

>>4
0xDICKBUTT

bool x = 0xD1C1<B|_|TT;

>>8
NYJMUP

0xFA66075

>>11
Ah, the illusive 28-bit architecture.

>>9
VALID PERL CODE

use warnings;
use strict;
BEGIN{*x=sub:lvalue{$_};*B=*_=*TT=sub(){2};*bool=sub{print+qq'\Uvalid$"perl$"code$/'}}
bool x = 0xD1C1<B|_|TT;

>>3

Like I said in the OP, that's what I originally did, but it's not very efficient if you don't need the list to be in sorted order.

Luckily, after a good night's sleep I was able to write the algorithm in about twenty minutes. I guess I was just suffering from some pretty severe programmer's block. My only problem now is that somehow I'm getting one extra key comparison creeping into my counter. I'm going to get someone else to proofread it to find out where, though.

Or alternatively, I guess I could post it here, and hope for some suggestions? It's pretty ugly code, especially in the traverse function - I haven't programmed in Java for years.

    public List<V> getValues(K rangeMin, K rangeMax)
    {
        count = 0; //Automatically set count equal to zero incase getLastCompare was not called.
        List<V> values = new LinkedList<V>();
        Node<K,V> p = root;
        boolean found = false;
        while(p.inited == 1 && !found){
            if(rangeMax.compareTo(p.key()) < 0){
                p = p.left();
                count++;
            }
            else if(rangeMin.compareTo(p.key()) > 0){
                p = p.right();
                count++;
            }
            else if(p.inited != 0){
                count++;
                values = traverse(p, rangeMin, rangeMax, values);
                found = true;
            }
        }
        return values;
    }

    private List<V> traverse(Node<K,V> node, K rangeMin, K rangeMax, List<V> values)
    {
        Node<K,V> p = node;
        values.add(node.value());
        if(p.left().inited == 1){
            p = p.left();
            count++;
            if(rangeMin.compareTo(p.key()) <= 0){
                values = traverse(p, rangeMin, rangeMax, values);
            }
            else{
                while(p.inited == 1 && rangeMin.compareTo(p.key()) > 0){
                    p = p.right();
                    count++;
                }
                if(p.inited == 1){
                    values = traverse(p, rangeMin, rangeMax, values);
                }
            }
        }
        p = node;
        if(p.right().inited == 1){
            p = p.right();
            count++;
            if(rangeMax.compareTo(p.key()) >= 0){
                values = traverse(p, rangeMin, rangeMax, values);
            }
            else{
                while(p.inited == 1 && rangeMax.compareTo(p.key()) < 0){
                    p = p.left();
                    count++;
                }
                if(p.inited == 1){
                    values = traverse(p, rangeMin, rangeMax, values);
                }
            }
        }
        return values;
    }

(define (get-values node min max)
  (define (traverse node values)
    (cond ((null? node)
           values)
          ((< (key node) min)
           (traverse (right node) values))
          ((> (key node) max)
           (traverse (left node) values))
          (#t
           (traverse (left node) (cons (value node) (traverse (right node) values))))))
  (traverse node '()))

>>16
If you're that fucking worried about performance you shouldn't fucking be using tail recursion in Java. Sure, you'll save yourself a couple of comparisons (which isn't really where Java's going to bottleneck you anyway) in exchange for raping the fuck out of the stack because most Java VM's don't optimize tail recursion¹.

Enjoy your shitty language and malformed programming practices.

                                 
^{References: [1] http://www.ibm.com/developerworks/java/library/j-diag8.html}

>>18
I lol'd.

>>1
there is such thing like «range trees» its based on red-black tree (which are used widely, base of C++'s std::map for example)

just google it

>>19
THIS IS NO LAUGHING MATTER!!!
$ java -version
java version "1.5.0_14-p8"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_14-p8-root_07_may_2008_12_21)
Java HotSpot(TM) Client VM (build 1.5.0_14-p8-hark_07_may_2008_12_21, mixed mode)

$ cat TailRecursionTest.java
public class TailRecursionTest {
        private static int loop( int i ) {
                return loop( i );
        }

        public static void main( String[] args ) {
                loop( 0 );
        }
}

$ javac TailRecursionTest.java
$ java TailRecursionTest
Exception in thread "main" java.lang.StackOverflowError
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        ...

>>21
private static int loop( int i ) {
        --i;
        if( i == 0 )
             return 0;
        else
             return loop( i );
}
...
loop(50000000)
Not a java coder, so you might want to check the syntax.

PS: return loop( i--) would keep a more functional look, though.

>>22,23
Are you fucking daft? Please re-read >>18,21 (and possibly the wikipedia article about optimizing tail recursion) to understand why any reasonable language can successfully execute >>21 without raping the stack. The code listing in >>21 was not intending to return a value (unlike your altered version in >>22), and your attempt to ``fix'' what was not already broken has revealed you are as incompetent as you are stupid.

Please refrain from posting on /prog/.

>>24

I don't know about you guys, but I quite enjoy raping unsuspecting stacks.

>>24

Also, if you wanted to do what >>22 does, I suggest:

public static int fucking java shit loop(int i) {
    return i ? loop(i - 1) : 0;
}

>>26
Do you rape them top-down or bottom-up?

>>27
$ javac Loop.java
Loop.java:2: ';' expected
    public static int fucking java shit loop(int i) {
                             ^
Loop.java:2: ';' expected
    public static int fucking java shit loop(int i) {
                                       ^
Loop.java:2: invalid method declaration; return type required
    public static int fucking java shit loop(int i) {
                                        ^
3 errors

>>27
_{I don't fucking want to do what} >>22 does!!!

private static int loop( int i ) {
        --i;
        if( i == 0 )
             return 0;
        else
             return loop( i );
}
...
loop(50000000)

>>29
what kind of shitty compiler keeps trying to parse a line after it encounters a syntax error?

Yes, good point! In fact, why don't we have the parser just stop completely after it hits an error of any kind? We couldn't have the compiler doing something useful, could we?

>>32
One that wants to give you as much information as possible so you don't have to recompile for every single typo.

>>33
if there's a syntax error it's not going to really do anything at all after that except print out potentially misleading error messages as it tries to incorrectly parse the rest of the code.
i don't think having over 9000 error messages (i've had this happen when compiling a certain open-source application, how the fuck can anyone be stupid enough to put 15000 lines of code in one file?) scroll the original error out of my terminal buffer is very useful.

>>34
you can't recompile something that you haven't compiled yet.
if there's a syntax error and the compiler still claims to have succeeded in compiling the file, something is very wrong.

>>35
well if there's a syntax error you can always pass it through a perl compiler

>>35
if there's a syntax error it's not going to really do anything at all after that except print out potentially misleading error messages as it tries to incorrectly parse the rest of the code.
When was the last time you tried to compile source with a few typos in it? 1978? Most modern parsers are very good at recovering from syntax errors.
Even as early as 1978, though, most parsers bailed out after a certain number of errors to prevent flooding the terminal.

you can't recompile something that you haven't compiled yet.
Attempt to recompile, then. Worthless pedant.

>>37
Reattempt to compile, moron.

progbot -pedant -O3 -funroll-loops


0x3feab33e
0x9939fede
0xf473902a
0xceb002ac
0x00007c00
0xffff0f10