生成唯一的正整数并将它们添加到 AVL 树

Question

我正在尝试生成 1000 个唯一的正数 integer 并将其插入大小为 1000 的 AVL 树。为了方便起见，这些正数没有上限 bound.But，© 给出了上限Integer.MAX_VALUE.My 问题是，我可以将 1000 个数字添加到 arraylist，但是当我尝试将 arraylist 中的数字添加到 avl 树时，它只会添加其中一些数字（即 1000 个数字中的 39 个），我花了一天时间来解决它。感谢任何帮助。

这是我的 AVL 树 class:

import java.util.Stack;

public class AVLTree {

    public int findHeight(AVLNode node){
        if(node != null)
            return node.height;
        return 0;
    }
    public int getBalance(AVLNode node){
        if(node != null)
            return findHeight(node.left) - findHeight(node.right);
        return 0;
    }
    public AVLNode insertNumber(AVLNode node, int data){
        if(node == null) {
            return (new AVLNode(data));
        }
        //If current node's number is greater than newly added node's number, add it to the right
        if(node.number < data){
            node.right = insertNumber(node.right,data);
        }
        //If current node's number is less greater than newly added node's number, add it to the left
        else{
            node.left = insertNumber(node.left,data);
        }

        //update node's height
        node.height = Math.max(findHeight(node.left), findHeight(node.right)) + 1;
        int balDiff = getBalance(node);

        // Left Rotate
        if (balDiff > 1 && data < node.left.number) {
            return rotateRight(node);
        }

        // Right Rotate
        if (balDiff < -1 && data > node.right.number) {
            return rotateLeft(node);
        }

        // Left Right Rotate
        if (balDiff > 1 && data > node.left.number) {
            node = rotateLeft(node.left);
            return rotateRight(node);
        }

        // Right Left Rotate
        if (balDiff < -1 && data < node.right.number) {
            node = rotateRight(node.right);
            return rotateLeft(node);
        }
        return node;
    }
    public AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        // Rotation
        x.right = y;
        y.left = T2;

        // update their heights
        x.height = Math.max(findHeight(x.left), findHeight(x.right)) + 1;
        y.height = Math.max(findHeight(y.left), findHeight(y.right)) + 1;

        return x;
    }
    public AVLNode rotateLeft(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        // Rotation
        y.left = x;
        x.right = T2;

        // update their heights
        x.height = Math.max(findHeight(x.left), findHeight(x.right)) + 1;
        y.height = Math.max(findHeight(y.left), findHeight(y.right)) + 1;

        return y;
    }
    public void printInorder(AVLNode root){
        if(root != null){
            printInorder(root.left);
            System.out.println(root.number);
            printInorder(root.right);
        }
    }
    public int findMaximum(AVLNode node){
        //Recursive solution
        /*if(node.right == null) {
            return node.number;
        } else {
            return findMaximum(node.right);
        }*/

        //Iterative solution
        while(node.right != null){
            node = node.right;
        }
        return node.number;
    }
    public int findMinimum(AVLNode node){
        //Recursive solution
        /*
        if(node.left == null)
            return node.number;
        else
            return findMinimum(node.left);
        */

        //Iterative solution
        while(node.left != null){
            node = node.left;
        }
        return node.number;
    }
    public double getSum(AVLNode node){
        if(node == null)
            return 0;
        return node.number + getSum(node.left) + getSum(node.right);
    }
    public int getSumSmaller(AVLNode root, int data){
        int sum = 0;
        Stack<AVLNode> s1 = new Stack<AVLNode>();
        Stack<AVLNode> s2 = new Stack<AVLNode>();
        s1.push(root);

        while(!s1.isEmpty()){
            AVLNode tmp = s1.pop();
            s2.push(tmp);

            if(tmp.left != null && tmp.left.number < data){
                s1.push(tmp.left);
                sum = sum + tmp.left.number;
            }
            if(tmp.right != null && tmp.right.number < data){
                s1.push(tmp.right);
                sum = sum + tmp.right.number;
            }
        }
        return sum;
    }
}

这是我的主Java class:

public static void main(String[] args) {
        Random rnd = new Random();
        ArrayList<Integer> ar = new ArrayList<>();
        int counter = 0;
        AVLNode root = null;
        AVLTree avltree1 = new AVLTree();
        //AVLTree avltree2 = new AVLTree();
        //AVLTree avltree3 = new AVLTree();

        while(counter < 1000) {
            int val;
            do{
                val = rnd.nextInt(Integer.MAX_VALUE);
            }while(ar.contains(val));
            ar.add(val);
        }

        long initTime = System.nanoTime();
        for(int i = 0;i < counter;i++){
            root = avltree1.insertNumber(root,ar.get(i));
        } 
        long finishTime = System.nanoTime();
        avltree1.printInorder(root);
        long durationTime = finishTime-initTime;
}

Answer 1

我可以直接看到的一个问题是循环

while(counter < 1000) {
    int val;
    do{
        val = rnd.nextInt(Integer.MAX_VALUE);
    }while(ar.contains(val));
    ar.add(val);
}

永远不会终止，因为变量 counter 不会递增。

你的 AVLTree.insert() 方法有更大的问题。取以下代码：

// Right Left Rotate
if (balDiff < -1 && data < node.right.number) {
    node = rotateRight(node.right); // node = node.right.left;
    return rotateLeft(node); // return node.right
}

如果root是原始节点，那么这段代码就会returnroot.right.left.right。所以在循环中

for(int i = 0;i < counter;i++){
    root = avltree1.insertNumber(root,ar.get(i));
}

root 的值偶尔会移到树的更深处。难怪当你调用 printInorder(root); 时，它只打印树的一部分。

这不是您唯一的问题。为了更多地了解发生了什么，我建议创建一个更有用的方法来显示树：

public void printOut(AVLNode root)
{
  System.out.print("(");
  if (root != null) {
    System.out.print(root.number);
    printOut(root.left);
    printOut(root.right);
  }
  System.out.print(")");
}

然后将你原来的循环修改为

for(int i = 0;i < counter;i++){
    root = avltree1.insertNumber(root,ar.get(i));
    avltree1.printOut(root);
}

将树的大小从 1000 减小以了解发生了什么。您可能希望跟踪原始根并在循环中调用 printOut(originalRoot);。

生成唯一的正整数并将它们添加到 AVL 树

Generating unique positive integer numbers and adding them to AVL Tree

java

data-structures

avl-tree