バイナリ検索ツリーバランス

Question

ヒットとその要素に応じてノードのバランスを取るBSTに取り組んでいます。ヒットは、find（）、contains（）などを使ってノードを見つけたときに増加する属性です。 ツリーのルートはヒット数が最も多いノードです。 ヒットをインクリメントした後にバランスを取るバランスメソッド以外のコードはすべて問題ありません。 修正されたAVL Tree rotateメソッド（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; 
} 

今のバランス方法は、単純にノードのを削除します回転するはずですが、私はそれをデバッグしようとしましたが、何が間違っているのか分かりませんでした。

Answer 1

一つは、渡されたパラメータを変更することはできません。

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

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

あなたはすべての挿入後のツリーにをリバランスすると仮定すると、1は、サブツリーのバランスを取るために回転した後、再帰的にする必要はありません。

回転しないと、再発する必要があります。

現在のアルゴリズムを再帰的には、左と右が、左に回転が行われた場合は、右のサブツリーはもはや再帰ない可能性があります。修正アルゴリズムのような種類のため

もっと気になる、それが安定していないかもしれないということです：リバランスを保ちます。しかし、あなたは確かにテストにスポットを当てます。

Answer 2

このコードには2つの問題があります。
1）私はこのツリーの構造が不足しています。ですから、hitCountに基づいてソートする必要があります。基本的には、リスト/コレクションはhitCountでソートされていませんか？

今のところ、自分よりも高いhitCountを持っている場合は、左右のノードでノードを交換しています。だから、2つのノード[A、B] Aには1つのhitCountがあり、Bには2つのhitCountがあるとします。だから、（あなたがpropably itterateのノードにします）ソートに：
は、状況を開始します：[A、B]

まずソート： Aは右とスワップので、Bより低いHITCOUNTを持っています。結果= [B、A]

第2ソート： AはBよりもヒットカウントが低いため、左にスワップします。結果= [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に追加するだけです。ノードを並べ替えるには、次のようにします。

これはすべての並べ替えを行う方法です。最初のパラメータは、並べ替えるリスト/コレクションです。第2のパラメータは、この場合、それぞれのノードをそのhitCountに基づいて比較する比較器である。

ドキュメント：1新しいノード値を返す必要があるので、Javaでhttps://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html