特定の値を持つノードをBSTに戻すにはどうすればよいですか？

Question

私はいわゆる「ヒットバランスツリー」を作っています。違いは、私のノードクラスにはnumberOfHitsというインスタンス変数があり、にはメソッドが含まれているか、またはfindNodeメソッドが含まれているといつでも増えます。この演習のポイントは、ヒット数が最も多いノードを先頭に置くことです。そのため、ツリーは基本的に再構成されます（または回転します）。ルートは明らかにヒット数が最も高い。

ヒットカウントが最も高いノードを返す、私が作成しなければならないメソッドに関する質問があります。私は後で木を自転させるためにそれを必要とします（私は少なくともそれが計画だと思います）。ここに私のノードクラスがあります。 （もちろん、すべてのゲッター）

public class HBTNode<T> { 


private HBTNode<T> left; 
private HBTNode<T> right; 
private T element; 
private int numberOfHits; 


public HBTNode(T element){ 
    this.left = null; 
    this.right = null; 
    this.element = element; 
    this.numberOfHits = 0; 
} 

私はこれまで持っていることはこれです：

public int findMaxCount(HBTNode<T> node) { 

    int max = node.getNumberOfHits(); 
    if (node.getLeft() != null) { 
     max = Math.max(max, findMaxCount(node.getLeft())); 
    } 
    if (node.getRight() != null) { 
     max = Math.max(max, findMaxCount(node.getRight())); 
    } 
    return max; 
} 

それはノード自体を返すためにinteger.I必要性を返す除いこれは、正常に動作します。これを再帰的に行う必要があるため、最大のヒット数を見つけて、このメソッドをノードを返す別のメソッドで使用することにしました（これはおそらく実際には効率が悪いため、改善のヒントがあれば聞いています） ：

public int findMaxCount() { 
    return findMaxCount(root); 
} 


public HBTNode<T> findMaxCountNode(HBTNode<T> node) { 

    if (node.getNumberOfHits() == this.findMaxCount()) { 
     return node; 
    } 

    if (node.getLeft() != null) { 
     return findMaxCountNode(node.getLeft()); 
    } 
    if (node.getRight() != null) { 
     return findMaxCountNode(node.getRight()); 
    } 

    return null; 
} 

私はこのようなメソッドを呼び出す：

public HBTNode<T> findMaxCountNode() { 
    return findMaxCountNode(root); 
} 

それは私がそれは問題ないはずだと思うにもかかわらず、私は何かが欠けていますので、明らかに、再帰で良いことはないですnullを返します。あなたが私のこの行使について何かを持っているなら、私はどんな助けにも、新しい提案にも開いています。どうもありがとう。

テストコード：

public static void main(String[] args) { 


    HBTree<Integer> tree = new HBTree<Integer>(); 

    tree.add(50); 
    tree.add(25); 
    tree.add(74); 
    tree.add(19); 
    tree.add(8); 
    tree.add(6); 
    tree.add(57); 
    tree.add(108); 


    System.out.println(tree.contains(108)); //contains method increases the count by one 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(8)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(108)); 
    System.out.println(tree.contains(108)); 

    System.out.println(tree.findMaxCountNode()); 

} 

電流出力：true true true true true true true true null

予想される出力：true true true true true true true true Element: 108 Left child: 6 //this is just a toString, doesn't matter at this point Right child: null Number of hits: 5

Answer 1

あなたの2つの関数は次のようになりますように思えます。私はここで仮定していることはHBTNodeクラス内で定義されているこれらの機能は、自体の下、最高のヒットカウントノードを見つけるために設計されていることである。

public HBTNode<T> findMaxCountNode(HBTNode<T> node) { 
    return findMaxCountNode(node, node); 
} 

public HBTNode<T> findMaxCountNode(HBTNode<T> node, HBTNode<T> maxNode) { 

    HBTNode<T> currMax = (node.getNumberOfHits() > maxNode.getNumberOfHits()) ? node : maxNode; 

    if (node.getLeft() != null) { 
     currMax = findMaxCountNode(node.getLeft(), currMax); 
    } 

    if (node.getRight() != null) { 
     currMax = findMaxCountNode(node.getRight(), currMax); 
    } 

    return currMax; 
} 

public int findMaxCount(HBTNode<T> node) { 
    HBTNode<T> maxNode = findMaxCountNode(node); 
    if (maxNode != NULL) 
     return maxNode.getNumberOfHits(); 
    else 
     return -1; 
} 

どんな問題があるかどうか、私に教えてください、これは私の頭の上にはありませんが、メソッドの "整数"バージョンでは、メソッドの "Node finding"バージョンを使用する必要があることを指摘すると役に立ちます。最大の値がであることを確認するために書き込んだ方法は、最大のノードを見つけるためにここに書いたものと非常に似ています。