Блог

в настоящее время я работаю над проектом uni, и у меня возникли некоторые трудности с моим двоичным деревом поиска, каждый узел должен иметь значение, но также и случайное «значение баланса», которое находится в диапазоне от 0 до 1, если значение баланса узлов больше, чем у его родителей, то дерево необходимо повернуть влево или вправо в зависимости от стороны, на которой сидит ребенок.

 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.

Создание совершенно нового генератора случайных чисел с

 Random Ran = new Random();
 

может составить ваше случайное число …немного случайно.

Создайте один генератор в своем приложении и направляйте на него все вызовы.