CS计算机代考程序代写 /**

/**
* 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 data type
*/
package Midterm.Q2;

public class RBTree> {

Node root; // The root node of the tree

/**
* 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 key) {
Node node = new Node(key);

// 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 root,Node x){
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 x){
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 uncle = left ? x.parent.parent.right : x.parent.parent.left; // Get opposite “uncle” node to parent

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 x) {
// 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 x) {
// 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 search(Node.Interval key) {
// 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 find(Node x,Node.Interval v){
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 tree) {
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);
}

}