In Java for the RedBlackTree how would you make the InsertFixup and RemoveFixup with the following RedBlackTree and BInNode 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 RedBlackTree { private BinNode root; private BinNode nil; public RedBlackTree() { nil = new BinNode(); nil.setColor(false); // Black color for NIL nodes root = nil; } public BinNode getRoot() { return this.root; } public void insert(String data) { BinNode newNode = new BinNode(data); newNode.setColor(true); // New nodes are always red newNode.setLeft(nil); newNode.setRight(nil); BinNode y = null; BinNode x = this.root; while (x != nil) { y = x; int comparison = data.compareTo(x.getData()); if (comparison < 0) { x = x.getLeft(); } else { x = x.getRight(); } } newNode.setParent(y); if (y == null) { this.root = newNode; // Tree was empty } else if (data.compareTo(y.getData()) < 0) { y.setLeft(newNode); } else { y.setRight(newNode); } insertFixup(newNode); } public void remove(String key) { BinNode z = search(key); if (z != nil) { remove(z); } } private void remove(BinNode z) { BinNode y = z; BinNode x; boolean yOriginalColor = y.getColor(); if (z.getLeft() == nil) { x = z.getRight(); transplant(z, z.getRight()); } else if (z.getRight() == nil) { x = z.getLeft(); transplant(z, z.getLeft()); } else { y = minimum(z.getRight()); yOriginalColor = y.getColor(); x = y.getRight(); if (y.getParent() == z) { x.setParent(y); } else { transplant(y, y.getRight()); y.setRight(z.getRight()); y.getRight().setParent(y); } transplant(z, y); y.setLeft(z.getLeft()); y.getLeft().setParent(y); y.setColor(z.getColor()); } if (yOriginalColor == false) { removeFixup(x); } } // Other Red-Black Tree helper methods go here // ... // Helper function to fix violations of Red-Black Tree properties after insertion private void insertFixup(BinNode z) { // Implementation of fixup procedure // ... } // Helper function to fix violations of Red-Black Tree properties after removal private void removeFixup(BinNode x) { // Implementation of fixup procedure // ... } // Other Red-Black Tree-specific methods go here // ... // Helper function to find the minimum node in a subtree private BinNode minimum(BinNode x) { while (x.getLeft() != nil) { x = x.getLeft(); } return x; } // Helper function to transplant a subtree private void transplant(BinNode u, BinNode v) { if (u.getParent() == nil) { this.root = v; } else if (u == u.getParent().getLeft()) { u.getParent().setLeft(v); } else { u.getParent().setRight(v); } v.setParent(u.getParent()); } // Other Red-Black Tree-specific methods go here // ...
In Java for the RedBlackTree how would you make the InsertFixup and RemoveFixup with the following RedBlackTree and BInNode 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 RedBlackTree {
private BinNode root;
private BinNode nil;
public RedBlackTree() {
nil = new BinNode();
nil.setColor(false); // Black color for NIL nodes
root = nil;
}
public BinNode getRoot() {
return this.root;
}
public void insert(String data) {
BinNode newNode = new BinNode(data);
newNode.setColor(true); // New nodes are always red
newNode.setLeft(nil);
newNode.setRight(nil);
BinNode y = null;
BinNode x = this.root;
while (x != nil) {
y = x;
int comparison = data.compareTo(x.getData());
if (comparison < 0) {
x = x.getLeft();
} else {
x = x.getRight();
}
}
newNode.setParent(y);
if (y == null) {
this.root = newNode; // Tree was empty
} else if (data.compareTo(y.getData()) < 0) {
y.setLeft(newNode);
} else {
y.setRight(newNode);
}
insertFixup(newNode);
}
public void remove(String key) {
BinNode z = search(key);
if (z != nil) {
remove(z);
}
}
private void remove(BinNode z) {
BinNode y = z;
BinNode x;
boolean yOriginalColor = y.getColor();
if (z.getLeft() == nil) {
x = z.getRight();
transplant(z, z.getRight());
} else if (z.getRight() == nil) {
x = z.getLeft();
transplant(z, z.getLeft());
} else {
y = minimum(z.getRight());
yOriginalColor = y.getColor();
x = y.getRight();
if (y.getParent() == z) {
x.setParent(y);
} else {
transplant(y, y.getRight());
y.setRight(z.getRight());
y.getRight().setParent(y);
}
transplant(z, y);
y.setLeft(z.getLeft());
y.getLeft().setParent(y);
y.setColor(z.getColor());
}
if (yOriginalColor == false) {
removeFixup(x);
}
}
// Other Red-Black Tree helper methods go here
// ...
// Helper function to fix violations of Red-Black Tree properties after insertion
private void insertFixup(BinNode z) {
// Implementation of fixup procedure
// ...
}
// Helper function to fix violations of Red-Black Tree properties after removal
private void removeFixup(BinNode x) {
// Implementation of fixup procedure
// ...
}
// Other Red-Black Tree-specific methods go here
// ...
// Helper function to find the minimum node in a subtree
private BinNode minimum(BinNode x) {
while (x.getLeft() != nil) {
x = x.getLeft();
}
return x;
}
// Helper function to transplant a subtree
private void transplant(BinNode u, BinNode v) {
if (u.getParent() == nil) {
this.root = v;
} else if (u == u.getParent().getLeft()) {
u.getParent().setLeft(v);
} else {
u.getParent().setRight(v);
}
v.setParent(u.getParent());
}
// Other Red-Black Tree-specific methods go here
// ...
}
Step by step
Solved in 6 steps with 2 images
