From: Michelangelo Grigni (mic@mathcs.emory.edu)
Date: Mon Feb 20 2012 - 20:44:43 EST
I had a few repeated questions about hw2
during office hours, so I'll summarize here.
Written part, question #1, reworded:
For each k, describe an example of a
left-leaning red-black tree, with a single insertion,
such that the insertion causes at least k rotations.
Furthermore, give me an upper bound on N, the
size of your example tree (a function on k).
A specific example, a figure from my whiteboard,
where one insertion triggers k=3 rotations:
https://docs.google.com/drawings/d/1FgEBIy7R-AVqSoBtIdEGPVbCqYK08lpMgb6dyaX9ouI/edit
Program part (PRedBlackBST.java):
A repeated source issue:
the 2-argument version of "put" must be "public"
(to agree with its declaration in the parent class)
To compile, test, and turnin (in your ~/cs323/hw2 directory):
javac *.java # ignore the two warning messages
java -ea Driver # "-ea" option enables assertion checks
~cs323000/turnin
In the rotate methods, you'll need to create new nodes
(say h2 and x2) instead of reusing the existing h and x.
Here is a sketch of rotateRight(h):
Node x = h.left;
// goal: create new version x2 of x, above new version of h2.
// We create h2 first, since x2 will link to h2.
Node h2 = new Node(h.key, h.val, ?, h.right, RED);
Node x2 = new Node(x.key, x.val, ???);
return x2;
Your 3-argument "put" method correponds to "insert" in
http://mathcs.emory.edu/~cs323000/book/RedBlackLiteBST.java
But where it modifies a field of h, like:
h.left = [whatever];
you instead need to create a new version of h:
h = h.setLeft([whatever]);
The Node.setLeft method does in fact create a new Node, since
the existing Node cannot be modified.
Also you need a new version of flipColors(h). It should create three
new nodes (new versions of h and its children, with flipped colors)
and then return the new version of h.
PS: I found that "protein network" from today's
slides (41UndirectedGraphs.pdf, page 3) in this paper:
http://arxiv.org/abs/cond-mat/0105306
This archive was generated by hypermail 2.1.4 : Wed Apr 04 2012 - 17:34:17 EDT