Java的AVL树 [英] AVL Tree for Java

问题描述

我不确定我是否正确执行此操作，因为这是我第一次使用节点进行编码.但是到目前为止，这是我的代码，如果有人可以看一下并帮助我了解我做错了什么.另外，我的插入/删除方法也给我带来了麻烦.教授为我们提供了伪代码，但是我似乎无法掌握如何将其解释为Java代码，因为我以前从未做过这种类型的代码.主要是因为有一个if语句检查高度以查看树是否平衡，我将如何在其中实现高度?提示或任何帮助都将不胜感激，我已经坚持了一段时间.谢谢！

I'm not sure if I'm doing this correctly as this is my very first time coding with nodes. But here's my code so far, if someone can look over it and help me out with understanding if I'm doing anything wrong. Also my insert/remove methods are giving me a hard time. The professor gave us the pseudocode for that but I can't seem to grasp how to interpret it into Java code as I've never done this type of code before. Mostly because there's a if statement that checks the heights to see if the tree is balanced, how would i implement height in this? Hints or any help is greatly appreciated, I've been stuck on this for a while. Thanks!

我也不认为我正确地构造了我的构造函数，对此我不确定.插入/删除中的返回可以忽略，它只是放在其中以确保其余代码可以编译.

I also don't think I did my constructor correctly and I'm unsure about it. The return in insert/remove can be ignored, it was just put in there to make sure the rest of the code will compile.

public class AvlNode{

    public static void main(String[]args){

    }
    //constructor
    public class AvlTreeNode{
        private int num;
        private AvlTreeNode left;
        private AvlTreeNode right;

        public AvlTreeNode left(){
            return this.left;
        }

        public AvlTreeNode right(){
            return this.right;
        }

        public int value(){
            return this.num;
        }
    }
    //method to find the number specified on the node
    public AvlTreeNode find(AvlTreeNode t, int x){
        if(t == null){
            return null;
        }
        if( t.value() == x){
            return t;
        }
        else if(x < t.value()){
            return find(t.left(), x);
        }
        else{
            return find(t.right(), x);
        }
    }
    //method to insert a new node and number to a tree
    public AvlTreeNode insert(AvlTreeNode t, int x){
        if(t == null){
            t = new AvlTreeNode(x, null, null);
            return t;
        }
        if(x < t.value()){
            t.left = insert(t.left(), x);
        }
        return t;
    }
    //method to remove a node and number from the tree
    public AvlTreeNode remove(AvlTreeNode t, int x){
        return t;
    }
    //Inorder traversal method, should print out numbers in ascending order if correct
    public void inOrder(AvlTreeNode t){
        if(t != null){
            inOrder(t.left());
            System.out.print(t.value() + " ");
            inOrder(t.right());
        }
    }
    //single rotation of nodes to balance tree, rotating leftwards
    public static AvlTreeNode singleRotateWithLeft( AvlTreeNode k1){
        AvlTreeNode k2 = k1.left;
        k1.left = k2.right;
        k2.right = k1;
        return k2;
    }
    //single rotation of nodes to balance tree, rotating rightwards
    public static AvlTreeNode singleRotateWithRight( AvlTreeNode k2){
        AvlTreeNode k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        return k1;
    }
    //double rotation of nodes towards the left
    public static AvlTreeNode doubleRotateWithLeft( AvlTreeNode k3){
        k3.left = doubleRotateWithRight(k3.left);
        return doubleRotateWithLeft(k3);
    }
    //double rotation of nodes towards the right
    public static AvlTreeNode doubleRotateWithRight( AvlTreeNode k2){
        k2.right = doubleRotateWithLeft(k2.right);
        return doubleRotateWithRight(k2);
    }
}

推荐答案

关于构造函数:我认为这是错误的事情，是您错误地使用了用于为构造函数描述AvlTreeNode的内部类.您极有可能不需要编写显式构造函数，因为默认的(空)构造函数将为您效劳.

Regarding the constructor: I think the thing that is wrong, is that you mistake the inner class you use to describe a AvlTreeNode for a constructor. In all probability, you don't need to write an explicit constructor, because the default (empty) one will do for you.

树的构造可以看作是将其所有节点插入到空树中.

The construction of a Tree can be viewed as the insertion of all its nodes to an empty tree.

关于高度，您可能应该将树的高度视为每个AvlTreeNode的属性(因此，在num旁边，您需要一个height变量).接下来的事情是实现插入和删除，以便使用正确的局部转换/旋转，并适当地增大或减小插入的节点及其子节点的高度.

Regarding the height, you should probably view the height of a tree as a property of each AvlTreeNode (so, next to num you need a height variable). The next thing will be to implement insert and remove so that the correct local transformations / rotations are used and so that the heights of the inserted node and its children are increased or decreased appropriately.

edit:我现在看到您的代码使用带有三个参数的构造函数.您可以使用本示例代码中的构造器.

edit: I now see that your code uses a constructor with three arguments. You can use a constructor like the one in this example code.

//inner class for the node
public class AvlTreeNode{
    private int num;
    private int height;

    private AvlTreeNode left;
    private AvlTreeNode right;

    //this is the constructor!
    public AvlTreeNode(int value, AvlTreeNode left, AvlTreeNode right){
        this.num = value;
        this.left = left;
        this.right = right;
        this.height = 1;

        if (left != null && left.height() >= height){
            height = left.height() + 1;
        }
        if (right != null && right.height() >= height){
            height = right.height() + 1;
        }
    }

    public AvlTreeNode left(){
        return this.left;
    }

    public AvlTreeNode right(){
        return this.right;
    }

    public int value(){
        return this.num;
    }

    public int height(){
        return height;
    }
}

这篇关于Java的AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！