# 数据结构代写 | CS 61BL Data Structures & Programming Methodology

(1) Mechanical Balanced Search Trees

We learned that !-” Trees have a one-to-one correspondence with Left-Leaning Red-Black
Trees. For each subpart in this question, take the &-‘ Tree given in the left column and perform the
indicated operation on it, drawing the resulting &-‘ Tree below the given tree. Then convert both
the given &-‘ Tree and the &-‘ Tree you drew into LLRB Trees, drawing them in the right column
next to their counterparts.

Indicate a node is red by putting an asterisk (*) next to it. You must use the conventions and
procedures we taught in lab this summer. Only your ﬁnal answer within the boxes will be graded;
perform any scratch work (which will not be graded) outside of the boxes.

（2) Heaps Spark Joy

Shown below is a binary Min Heap, in which each symbol represents a node in the heap. The
values contained within the nodes are comparable, and are not necessarily unique (except for the
allowance of duplicate values here, all of the heap invariants from lab apply).

For each of the following questions, select all possible relationships that could occur between the
values represented by the letter and symbol shown. IMPORTANT: For this entire question, assume
that X>Y . Erase any undesired markings from boxes completely if you change your answer.

（3) #BARTable

Assume the standard java.util.LinkedList is imported everywhere as needed in this question.
Bay Area Rapid Transit is the local rail and subway transportation system. From the nearby

Downtown Berkeley station, you can travel to a number of exciting destinations in varying amounts
of time. Our goal here is to print the names of all the stations, ordered by their travel times from
Berkeley (from shortest to longest). A Station is represented as:

public class Station {
String name;
int travelTime;
public Station(String name, int travelTime) {
this.name = name;
this.travelTime = travelTime;
}
}

Note that the travelTime of a Station represents the travel time from the Berkeley station (not
from another neighboring station).

E-mail: itcsdx@outlook.com  微信:itcsdx