0

ヒットとその要素に応じてノードのバランスを取る BST に取り組んでいます。ヒットとは、find()、contains() などを使用してノードが見つかったときに増加する属性です。ツリーのルートはノードです。ヒット数が最も多い。ヒットをインクリメントした後にツリーのバランスを取る balance メソッドを除いて、私のコードはすべて問題ありません。変更された AVL ツリーの回転メソッド ( https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java ) を使用しています。ここでは、要素ではなく、ヒット数を比較します。ノード。何を試しても機能しません。ツリーを正しくバランスさせることができません。これまでのコードは次のとおりです。

 public void balanceTree() {
    balanceTree(root);
}

private void balanceTree(Node node) {

    if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) {
        return;
    } else if (node.left.getHits() > node.getHits()) {
        node = rotateWithLeftChild(node);

    } else if (node.right.getHits() > node.getHits()) {
        node = rotateWithRightChild(node);

    }


}

static Node rotateWithLeftChild(Node k2) {
    Node k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    return k1;
}

static Node rotateWithRightChild(Node k1) {
    Node k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    return k2;
}

現在、balance メソッドは、回転するはずのノードを削除するだけです。デバッグを試みましたが、何が問題なのかわかりませんでした。

4

2 に答える 2

0

このコードには 2 つの問題があります。
1)このツリーの構造が恋しい。したがって、hitCount に基づいて並べ替える必要があります。基本的に、hitCount で並べ替えられたリスト/コレクションではありませんか?

現在、ノード自体よりも hitCount が大きい場合、ノードを左右のノードと交換しています。したがって、2 つのノード [A, B] を想像してください。A には 1 つの hitCount があり、B には 2 つの hitCount があります。ソート時 (おそらくノードを反復処理します): 開始
状況: [A, B]

最初の並べ替え: A は B よりも hitCount が低いため、右と交換します。結果 = [B, A]

2 番目の並べ替え: A は B よりも hitCount が低いため、左と交換します。結果 = [A, B]

どこで終わりますか？List を使用し、hitCount に基づいてノードをソートすることをお勧めします。このようにして、これらすべてを台無しにする必要はありません。

2)スワップ メソッドが思ったように機能しない。これをよく見てください：

 static Node rotateWithLeftChild(Node k2) {
     Node k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     return k1;
 }

 // exact the same results:
 static Node rotateWithLeftChild(Node k2)
 {
     k2.left = k2;
     return k2.left;
 }

私には正しくないようです。おそらくあなたは次のような意味でした：

 static Node rotateWithLeftChild(Node k2)
 {
     Node k1 = k2.left;
     k1.right = k2.right;
     k2.left = k1.left;
     k1.left = k2;
     k2.right = k1;
     return k1;
 }

もちろん、「rotateWithRightChild」の場合は逆になります。

これが少しお役に立てば幸いです。

編集：

注文のためにリスト/コレクションを実装する方法は? ノードがツリーに追加されたら、そのノードを Lisf/Collection に追加するだけです。ノードを並べ替えたい場合は、次のようにします。

 //myNodesCollection is the List/Collection containing all the nodes.
 static void sortByHitCount()
 {
     Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits());
 }

複雑に思えるかもしれませんが、これはすべてのソートを行うメソッドです。最初のパラメーターは、並べ替えたいリスト/コレクションです。2 番目のパラメータはコンパレータで、この場合は hitCount に基づいて各ノードを比較します。

ドキュメント: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

于 2016-10-23T19:35:52.803 に答える