I am trying to create null nodes at the bottom of a RBTree and want to instantiate EMPTY as an empty node.
this the line that has the error:
final private Node<E> EMPTY = new Empty();
And the empty class:
private class Empty extends Node<E> {
public Empty() {
red = false;
}
public Node<E> add(E data) {
count++;
return new Node<E>(data);
}
public Node<E> getNode(E data) {
return null;
}
}
I know it has something to do with the constructor but I can't zero in on it. I have tried searching but most everything I come across on this site is related to android programming and/or some other language I'm not familiar with. I've tried the following:
(Node) casting the new Empty(); then realized it was obviously not that.
and working with the class seeing if public would work.
Aside from programming changes i've also tried the solutions offered here:
http://philip.yurchuk.com/software/eclipse-cannot-be-resolved-to-a-type-error/
But to no success.
Sorry if this question is out of place, and thank you for your time!
complete code:
package data_structures;
public class RedBlackTree<E extends Comparable<E>> {
private Node<E> root;
private int count = 0;
final private Node<E> EMPTY = new Empty<E>();
public RedBlackTree() {
root = EMPTY;
}
public void add(E data) {
root = root.add(data);
count++;
root.red = false;
}
public boolean find(E data) {
return root.getNode(data) != null;
}
private class Node<E> {
public E data;
public boolean red;
public Node<E> leftChild;
public Node<E> rightChild;
/** Used by Empty */
protected Node() {
assert EMPTY == null;
}
/** Nodes always begin red */
public Node(E k) {
data = k;
red = true;
leftChild = (Node<E>) EMPTY;
rightChild = (Node<E>) EMPTY;
}
private boolean isRed() {
return red;
}
public int height(){
return 0; //returns the counts binary left most bit position to determine the height.
}
public Node<E> add(E newData) {
if(((Comparable<E>) newData).compareTo(data) == -1) {
count++;
leftChild = leftChild.add(newData);
return leftChild;
}
if(((Comparable<E>) newData).compareTo(data) == +1){
count++;
rightChild = rightChild.add(newData);
return rightChild;
}
if(((Comparable<E>) newData).compareTo(data) == 0){
return this;
}
if (leftChild.isRed() && leftChild.leftChild.isRed()) {
return balance(leftChild.leftChild, leftChild, this,
leftChild.leftChild.rightChild, leftChild.rightChild);
} else if (leftChild.isRed() && leftChild.rightChild.isRed()) {
return balance(leftChild, leftChild.rightChild, this,
leftChild.rightChild.leftChild, leftChild.rightChild.rightChild);
} else if (rightChild.isRed() && rightChild.leftChild.isRed()) {
return balance(this, rightChild.leftChild, rightChild,
rightChild.leftChild.leftChild, rightChild.leftChild.rightChild);
} else if (rightChild.isRed() && rightChild.rightChild.isRed()) {
return balance(this, rightChild, rightChild.rightChild,
rightChild.leftChild, rightChild.rightChild.leftChild);
}
return this;
}
/** Returns the node for this key, or null. */
public Node<E> getNode(E newData) {
if(((Comparable<E>) newData).compareTo(data) == -1){
return leftChild.getNode(newData);
}
if(((Comparable<E>) newData).compareTo(data) == +1){
return rightChild.getNode(newData);
}
else{
return this;
}
}
private class Empty<E> extends Node<E> {
public Empty() {
red = false;
}
public Node<E> add(E data) {
count++;
return new Node<E>(data);
}
public Node<E> getNode(E data) {
return null;
}
}
private Node<E> balance(Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e) {
a.rightChild = d;
b.leftChild = a;
b.rightChild = c;
c.leftChild = e;
a.red = false;
b.red = true;
c.red = false;
return b;
}
}
}
You can't write
Node<E> EMPTY = new Empty<E>();
because E is a generic type. You can only create an object with actual class, such as:
Node<String> EMPTY = new Empty<String>()
If you know what you are doing, you can do an ugly trick that should work with a warning
Node<E> EMPTY = new Empty();
Also, move the Empty class outside of Node.