I have 6 Red Black trees filled with different data, but the further down I go, the more my trees get mixed up. I've commented out all but two of them, here's my code for those two trees.
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);
I'm using the same file for both trees, but using different pieces of data for the keys and values. If I print co2DateKey inorder, then it prints the keys/values for co2DateKey and co2NumKey, but if I comment out the code for co2NumKey, then co2DateKey only prints its own keys/values. I'm not sure where they're getting crossed, so any help would be appreciated.
Here's my 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);
}
}
Problem is here:
public static Node root = null; // root initialized
The root is declared static, which means it is shared between all instances of RedBlackBST. They all have the same root. Sure they will be mixed up.
Remove the static keyword.