In Java how would you create a RedBlackTree class with Insert and Remove based off this BinNode Class and this BinaryTree Class? public class BinNode { private String data; private BinNode left; private BinNode right; private int height; //height field as with AVL tree or Red Black Tree private boolean color; //Needed for Red Black Tree public BinNode(){ data = ""; left = null; right = null; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } public BinNode(String d){ data = d; left = null; right = null; } public void setData(String d){ this.data = d; } public String getData(){ return this.data; } public void setLeft(BinNode l){ this.left = l; } public BinNode getLeft(){ return this.left; } public void setRight(BinNode r){ this.right = r; } public BinNode getRight(){ return this.right; } } public class BinaryTree { private BinNode root; private BinNode curr; /* Function to traverse right */ public void goRight() { this.curr = this.curr.getRight(); } public BinaryTree() { root = new BinNode(); curr = new BinNode(); } public BinNode getRoot(){ return this.root; } public void setRoot(BinNode r) {this.root = r;} /* Function to check if tree is empty */ public boolean isEmpty() { return this.root == null; } /* Functions to insert data */ public void insert(String data) { this.root = insert(this.root, data); } //done /* Function to insert data recursively */ private BinNode insert(BinNode node, String data) { if (node == null) node = new BinNode(data); else { int i = node.getData().compareTo(data); if (i < 0) { // Go right node.setRight(insert(node.getRight(), data)); } else if (i >= 0) { // Go left node.setLeft(insert(node.getLeft(), data)); } // write this! } return node; } /* Function to count number of nodes */ public int countNodes() { return countNodes(this.root); } /* Function to count number of nodes recursively */ private int countNodes(BinNode r) { if (r == null) { return 0; // If the current node is null, there are no nodes to count. } int leftCount = countNodes(r.getLeft()); // Count nodes in the left subtree int rightCount = countNodes(r.getRight()); // Count nodes in the right subtree // Add 1 to count the current node itself return 1 + leftCount + rightCount; } /* Function to search for an element */ public BinNode search(String val) { return search(this.root, val); } /* Function to search for an element recursively */ private BinNode search(BinNode r, String val) { // Base case: If the current node is null, the value is not found. if (r == null) { return null; } int comparison = val.compareTo(r.getData()); if (comparison < 0) { // Value is smaller, so search in the left subtree. return search(r.getLeft(), val); } else if (comparison > 0) { // Value is larger, so search in the right subtree. return search(r.getRight(), val); } else { // Value is equal to the current node's data, so it's found. //this.curr = r; return r; } } /* Function for inorder traversal */ public void inorder() { inorder(this.root); } private void inorder(BinNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() +" "); inorder(r.getRight()); } } /* Function for preorder traversal */ public void preorder() { preorder(root); } private void preorder(BinNode r) { if (r != null) { System.out.print(r.getData() +" "); preorder(r.getLeft()); preorder(r.getRight()); } } /* Function for postorder traversal */ public void postorder() { postorder(root); } private void postorder(BinNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() +" "); } } // find the in-order successor of a given node public BinNode findInorderSuccessor(BinNode node) { BinNode current = node.getRight(); while (current.getLeft() != null) { current = current.getLeft(); } return current; } //Remove function public void remove(String key) { // Find the node to be removed and its parent BinNode parent = null; BinNode n = this.root; while (n != null && !n.getData().equals(key)) { parent = n; if (key.compareTo(n.getData()) < 0) { n = n.getLeft(); } else { n = n.getRight(); } } if (n == null) { // Key not found, nothing to remove return; } // Case 1: Node with no children if (n.getLeft() == null && n.getRight() == null) { if (parent == null) { // Removing the root node this.root = null; } else if (parent.getLeft() == n) { parent.setLeft(null); } else { parent.setRight(null); } } // Case 2: Node with one child else if (n.getLeft() == null || n.getRight() == null) { BinNode child = (n.getLeft() != null) ? n.getLeft() : n.getRight(); if (n == this.root) { this.root = child; } else if (parent.getLeft() == n) { parent.setLeft(child); } else { parent.setRight(child); } } // Case 3: Node with two children else { BinNode successor = findInorderSuccessor(n); n.setData(successor.getData()); remove(successor.getData()); // Recursively remove the successor } } }
In Java how would you create a RedBlackTree class with Insert and Remove based off this BinNode Class and this BinaryTree Class?
public class BinNode
{
private String data;
private BinNode left;
private BinNode right;
private int height; //height field as with AVL tree or Red Black Tree
private boolean color; //Needed for Red Black Tree
public BinNode(){
data = "";
left = null;
right = null;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public BinNode(String d){
data = d;
left = null;
right = null;
}
public void setData(String d){
this.data = d;
}
public String getData(){
return this.data;
}
public void setLeft(BinNode l){
this.left = l;
}
public BinNode getLeft(){
return this.left;
}
public void setRight(BinNode r){
this.right = r;
}
public BinNode getRight(){
return this.right;
}
}
public class BinaryTree
{
private BinNode root;
private BinNode curr;
/* Function to traverse right */
public void goRight() {
this.curr = this.curr.getRight();
}
public BinaryTree()
{
root = new BinNode();
curr = new BinNode();
}
public BinNode getRoot(){
return this.root;
}
public void setRoot(BinNode r) {this.root = r;}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return this.root == null;
}
/* Functions to insert data */
public void insert(String data)
{
this.root = insert(this.root, data);
} //done
/* Function to insert data recursively */
private BinNode insert(BinNode node, String data)
{
if (node == null)
node = new BinNode(data);
else
{
int i = node.getData().compareTo(data);
if (i < 0) {
// Go right
node.setRight(insert(node.getRight(), data));
} else if (i >= 0) {
// Go left
node.setLeft(insert(node.getLeft(), data));
}
// write this!
}
return node;
}
/* Function to count number of nodes */
public int countNodes()
{
return countNodes(this.root);
}
/* Function to count number of nodes recursively */
private int countNodes(BinNode r)
{
if (r == null) {
return 0; // If the current node is null, there are no nodes to count.
}
int leftCount = countNodes(r.getLeft()); // Count nodes in the left subtree
int rightCount = countNodes(r.getRight()); // Count nodes in the right subtree
// Add 1 to count the current node itself
return 1 + leftCount + rightCount;
}
/* Function to search for an element */
public BinNode search(String val)
{
return search(this.root, val);
}
/* Function to search for an element recursively */
private BinNode search(BinNode r, String val)
{
// Base case: If the current node is null, the value is not found.
if (r == null) {
return null;
}
int comparison = val.compareTo(r.getData());
if (comparison < 0) {
// Value is smaller, so search in the left subtree.
return search(r.getLeft(), val);
} else if (comparison > 0) {
// Value is larger, so search in the right subtree.
return search(r.getRight(), val);
} else {
// Value is equal to the current node's data, so it's found.
//this.curr = r;
return r;
}
}
/* Function for inorder traversal */
public void inorder()
{
inorder(this.root);
}
private void inorder(BinNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BinNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BinNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
// find the in-order successor of a given node
public BinNode findInorderSuccessor(BinNode node) {
BinNode current = node.getRight();
while (current.getLeft() != null) {
current = current.getLeft();
}
return current;
}
//Remove function
public void remove(String key) {
// Find the node to be removed and its parent
BinNode parent = null;
BinNode n = this.root;
while (n != null && !n.getData().equals(key)) {
parent = n;
if (key.compareTo(n.getData()) < 0) {
n = n.getLeft();
} else {
n = n.getRight();
}
}
if (n == null) {
// Key not found, nothing to remove
return;
}
// Case 1: Node with no children
if (n.getLeft() == null && n.getRight() == null) {
if (parent == null) {
// Removing the root node
this.root = null;
} else if (parent.getLeft() == n) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
}
// Case 2: Node with one child
else if (n.getLeft() == null || n.getRight() == null) {
BinNode child = (n.getLeft() != null) ? n.getLeft() : n.getRight();
if (n == this.root) {
this.root = child;
} else if (parent.getLeft() == n) {
parent.setLeft(child);
} else {
parent.setRight(child);
}
}
// Case 3: Node with two children
else {
BinNode successor = findInorderSuccessor(n);
n.setData(successor.getData());
remove(successor.getData()); // Recursively remove the successor
}
}
}
Step by step
Solved in 3 steps
