2

AVL ツリーの実装にいくつか問題があります。すべてのローテーションとすべての追加のコードは正しいようです。プログラムをドライランして、論理的に正しく実行されていることを徹底的に確認します。想定される 100 からいくつかの整数しか出力しないため、ツリー トラバーサル (順序どおり) に問題があるようです。また、入力内容に関係なく、検索は常に失敗します。何が起こっているのか理解できないようですが、いくつかの null ポインターと関係があると思われます。以下は、AVL ツリーのコードです。AddNode メソッドまたは回転メソッドに間違ったコードがあるかどうか疑問に思っていますが、問題ないようです。クラスは、Node クラス、AVL クラス、およびメイン クラスである AVL ツリー クラスです。 .

ノードクラス

private int data;
private Node left;
private Node right;     
private int height;

public Node(int m) {
    data = m;        
    left = null;
    right = null;
    height = 0;
}

public void setToleft(Node newleft) {
    left = newleft;
}

public Node getleftNode() {
    return left;
}

public void setToright(Node newright) {
    right = newright;
}

public Node getrightNode() {
    return right;
}

public int getData() {
    return data;
}

public int getHeight(){
    return height;
}

public void setHeight(int height){
    this.height = height;
}

AVLクラス

public Node root;

public AVL(int root) {
    this.root = new Node(root); // since root presently has no left or right children, height is currently 0
}

public int Height(Node n) {

    if (n == null) { //basis step                 
        return -1;
    } else { //add one for every path 
        if (n.getleftNode() == null && n.getrightNode() == null) {
            return 0;
        }
        return 1 + Math.max(Height(n.getleftNode()), Height(n.getrightNode()));
    }
}

public void add(int data) {
    addNode(data, root);
    root.setHeight(Math.max(Height(root.getleftNode()), Height(root.getrightNode())) + 1);
}

public void addNode(int data, Node n) {

    if (data < n.getData()) {
        if (n.getleftNode() == null) {
            n.setToleft(new Node(data));
        } else {
            addNode(data, n.getleftNode());
        }

        n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);

        if ((Height(n.getleftNode()) + 1) - (Height(n.getrightNode()) + 1) == Math.abs(2)) {
            if (data < n.getleftNode().getData()) {
                n = LLRotation(n);
            } else {
                n = LRRotation(n);
            }
        }
    } else if (data >= n.getData()) {  //>= also caters for duplicates and inserts them infront of same value
        if (n.getrightNode() == null) {
            n.setToright(new Node(data));
        } else {
            addNode(data, n.getrightNode());
        }

        n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);

        if ((Height(n.getrightNode()) + 1) - (Height(n.getleftNode()) + 1) == Math.abs(2)) {
            if (data >= n.getrightNode().getData()) {
                n = RRRotation(n);
            } else {
                n = RLRotation(n);
            }
        }
    }
}

public Node LLRotation(Node n) {      //single

    Node n1 = n.getleftNode();
    n.setToleft(n1.getrightNode());
    n1.setToright(n);
    n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
    n1.setHeight(Math.max(Height(n1.getleftNode()), Height(n)) + 1);
    //compares heights of left and right subtrees and gets max
    //the above source code is of course vital since the node height must be resetted after rotations
    //adding 1 at the end of the last two code lines is important since 
    //initially the height is only calculated from subtrees onwards
    //same for single right rotation below
    return n1;
}

public Node RRRotation(Node n) {   //single

    Node n1 = n.getrightNode();
    n.setToright(n1.getleftNode());
    n1.setToleft(n);
    n.setHeight(Math.max(Height(n.getleftNode()), Height(n.getrightNode())) + 1);
    n1.setHeight(Math.max(Height(n1.getrightNode()), Height(n)) + 1);

    return n1;
}

public Node LRRotation(Node n) {   //double

    n.setToleft(RRRotation(n.getleftNode()));
    return LLRotation(n);       
}

public Node RLRotation(Node n) {   //double

    n.setToright(LLRotation(n.getrightNode()));
    return RRRotation(n);         
}

public void inOrderTraversal(Node n) {

    if (n != null) {
        inOrderTraversal(n.getleftNode()); //recursive call to the left subtree
        System.out.println(n.getData()); //line which makes the actual node to display its data
        inOrderTraversal(n.getrightNode()); //recursive call to the right subtree
    }

}

public void traverse() {
    inOrderTraversal(root);   // can be called in main class to automatically traverse tree from its root
}

public int search(int x) {
    try {
        if (x == root.getData()) { //basis step
            System.out.println("Item found!");
            return x;
        }
        if (x < root.getData()) {
            root = root.getleftNode();
            return search(x);//recursive call
        } else {
            root = root.getrightNode();
            return search(x);//recursive call
        }
    } catch (NullPointerException e) {
        System.out.println ("Search failed!");
        return 0;
    }
}

メインクラス

