d3nls d3nls - 1 month ago 8
Java Question

How can I return a node with a specific value in a BST?

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.

Comments