我正在研究红黑树，并编写了其完整的工作代码，如下所示。我遍历了泛型教程，并了解到使用单个类声明，可以指定一组相关方法。如何将其应用于红黑树算法？在仿制药的情况下会发生什么？如果可以的话，你能帮我吗？这是完整的代码：
import java.util.Scanner;
public class RedBlackTree {
private final int RED = 0;
private final int BLACK = 1;
private class Node {
int key = -1, color = BLACK;
Node left = nil, right = nil, parent = nil;
Node(int key) {
this.key = key;
}
}
private final Node nil = new Node(-1);
private Node root = nil;
public void printTree(Node node)
{
if (node == nil) {
return;
}
printTree(node.left);
System.out.print(((node.color==RED)?"Color: Red ":"Color: Black ")+"Key: "+node.key+" Parent: "+node.parent.key+"\n");
printTree(node.right);
}
private Node findNode(Node findNode, Node node)
{
if (root == nil) {
return null;
}
if (findNode.key < node.key) {
if (node.left != nil) {
return findNode(findNode, node.left);
}
} else if (findNode.key > node.key) {
if (node.right != nil) {
return findNode(findNode, node.right);
}
} else if (findNode.key == node.key) {
return node;
}
return null;
}
private void insert(Node node)
{
Node temp = root;
if (root == nil) {
root = node;
node.color = BLACK;
node.parent = nil;
} else {
node.color = RED;
while (true) {
if (node.key < temp.key) {
if (temp.left == nil) {
temp.left = node;
node.parent = temp;
break;
} else {
temp = temp.left;
}
} else if (node.key >= temp.key) {
if (temp.right == nil) {
temp.right = node;
node.parent = temp;
break;
} else {
temp = temp.right;
}
}
}
fixTree(node);
}
}
private void fixTree(Node node)
{
while (node.parent.color == RED) {
Node uncle = nil;
if (node.parent == node.parent.parent.left) {
uncle = node.parent.parent.right;
if (uncle != nil && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;
}
if (node == node.parent.right) {
//Double rotation needed
node = node.parent;
rotateLeft(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
//if the "else if" code hasn't executed, this
//is a case where we only need a single rotation
rotateRight(node.parent.parent);
} else {
uncle = node.parent.parent.left;
if (uncle != nil && uncle.color == RED) {
node.parent.color = BLACK;
uncle.color = BLACK;
node.parent.parent.color = RED;
node = node.parent.parent;
continue;
}
if (node == node.parent.left) {
//Double rotation needed
node = node.parent;
rotateRight(node);
}
node.parent.color = BLACK;
node.parent.parent.color = RED;
rotateLeft(node.parent.parent);
}
}
root.color = BLACK;
}
void rotateLeft(Node node)
{
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.right;
} else {
node.parent.right = node.right;
}
node.right.parent = node.parent;
node.parent = node.right;
if (node.right.left != nil) {
node.right.left.parent = node;
}
node.right = node.right.left;
node.parent.left = node;
} else {//Need to rotate root
Node right = root.right;
root.right = right.left;
right.left.parent = root;
root.parent = right;
right.left = root;
right.parent = nil;
root = right;
}
}
void rotateRight(Node node)
{
if (node.parent != nil) {
if (node == node.parent.left) {
node.parent.left = node.left;
} else {
node.parent.right = node.left;
}
node.left.parent = node.parent;
node.parent = node.left;
if (node.left.right != nil) {
node.left.right.parent = node;
}
node.left = node.left.right;
node.parent.right = node;
} else {//Need to rotate root
Node left = root.left;
root.left = root.left.right;
left.right.parent = root;
root.parent = left;
left.right = root;
left.parent = nil;
root = left;
}
}
void replace(Node target, Node with){
if(target.parent == nil){
root = with;
}else if(target == target.parent.left){
target.parent.left = with;
}else
target.parent.right = with;
with.parent = target.parent;
}
boolean delete(Node z){
if((z = findNode(z, root))==null)
return false;
Node x;
Node y = z;
int y_original_color = y.color;
if(z.left == nil){
x = z.right;
replace(z, z.right);
}else if(z.right == nil){
x = z.left;
replace(z, z.left);
}else{
y = treeMinimum(z.right);
y_original_color = y.color;
x = y.right;
if(y.parent == z)
x.parent = y;
else{
replace(y, y.right);
y.right = z.right;
y.right.parent = y;
}
replace(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if(y_original_color==BLACK)
fixDelColor(x);
return true;
}
void fixDelColor(Node x){
while(x!=root && x.color == BLACK){
if(x == x.parent.left){
Node w = x.parent.right;
if(w.color == RED){
w.color = BLACK;
x.parent.color = RED;
rotateLeft(x.parent);
w = x.parent.right;
}
if(w.left.color == BLACK && w.right.color == BLACK){
w.color = RED;
x = x.parent;
continue;
}
else if(w.right.color == BLACK){
w.left.color = BLACK;
w.color = RED;
rotateRight(w);
w = x.parent.right;
}
if(w.right.color == RED){
w.color = x.parent.color;
x.parent.color = BLACK;
w.right.color = BLACK;
rotateLeft(x.parent);
x = root;
}
}else{
Node w = x.parent.left;
if(w.color == RED){
w.color = BLACK;
x.parent.color = RED;
rotateRight(x.parent);
w = x.parent.left;
}
if(w.right.color == BLACK && w.left.color == BLACK){
w.color = RED;
x = x.parent;
continue;
}
else if(w.left.color == BLACK){
w.right.color = BLACK;
w.color = RED;
rotateLeft(w);
w = x.parent.left;
}
if(w.left.color == RED){
w.color = x.parent.color;
x.parent.color = BLACK;
w.left.color = BLACK;
rotateRight(x.parent);
x = root;
}
}
}
x.color = BLACK;
}
Node treeMinimum(Node subTreeRoot)
{
while(subTreeRoot.left!=nil){
subTreeRoot = subTreeRoot.left;
}
return subTreeRoot;
}
public void consoleUI() {
Scanner scan = new Scanner(System.in);
while (true) {
System.out.println("\n1. Insert () method\n"
+ "2. ToString() method\n"
+ "3. Contains() method\n"
+ "4. Delete() method\n"
+ "5. Exit \n");
int choice = scan.nextInt();
int item;
Node node;
switch (choice) {
case 1:
item = scan.nextInt();
while (item != 001) {
node = new Node(item);
insert(node);
item = scan.nextInt();
}
printTree(root);
break;
case 2:
printTree(root);
break;
case 3:
item = scan.nextInt();
while (item != 001) {
node = new Node(item);
System.out.println((findNode(node, root) != null) ? "found" : "not found");
item = scan.nextInt();
}
break;
case 4:
item = scan.nextInt();
while (item != 001) {
node = new Node(item);
System.out.print("\nDeleting item " + item);
if (delete(node)) {
System.out.print(": deleted!");
} else {
System.out.print(": entered item does not exist!");
}
item = scan.nextInt();
}
System.out.println();
printTree(root);
break;
case 5:
return;
}
}
}
public static void main(String[] args) {
RedBlackTree redblacktree = new RedBlackTree();
redblacktree.consoleUI();
}
}
参考方案
归纳的基本步骤：
类声明：
class RedBlackTree<KeyType extends Comparable<KeyType>, ValueType>
假设每个节点存储两个值-一个键（该键确定有序树中的位置）和一个可为空的值（不包括）。 ValueType是可选的，但它确实以树的形式提供了有效的地图实现。
（除了基于4castle的评论：用Comparable<KeyType>替换Comparable<? super KeyType>没有意义，因为不可能将非KeyType插入树中）
类实现（Node类）：用int key替换KeyType key的两种情况；添加实例变量ValueType val（可选）。如果添加了ValueType，则Node构造函数将变为：
Node(KeyValue key, KeyValue val) {
this.key = key;
this.val = val;
}
类用法（方法consoleUI），在KeyType声明期间实例化ValueType和Node，例如：
Node<Integer, String> node;
...
node = new Node(item, val);
要么
Node<Integer, Void> node;
...
node = new Node(item, null);
*结果*
import java.util.Scanner;
public class RedBlackTree<KeyType extends Comparable<KeyType>, ValueType> {
private static final int RED = 0;
private static final int BLACK = 1;
private static final Node nil = new Node(-1); ******
private Node root = nil;
private class Node {
KeyType key;
ValueType val;
color = BLACK;
Node left = nil, right = nil, parent = nil;
Node(int key) {
this.key = key;
this.val = val;
}
}
// believe remaining code is unchanged (except for adding val param)
// ...
// ...
public void consoleUI() {
Scanner scan = new Scanner(System.in);
while (true) {
System.out.println("\n1. Insert () method\n"
+ "2. ToString() method\n"
+ "3. Contains() method\n"
+ "4. Delete() method\n"
+ "5. Exit \n");
int choice = scan.nextInt();
int item;
Node<Integer, Void> node;
switch (choice) {
case 1:
item = scan.nextInt();
while (item != 001) {
node = new Node(item, null);
etc
一般建议：将您的班级分成2个。将树用法掩埋在树类本身内是没有意义的。创建一个类调用RedBlackTreeTest并将consoleUI和main移到其中。
我有一个程序，其中Main类将创建几个Node类资源，其中包含一个可运行线程，该线程在创建Node类资源时执行。我有一个Receive类使用的共享资源Node类。但是当几个Node资源从Resource类到达同步方法rcv()时，程序没有考虑互斥，并且输出是来自不同Node类不同部分的汞合金public class Main { //field //meth…
不兼容的类型:java.lang.Object无法转换为T - java这是我的代码：package datastructures; import java.util.Iterator; public class Stack<T>{ private class Node<T>{ T data; Node next; } private int size; private Node head; privat…
在Java中从TreeSet查找并返回元素 - java我有以下节点类Class Node { private int id; public int getId() { return this.id; } } 然后创建带有节点的TreeSet。接下来，我想基于ID匹配查找并返回一个Node对象。但是，每次findNode（）函数返回的是下一个到下一个Node而不是下一个。我了解这是因为两次调用了iterator.…
Java-父类正在从子类中调用方法？ - java抱歉，我还是编码的新手，可能还没有掌握所有术语。希望您仍然能理解我的问题。我想得到的输出是："Cost for Parent is: 77.77" "Cost for Child is: 33.33" 但是，我得到这个："Cost for Parent is: 33.33" "Cost f…
休眠时如何在父项保存期间将子项添加到现有项？ - java假设Parent已经与id=1存在。它已经有两个孩子了。如何编写代码： Parent parent = parentDao.getbyId(1); //here somebody added a collection of children parent.setChildren(myNewCreatedChildren) parentDao.save(par…