1
データを挿入しようとしましたが、ドライバが動作していません。インセットが赤く強調表示され、正しいデータタイプではないことを伝えています。ジェネリック型のNodeを設定するにはどうすればいいですか？一般的なRedBlackドライバ
public class Driver {
public static <E> void main(String[] args){
RedBlack<Integer> rb = new RedBlack<Integer>();
Node<Integer> item=32;
rb.insert(item);
}//close main
}//close driver
REDBLACKのCODE：
import java.util.NoSuchElementException;
public class RedBlack<E extends Comparable<? super E>>{
////////////////////////////////SETUP//////////////////////////////////////////
private final static int Red=0;
private final static int Black=1;
private Node<E> nil;
private Node<E> root;
public RedBlack() {
nil=new Node<E>(null);
nil.left=nil.right=nil;
root=new Node<E>(null);
root.left=root.right=nil;
}
static class Node<E>{
Node(E theData){
this(theData,null,null);
}
Node(E theData,Node<E> lt,Node<E> rt){
data=theData;
left=lt;
right=rt;
color=RedBlack.Black;
}
E data; // The data in the Node
Node<E> left; // Left child
Node<E> right; // Right child
Node<E> parent; // Above Node
int color=Black; // Color of Node
}
////////////////////////////////INSERT////////////////////////////////
public void insert(Node<E> item) {
if(item==null) {
throw new NoSuchElementException("Inset was null");
}//close if
Node<E> temp=root;
if(root==nil) {
root= item;
item.color=Black;
item.parent=nil;
}//close if
else {
item.color=Red;
while(item!=root) {
if(compare(item.data,temp.data)<0) {
if(temp.right==nil) {
temp.right=item;
item.parent=temp;
break;
}//close if
else {
temp=temp.right;
}//close else
}//close if
else if(compare(item.data,temp.data)>0){
if(temp.left==nil) {
temp.left=item;
item.parent=temp;
break;
}//close if
else {
temp=temp.left;
}//close else
}//close else if
}//close while
adjustment(item);
}//close else
}//close insert
private void adjustment(Node<E> item) {
while(item.parent.color==Red) {
Node<E> uncle;
if(item.parent==item.parent.parent.left) {
uncle=item.parent.parent.right;
if(uncle.color==Red && uncle!=nil) { //the uncle needs to exist and and be red to recolored
item.parent.color=Black;
item.parent.parent.color=Red;
uncle.color=Black;
continue;
}//close if
if(item==item.parent.right) {
item=item.parent;
lR(item);
}//close if
item.parent.color=Black;
item.parent.parent.color=Red;
rR(item.parent.parent);
}//close if
else {
uncle=item.parent.parent.left;
if(uncle.color==Red&&uncle!=nil) {
item.parent.color=Black;
item.parent.parent.color=Red;
uncle.color=Black;
continue;
}//close if
if(item==item.parent.left) {
item=item.parent;
rR(item);
}//close if
item.parent.color=Black;
item.parent.parent.color=Red;
lR(item.parent.parent);
}//close else
}//close while
root.color=Black;
}//close adjustment
private int compare(E item,E x) {
if(x==root) {
return 1; //same as root will be placed on the right
}//close if
else return item.compareTo(x);
}//close compare
////////////////////////////////ROTATE////////////////////////////////
private void rR(Node<E> node) {
if(node.parent!=nil) {
if(node==node.parent.left) {
node.parent.left=node.left;
}//close if
else {
node.parent.right=node.left;
}//close else
node.left.parent=node.parent;
node.parent=node.left;
if(node.left.right!=nil) {
node.left.right.parent=node;
}//close if
Node<E> left=root.left;
root.left=root.left.right;
left.right.parent=nil;
root=left;
}//close if
}//close rR
private void lR(Node<E> node) {
if(node.parent!=nil) {
if(node==node.parent.left) {
node.parent.left=node.right;
}//close if
else {
node.parent.right=node.right;
}//close else
node.right.parent=node.parent;
node.parent=node.parent;
if(node.right.left!=nil) {
node.right.left.parent=node;
}//close if
node.right=node.right.left;
node.parent.left=node;
}//close if
else {
Node<E> right=root.right;
root.right=right.left;
right.left.parent=root;
root.parent=right;
right.left=root;
right.parent=nil;
root=right;
}//close else
}//close lR
////////////////////////////////DELETE////////////////////////////////
public void delete(Node<E> node) {
if((node=find(node,root))==null) {
System.out.println("Node does not exist");
return;
}
Node<E> node2;
Node<E> temp=node;
int tempColor=node.color;
if(node.left==nil) {
node2=node.right;
switchNodes(node,node.right);
}
else if(node.right==nil) {
node2=node.left;
switchNodes(node,node.left);
}
else {
temp=subTree(node.right);
tempColor=temp.color;
node2=temp.right;
if(temp.parent==node) {
node2.parent=temp;
}
else {
switchNodes(temp,temp.right);
temp.right=node.right;
temp.right.parent=temp;
}
switchNodes(node,temp);
temp.left=node.left;
temp.left.parent=temp;
temp.color=node.color;
}
if(tempColor==Black) {
deleteAdjustment(node2);
}
}//close delete
public void switchNodes(Node<E> node,Node<E> nodeOther) {
if(node.parent==nil) {
root=nodeOther;
}
else if(node==node.parent.left) {
nodeOther.parent.left=nodeOther;
}
else {
node.parent.right=nodeOther;
}
nodeOther.parent=node.parent;
}
public Node<E> subTree(Node<E> subRoot) {
while(subRoot!=nil) {
subRoot=subRoot.left;
}
return subRoot;
}
public void deleteAdjustment(Node<E> node) {
while(node!=root && node.color==Black) {
if(node==node.parent.left) {
Node<E> brother=node.parent.right;
if(brother.color==Red) {
brother.color=Black;
node.parent.color=Red;
lR(node.parent);
brother=node.parent.right;
}//close if
if(brother.left.color==Black && brother.right.color==Black) {
brother.color=Red;
node=node.parent;
continue;
}//close if
else if(brother.right.color==Black) {
brother.left.color=Black;
brother.color=Red;
rR(brother);
brother=node.parent.right;
}//close else if
if(brother.right.color==Red) {
brother.color=node.parent.color;
node.parent.color=Black;
brother.right.color=Black;
lR(node.parent);
node=root;
}//close if
}//close if
else {
Node<E> brother=node.parent.left;
if(brother.color==Red) {
brother.color=Black;
node.parent.color=Red;
rR(node.parent);
brother=node.parent.left;
}//close if
if(brother.right.color==Black&&brother.left.color==Black) {
brother.color=Red;
node=node.parent;
continue;
}//close if
else if(brother.left.color==Black) {
brother.right.color=Black;
brother.color=Red;
lR(brother);
brother=node.parent.left;
}//close else if
if(brother.left.color==Red) {
brother.color=node.parent.color;
node.parent.color=Black;
brother.left.color=Black;
rR(node.parent);
node=root;
}//close if
}//close else
}//close while
node.color=Black;
}//close deleteAdjustment
////////////////////////////////FIND////////////////////////////////
public Node<E> find(Node<E> item) {
if(item==null) {
throw new NoSuchElementException("Item was null.");
}//close if
return find(item,root);
}//close find
private Node<E> find(Node<E> findNode,Node<E> node) {
if(root==nil) {
return null;
}//close if
if(compare(findNode.data,node.data)<0) {
if (node.right != nil) {
return find(findNode,node.right);
}
}
else if(compare(findNode.data,node.data)>0) {
if (node.left != nil) {
return find(findNode,node.left);
}//close if
}//close if
else if(findNode.data==node.data) {
return node;
}
return null;
}
////////////////////////////////Print////////////////////////////////
public void printInOrder() {
if(root==nil) {
return;
}//close if
System.out.print("Key: "+root.data+"-Black");
printTree(root);
}//close printInOrder
public void printTree(Node<E> node) {
if(node==nil) {
return;
}//close if
printTree(node.left);
if(node.color==Black) {
System.out.print("Key: "+node.data+"-Black");
}//close if
else {
System.out.print("Key: "+node.data+"-Red");
}//close else
printTree(node.right);
}//close printTree
}//close class