为什么我的 BST 的平均高度这么高？

Question

我目前在一个 uni 项目上工作，我的二叉搜索树有些困难，每个节点都必须有一个值，但如果节点平衡，也必须有一个介于 0 和 1 之间的随机“平衡值”值大于它的 parents 那么树需要旋转，根据 child 所在的一侧向左或向右旋转。

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);

    }

}

关于我在哪里出错的任何建议都很棒，输出应该在 20 到 21 左右，但我得到了 850 左右。

Answer 1

使用

制作全新的随机数生成器

Random Ran = new Random();

可以让你的随机数...小随机。

在您的应用程序中创建一个生成器并将所有调用定向到它。

为什么我的 BST 的平均高度这么高？

why is the average height of my BST so high?

java

binary-search-tree