d3nls - 4 months ago 18

Java Question

I have to make a so called "Hit Balanced Tree". The difference is that as you can see, my node class has an instance variable called numberOfHits, which increments anytime you call **contains** method or **findNode** method. The point of this exercise is to have the nodes with highest hit count on the top, so the tree basically reconstructs itself (or rotates). Root has the highest hit count obviously.

I have a question regarding a method I have to make, that returns the node with highest hit count. I will later need it to make the tree rotate itself (I guess, at least that's the plan). Here is my node class. (All the getters of course)

`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;

}

What I have so far is this:

`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;

}

This works fine, except it returns an integer.I need to return the node itself. And since I have to do this recursively, I decided find the biggest hit count and then subsequently using this method in another method that returns a node, like this(it's probably really inefficient, so if you have tips on improvement, I am listening):

`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;

}

I call the method like this:

`public HBTNode<T> findMaxCountNode() {`

return findMaxCountNode(root);

}

It returns null even though I think it should be fine, I am not that good at recursion so obviously I am missing something. I am open to any help, also new suggestions, if you have any about this exercise of mine. Thanks a lot.

Test code:

`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());

}

Current output:

`true`

true

true

true

true

true

true

true

null

Expected output:

`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

Seems like your two functions should look like the following. What I'm assuming here is that these functions, which are defined inside the HBTNode class, are designed to find the highest hit-count node *below* itself:

```
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;
}
```

Let me know if there are any issues, this is off the top of my head, but I thought it would be helpful to point out that the "integer" version of your method should just use the "Node finding" version of the method. The method you wrote to find the maximum *value* is quite similar to the one I wrote here to find the maximum *node*.