红黑树合并？

Question

我有 6 棵红黑树，里面装满了不同的数据，但我越往下走，我的树就越混在一起。我已经注释掉了除了其中两个之外的所有内容，这是我对这两棵树的代码。

Scanner co2DateFile = new Scanner(new File("co2.csv"));
Scanner co2NumFile = new Scanner(new File("co2.csv"));

RedBlackBST co2DateKey = new RedBlackBST();
RedBlackBST co2NumKey = new RedBlackBST();

while (co2DateFile.hasNextLine()) {                 
    String[] line3 = co2DateFile.nextLine().split(",");
    if (line3[0].equals("World")) {
        LocalDate date = parseDateString(line3[2]);
        String stringDate = date.toString();
        co2DateKey.root = co2DateKey.put(co2DateKey.root, stringDate, line3[3]);
    }
}
        
while (co2NumFile.hasNextLine()) {                  
    String[] line4 = co2NumFile.nextLine().split(",");
    if (line4[0].equals("World")) {
        co2NumKey.root = co2NumKey.put(co2NumKey.root, line4[3], line4[2]);
    }
}

co2DateKey.inorder(co2DateKey.root);

我对两棵树使用相同的文件，但对键和值使用不同的数据。如果我按顺序打印 co2DateKey，那么它会为 co2DateKey 和 co2NumKey 打印 keys/values，但是如果我注释掉 co2NumKey 的代码，那么 co2DateKey 只会打印它自己的 keys/values。我不确定他们在哪里越过，所以任何帮助将不胜感激。

这是我的 RedBlackBST class:

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.io.File;
import java.io.FileNotFoundException;

class Node
{
    Node left;
    Node right;     // initializing Nodes and variables
    String key;
    String value;
    String type;
    
    boolean color;          // true means color is red, false is black
     
    Node(String key, String value)
    {
        this.key = key;
        this.value = value;
        left = null;
        right = null;
         
        color = true;       // new nodes are always red
    }
}
 
public class RedBlackBST {
 
    public static Node root = null;     // root initialized
     
    public Node rotateLeft(Node myNode)
    {
        Node child = myNode.right;
        Node childLeft = child.left;        // assigning variables
 
        child.left = myNode;    
        myNode.right = childLeft;           // rotating nodes to the left
 
        return child;
    }
 
    public Node rotateRight(Node myNode)
    {
        Node child = myNode.left;       // assigning variables
        Node childRight = child.right;
 
        child.right = myNode;           // rotating nodes to the right
        myNode.left = childRight;
 
        return child;
    }
    
    public void flipColors(Node x, Node y)  // flipping colors of two given nodes
    {
        boolean temp = x.color;                 // uses temp to store color of first node
        x.color = y.color;              // first node takes second node's color
        y.color = temp;                 // second node takes first node's color
    }
 
    public String get(String key) {
        return get(root, key);              // this function is called from main, which calls recursive get
    }

    private String get(Node x, String key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);     // compares current key with the one we are searching for
            if (cmp < 0) 
                x = x.left;
            else if (cmp > 0)
                x = x.right;                // recursively searches through tree until key is found
            else              
                return x.value;         // returns value associated with said key
        }
        return null;
    }

    public boolean getColor(String key) {
        return getColor(root, key);     // this function is called from main, which calls recursive getColor
    }
    
    private boolean getColor(Node x, String key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);     // same idea as get
            if (cmp < 0) 
                x = x.left;
            else if (cmp > 0)       // recursively searches through tree to find key
                x = x.right;
            else              
                return x.color;     // returns color of node associated with said key
        }
        return false;
    }
    
    public boolean isRed(Node myNode)
    {
        if (myNode == null)             // checks color of node passed into function, returns true if red
            return false;
        return (myNode.color == true);
    }
 
    // insertion into Left Leaning Red Black Tree.
    public Node put(Node myNode, String key, String value)
    {
        // inserting node, checks for violations to left leaning red black tree come next
        if (myNode == null)
            return new Node(key, value);
 
        if (key.compareTo(myNode.key) < 0)                  // compares keys, recursive calls to find proper spot
            myNode.left = put(myNode.left, key, value);
         
        else if (key.compareTo(myNode.key) > 0)
            myNode.right = put(myNode.right, key, value);
        
        else if (key.equals(myNode.key) == true)            // if key is already in tree, numeric value is replaced
            myNode.value = value;                   
         
        else
            return myNode;
 
 
        // case 1.
        // when right child is Red but left child is
        // Black or doesn't exist.
        if (isRed(myNode.right) && !isRed(myNode.left))
        {
            myNode = rotateLeft(myNode);                    // left rotate the node to make it into valid structure.
 
            flipColors(myNode, myNode.left);                // swap the colors as the child node should always be red
 
        }
 
        // case 2
        // when left child as well as left grand child are Red
        if (isRed(myNode.left) && isRed(myNode.left.left))
        {
            myNode = rotateRight(myNode);                           // right rotate the current node to make it into a valid structure, then flip colors
            flipColors(myNode, myNode.right);
        }
 
 
        // case 3
        // when both left and right child are Red in color.
        if (isRed(myNode.left) && isRed(myNode.right))
        {
            myNode.color = !myNode.color;                   // invert the color of node as well it's left and right child
 
            myNode.left.color = false;                      // change the color to black
            myNode.right.color = false;
        }
 
        return myNode;
    }
 
    
    public Iterable<String> keys(Node node, Queue<String> queue) {      // uses inorder traversal to put keys in right order
        if (node != null)
        {
            keys(node.left, queue);
            queue.add(node.key);            // adds each key to queue in correct order
            keys(node.right, queue);
        }
        return queue;       // returns queue after all keys have been added
    }
    
    public String highest(Node node) {
        Node current = node;
        while (current.right != null) {
            current = current.right;
        }
        return current.key;
    }
    
    void inorder(Node node)
    {
        if (node != null)
        {
            inorder(node.left);
            System.out.println(node.key + " " + node.value);
            inorder(node.right);
        }
    }

Answer 1

问题在这里：

public static Node root = null;     // root initialized

根声明为 static，这意味着它在 RedBlackBST 的所有实例之间共享。他们都有同根。当然他们会混淆。

删除 static 关键字。

红黑树合并？

Red Black Trees getting merged?

java

red-black-tree