why is the average height of my BST so high?

Question

im currently working on a uni project and i am having som edifficulty with my Binary search tree, each node has to have a value but also a random "balance value" which is between 0 and 1, if a nodes balance value is more than its parents then the tree needs to be rotated, either left or right depending on the side the child sits.

public class RandomBST {
    class Node {
        int x;
        double balanceValue;
        Node parent;
        Node LChild;
        Node RChild;

        public Node(int i, double b) {
            x = i;
            balanceValue = b;
            parent = this;
            LChild = RChild =  null;
        }
    }

    Node root;

    public double randomDouble() {
        Random Ran = new Random();
        return (0 + (1 - 0) * Ran.nextDouble());
    }

    public void insert(int i) {
        double b = randomDouble();
        root = Rec_insert(root, i, b);
        Node p = findParent(root,i,-1);
        if (p.balanceValue < b ){
            if (p.x > i){
                rotateLeft();
            }else{
                rotateRight();
            }
        }
    }

    Node Rec_insert(Node root, int i, double b) {
        if (root == null) {
            root = new Node(i, b);
            return root;
        }
        if (i < root.x)
            root.LChild = Rec_insert(root.LChild, i, b);
        else if (i > root.x)
            root.RChild = Rec_insert(root.RChild, i, b);


        return root;
    }

    static Node findParent(Node node,int i, int parent) {
        if (node == null)
            return null;
        if (node.x == i) {
            return node.parent;
        } else {
            findParent(node.LChild, i, node.x);
            findParent(node.RChild, i, node.x);
        }
        return node.parent;
    }



    int findMax(int a, int b){
        if(a >= b)
            return a;
        else
            return b;
    }

    int findHeight(Node root){
        if(root == null)
            return 0;

        return findMax(findHeight(root.LChild), findHeight(root.RChild)) + 1;
    }
    
    public void rotateRight(){
        Node previoius = root;
        if (root.RChild!=null){
            root = root.RChild;
        }
        previoius.RChild = root.LChild;
        root.LChild = previoius;
    }
    
    public void rotateLeft(){
        Node previoius = root;
        if (root.LChild!=null){
            root = root.LChild;
        }
        previoius.LChild = root.RChild;
        root.RChild = previoius;
    }

 public static void main(String[] args) {
        int total = 0;
        for (int j = 0; j<1000;j++) {
            RandomBST RBST = new RandomBST();
            for (int i = 0; i < 1000; i++) {
                RBST.insert(i);
            }
            int height = RBST.findHeight(RBST.root);
            total =total + height;
        }
        System.out.println(total/1000);

    }

}

any suggestions on where im goign wrong woukd be fantastic, the output is meant to be around 20 to 21, yet i get around 850.

Answer 1

Making a brand new random number generator with

Random Ran = new Random();

may make your random number ...little random.

Create one generator in your application and direct all calls to it.