public static void main(String[] args) throws IOException {

    Scanner s = new Scanner(System.in);

    AVL tree = null;

    int choice = 0;

    System.out.println("AVL TREE");

    System.out.println("\n Choose an option from the menu: ");
    System.out.println("\n\t 1.) Create file of 100 integers");
    System.out.println("\n\t 2.) Create the tree");
    System.out.println("\n\t 3.) In-Order traverse and show tree");
    System.out.println("\n\t 4.) Search for integer");
    System.out.println("\n\t 5.) Quit");

    while (choice != 5) {

        System.out.print("\nChoice: ");
        choice = s.nextInt();

        switch (choice) {

            case 1:
                createFile();
                break;

            case 2:
                try {
                    FileReader readto = new FileReader("Integers.txt");
                    BufferedReader br = new BufferedReader(readto);

                    String line = br.readLine(); //reads text at start of file                        
                    line = br.readLine(); // skipping empty lines                      
                    line = br.readLine();
                    line = br.readLine();

                    int root = Integer.parseInt(line);   //extracts first integer from the line
                    System.out.println("Root: " + root);

                    tree = new AVL(root);                        

                    int x = 0;
                    while (x != 99) {
                        try {
                            line = br.readLine();
                            int next = Integer.parseInt(line);
                            tree.add(next);
                            System.out.println(next);
                            x++;
                        } catch (NumberFormatException e) {
                        };
                    }
                    System.out.println("Tree successfully populated!");
                } catch (FileNotFoundException e) {
                    System.out.println("ERROR: File not found!");
                }
                break;

            case 3:
                System.out.println("In-Order traversel executed. The now balanced tree shall now be printed in");
                System.out.println("ascending order and also the left and right children of each node shall be printed.\n");

                System.out.println("Traversal: ");

                tree.traverse();
                break;

            case 4: 
                System.out.print("Please enter the integer to be searched: ");
                int x = s.nextInt();

                System.out.println(tree.search(x));
                break;

            case 5:
                System.exit(0);
                break;

            default:
                System.out.println("ERROR: Choice out of bounds!");
        }

    }
}

static void createFile() throws IOException {

    Random r = new Random();

    File intfile = new File("Integers.txt");
    FileWriter writeto = new FileWriter("Integers.txt");
    BufferedWriter bw = new BufferedWriter(writeto);
    if (!(intfile.exists())) {
        System.out.println("ERROR: File not found!");
    } else {

        bw.write("The following integers are randomly generated");
        bw.newLine();
        bw.write("and will be used to construct the AVL tree:");
        bw.newLine();
        bw.newLine();

        int x;

        System.out.println("The following random numbers shall be used to build the AVL tree: \n");

        for (int i = 0; i < 100; i++) {
            x = r.nextInt(100) + 1;
            bw.write(String.valueOf(x));
            bw.newLine();
            System.out.println(x);
        }
        bw.close();
    }

}

トラバーサルの出力は次のとおりです。

トラバーサル: 44 53 54 54 77

100 個の整数が入力され、その中にこれらがあったとします。しかし、トラバーサルの出力はこれだけでした。

検索の出力は次のようになります: Choice: 4 検索する整数を入力してください: 44 Item found! 44

選択肢: 4 検索する整数を入力してください: 100 検索に失敗しました! 0

100 と 44 はどちらもツリーに追加された整数ですが、44 が見つかり、100 が見つかりませんでした..わかりません..

誰でも私を解決策に導くことができます..？

前もって感謝します ：）

4

1 に答える 1

1

さて、最初に明らかなこと...あなたのsearchメソッドでは、ツリーのルートを保持する変数を悪用しroot、検索が進むにつれて新しい値に設定します。したがって、最初の検索後、検索でrootトラバースされた最後のノードを指し、ツリーのルートノードを指しなくなります。以降のすべての検索で、その時点以降に何かが見つかる可能性はほとんどありません。

検索は再帰的であるため、検索対象のノードをパラメーターとして渡してみてください。

int search(Node node, int key) {

    if (node == null) {

         return 0;  // missing from tree

    } else if (key < node.getData()) {

         return search(node.getLeft(), key);

    } else if (key > node.getData()) {

         return search(node.getRight(), key);

    } else {

         return node.getData();  // found it
    }
}

（コメントに対処するために編集）公開されているラッパーと内部実装を使用してadd/メソッドのペアを使用する場合と同様に、このメソッドを公開する必要がある場合があります。addNode

public int search(int key)  {
    return searchNode(root, key);
}

private int searchNode(Node node, int key) {
    // Perform the recursive search, as above
}

add/addNodeメソッドに関連する他の問題があります。見落としたかもしれませんが、回転によって必要になる場合は、ツリーのルートノードをどこでも調整しません。これにより、事実上、ツリーのバランスが崩れ、時間の経過とともにAVLプロパティが失われます。

于 2011-12-18T16:22:44.943 に答える