个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
24
4
我正在研究红黑树并编写了完整的工作代码，如下所示。我浏览了泛型教程，了解到通过单个类声明，可以指定一组相关方法。如何将它应用到我的红黑树算法中？在泛型案例中会发生什么？如果可能的话，你能帮我解决这个问题吗？这是完整的代码:
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是可选的，但它确实以树的形式提供了一个高效的 map 实现。(根据 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进入其中。
关于java - 如何在java中使红黑树泛型，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40603255/
24
4
0
我是一名优秀的程序员,十分优秀！