0

私はいくつかのデータ構造の内外を学習しようとしており、バイナリ スプレー ツリーを適切に機能させようとしています。次のコードを実行すると、探しているノードがルートを 1 つ以上超えているたびに、そこにあることがわかり、ルートからその側全体が削除されます。ノードが上から 1 レベルだけ下にある場合は、正常に機能します。

何がうまくいかないのかわかりませんが、回転機能と関係があると思います。これをモデルにした挿入機能で適切に動作するようにしました。

public class SplayBST {
    Node root;
    int count;
    int level = 0;
    boolean found = false;
    public SplayBST() {
        root = null;
        count = 0;
    }

public String searchIt(String x) {
    //after finishing search method I need to check if splaySearch exists then don't insert just splay it
    splaySearch(root, x);
    if (this.found == true) {
        this.found = false;
        return x;
    }
    else {
        return null;
    }
}


    Node splaySearch(Node h, String x) {
        if (h == null) {
            return null;
        }
        if (x.compareTo(h.value) < 0) {
            try {
            if (x.compareTo(h.left.value) < 0) {
                h.left.left = splaySearch(h.left.left, x);
                h = rotateRight(h);
            } else if (x.compareTo(h.left.value) > 0) {
                h.left.right = splaySearch(h.left.right, x);
                h.left = rotateLeft(h.left);
            }
            else {
                this.found = true;
                return h.left;
            }
            return rotateRight(h);
            } 
        catch (NullPointerException ex) {
            return null;
            }
        }

        else { //basically x.compareTo(h.value)>0
            try {
            if (x.compareTo(h.right.value) > 0) {
                h.right.right = splaySearch(h.right.right, x);                
                h = rotateLeft(h);
            } else if (x.compareTo(h.right.value) < 0) {
                h.right.left = splaySearch(h.right.left, x);
                h.right = rotateRight(h.right);
            }
            else {
                this.found = true;
                return h.right;
            }
            return rotateLeft(h);
            }
            catch (NullPointerException ex) {
                return null;
            }
        }
    }


    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        return x;
    }
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        return x;
    }


    class Node {
        Node left;
        Node right;
        String value;
        int pos;
        public Node(String x) {
            left = null;
            right = null;
            value = x;
        }
    }
}
4

2 に答える 2

2

「機能する」検索方法を使用して通常のBSTを作成するためのTristanHullの2番目のアプローチ。それが機能するようになったら、splayメソッドを追加するのは簡単です。Javaでスプレーツリーを実装したときも、実際に同じことをしました。これは、より優れたソフトウェア設計とより単純な実装です。

于 2012-10-09T00:00:59.030 に答える
1

あなたの問題は、回転すると、関数「SplaySearch」でノード H への参照を更新しますが、元の「searchIt」関数で親ノードを更新しないことです。したがって、プログラムは、回転したノードが親である必要がある場合でも、元の親ノードが親のままであると「考え」ます。したがって、ツリーを印刷するために使用するメソッドを実行すると、実際にはツリーの親ノードではなく子ノードから印刷されます (そのレベルは、プログラムがrotateLeftとrotateRightを呼び出した回数によって異なります) ）。

これを修正するには、通常のバイナリ ツリーと同じように検索を実装し、ノードをツリーの最上部に展開する検索機能とは完全に分離した「スプレイ」機能を作成することをお勧めします。すべての検索の最後にこの splay 関数を呼び出して、参照を適切に更新するようにします。これはスプレイ ツリーを実装する従来の方法であり、これを参照することをお勧めします (スプレイ ツリーに関するウィキペディアの記事を参照するか、Google 検索を行うことをお勧めします)。また、回転機能が完全ではないことを知りたい場合もあります。スプレー ツリーに関しては、シングル ローテーションとは大きく異なる 2 つの別々のタイプのダブル ローテーションもあります。繰り返しになりますが、スプレー ツリーについて詳しく調べることをお勧めします。

于 2012-10-08T23:05:26.693 に答える