/**
* Skeleton code for Red Black Tree.
* You are required to implement the search & insert methods, where the keys are intervals.
* You may add additional helper methods.
*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly. You might need to implement
* additional procedures, such as error checking and handling, in order to apply the
* code properly.
*
* @param
*/
package Midterm.Q2;
public class RBTree
Node
/**
* Initialize empty RBTree
*/
public RBTree() {
root = null;
}
/**
* (Safely) insert a key into the tree
* Note that if a node with duplicate key is inserted into the red-black tree,
* it will replace the old node with the same key.
*
* @param key T The key of the new node being inserted.
*/
public void insert(Node.Interval
Node
// TODO: Complete this method
// START YOUR CODE
if(node!=null){
insert(node);
}
// END YOUR CODE
}
//(1) i1. startTime < i2. startTime, or
//(2) i1. startTime = i2. startTime, and i1. endTime < i2.endTime
public void insertRecurse(Node
int startcmp = root.key.startTime.compareTo(x.key.startTime);
int endcmp = root.key.endTime.compareTo(x.key.endTime);
if(startcmp<0||(startcmp==0&&endcmp<0)){
if (root.right.key == null) {
root.right = x;
x.parent = root;
} else {
insertRecurse(root.right, x);
}
}else {
if(root.left.key==null){
root.left=x;
x.parent = root;
}else {
insertRecurse(root.left, x);
}
}
}
public void insert(Node
if (root == null) {
root = x;
} else {
if(search(x.key) != null) {
return; }
insertRecurse(root, x);
}
// Fix tree
while (x.key != root.key && x.parent.colour== Colour.RED) {//x不是root节点,且x的父节点颜色为红色
boolean left = x.parent == x.parent.parent.left; // Is parent a left node
Node
if (uncle.colour == Colour.RED) {//只重新着色,
// Case 1: Recolour
// TODO: Implement this part
// ########## YOUR CODE STARTS HERE ##########
x.parent.colour = Colour.BLACK;
uncle.colour = Colour.BLACK;
x.parent.parent.colour = Colour.RED;
// ########## YOUR CODE ENDS HERE ##########
// Check if violated further up the tree
x = x.parent.parent;
} else {
if (x.key == (left ? x.parent.right.key : x.parent.left.key)) {
// Case 2: Left Rotation, uncle is right node, x is on the right / Right Rotation, uncle is left node, x is on the left
x = x.parent;//以parent为中心左旋,变成case3
if (left) {
// Perform left rotation
if (x.key == root.key)
root = x.right; // Update root
rotateLeft(x);
} else {
// This is part of the “then” clause where left and right are swapped
// Perform right rotation
// TODO: Implement this part
// ########## YOUR CODE STARTS HERE ##########
if (x.key == root.key)
root = x.left; // Update root
rotateRight(x);
// ########## YOUR CODE ENDS HERE ##########
}
}
// Adjust colours to ensure correctness after rotation
x.parent.colour = Colour.BLACK;
x.parent.parent.colour = Colour.RED;
// Case 3 : Right Rotation, uncle is right node, x is on the left / Left Rotation, uncle is left node, x is on the right
//父亲(变黑)和祖父节点(变红),以z的祖父为中心旋转
// TODO: Complete this part
if (left) {
// Perform right rotation
// ########## YOUR CODE STARTS HERE ##########
rotateRight(x.parent.parent);
// ########## YOUR CODE ENDS HERE ##########
} else {
// This is part of the “then” clause where left and right are swapped
// Perform left rotation
// ########## YOUR CODE STARTS HERE ##########
rotateLeft(x.parent.parent);
// ########## YOUR CODE ENDS HERE ##########
}
}
}
// Ensure property 2 (root and leaves are black) holds
root.colour = Colour.BLACK;
}
public void rotateLeft(Node
// Make parent (if it exists) and right branch point to each other
if (x.parent != null) {//原先x的父节点绑定其左节点或右节点为x.right(即b节点)
// Determine whether this node is the left or right child of its parent
if (x.parent.left.key == x.key) {
x.parent.left = x.right;
} else {
x.parent.right = x.right;
}
}
//x右节点的父节点b变成原x的父节点,此时x和b的关系还未确定
x.right.parent = x.parent;
x.parent = x.right;
// Take right node’s left branch
x.right = x.parent.left;
x.right.parent = x;
// Take the place of the right node’s left branch
x.parent.left = x;
}
public void rotateRight(Node
// TODO: Implement this function
// HINT: It is the mirrored version of rotateLeft()
// ########## YOUR CODE STARTS HERE ##########
if(x!=null){
if(x.key == x.parent.left.key){
x.parent.left = x.left;
}else{
x.parent.right = x.left;
}
}
x.left.parent = x.parent;
x.parent = x.left;
x.left = x.parent.right;
x.left.parent = x;
x.parent.right = x;
// ########## YOUR CODE ENDS HERE ##########
}
/**
* Returns a node if the key of the node is {@code key}.
* Otherwise, return null.
*
* @param key T The key we are looking for
* @return
*/
public Node
// TODO: Complete this method
// START YOUR CODE
return find(root,key);
// END YOUR CODE
}
//(1) i1. startTime < i2. startTime, or
//(2) i1. startTime = i2. startTime, and i1. endTime < i2.endTime
public Node
if (x.key == null){
return null;
}
int startcmp = v.startTime.compareTo(x.key.startTime);
int endcmp = v.endTime.compareTo(x.key.endTime);
if (startcmp<0||(startcmp==0&&endcmp<0))
return find(x.left, v);
else if(startcmp==0&&endcmp==0)
return x;
else
return find(x.right, v);
}
/**
* Return the result of a pre-order traversal of the tree
*
* @param tree Tree we want to pre-order traverse
* @return pre-order traversed tree
*/
private String preOrder(Node
if (tree != null && tree.key != null) {
String leftStr = preOrder(tree.left);
String rightStr = preOrder(tree.right);
return “(“+tree.key.startTime + “,” + tree.key.endTime +”)” + (leftStr.isEmpty() ? leftStr : ” ” + leftStr)
+ (rightStr.isEmpty() ? rightStr : ” ” + rightStr);
}
return “”;
}
public String preOrder() {
return preOrder(root);
}
}