BinarySearchTree searching speed efficiency

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Random;


public class BSTSearchTimer {

int [] n = {10000, 50000, 100000, 250000};
Random rand = new Random();

public static void main(String[] args) throws IOException{

    BSTSearchTimer timer = new BSTSearchTimer();
    timer.runBSTSearchTimer();

}

public void runBSTSearchTimer() throws IOException{
    PrintWriter out = new PrintWriter( new FileWriter("tree2.csv"));
    int reps = 10000; // the number of searches that we will do on the tree


    for (int i = 0; i < n.length; i++){
        BinarySearchTree<Long> longBST = new BinarySearchTree<Long>();
        boolean success = true;

        int numOfElements = n[i];

        while (longBST.size() < numOfElements){

                success = longBST.add(rand.nextLong());
                while (!success){ // should keep attempting to add values until success is true
                    success = longBST.add(rand.nextLong());
            }

        }

        long start = System.currentTimeMillis(); // start the timer for searching

        for ( int j = 0; j < reps; j++){ // search rep times
            longBST.find(rand.nextLong());
        }
        long end = System.currentTimeMillis(); // end timer for searching tree

        double time = end-start;

        System.out.printf("%d, %f\n", longBST.size(), time);
        out.printf("%d, %f\n", n[i], time);

    }
    out.close();
}
}

When I run this program it is supposed to be making 4 different sized trees: 10000, 50000, 100000, 250000. I know that the speed efficiency on searching BSTs is supposed to be O(Log n) but I am getting these numbers:

when doing 10,000 searches I get these numbers: (first column is the size of the tree开发者_JAVA百科, the second is the time it took to do the search)

10000, 9.000000
50000, 3.000000
100000, 4.000000

when doing 100,000 searches:

10000, 41.000000
50000, 31.000000
100000, 40.000000
250000, 74.000000

Any tips are appreciated.

Most likely you're seeing the effect of "misses". Since you're just searching for random numbers, numbers that aren't in the tree will take a lot longer than number that are.

Also, the efficiency of a binary search tree is O(h), where h is the height of the tree. Red-Black trees and AVL trees guarantee that they will be constructed with a height of O(log n), but randomly constructed trees could easily end up with a height close to O(n).