Implementation of the RBTreeMap (Red-Black Tree) class.

Finish the implementation of the RBTreeMap

The partial implementation of the class is given below: Complete the methods that say "// your implementation" or "// your implementation using the psudeo code" Psuedo code that MUST BE FOLLOWED is provided in most instances.

import java.util.Comparator; public class RBTreeMap extends AbstractMap { private int n; private static final boolean RED = true; private static final boolean BLACK = false; private RBNode root; private RBNode NIL = new RBNode(); private RBNodeComparator comp = new RBNodeComparator(); RBTreeMap() { // your implementation } public int size() {return n;} public boolean isEmpty() {return n == 0;} public Object get(Object key) { // your implementation } public Object put(Object key, Object value) { // your implementation using the psudeo code Case 1: z's uncle is RED p<---z.parent pp<---p.parent if(p = pp.left) y<---pp.right else y<---pp.left p.color<---BLACK y.color<---BLACK pp.color<---RED z<---pp(Restart the recursive restoration) Case 2: z's uncle is BLACK, z is right child p<---z.parent left.rotate(p) Case 3: z's uncle is BLACK, z is left child p<---z.parent pp<---p.parent p.color<---BLACK pp.color<---RED right_rotation(pp) } private void insert_fixup(RBNode r, RBNode z) { // your implementation using the psuedo code p<---z.parent while(p.color = RED){ pp<---p.parent if(p = pp.left){ y<---pp.right} if(y.color = RED){ Case 1(z)} else{ if(z = p.right){ z<---Case 2(z)} Case 3(z) }else{ y<--pp.left if(y.color = RED){ Case 1(z)} else{ if(z = p.left){ z<---Case 2(z)} Case 3(z) } } } root.color = BLACK } private RBNode left_rotate(RBNode x) { // your implementation using the psuedo code p<---x.parent y<---x.right v<---y.left x.right<---v if(v != NIL) v.parent<---p if(p = null) root<---y else if(x = p.left) p.left<---y else p.right<---y y.left<---x x.parent<---y // return the root of the rotated subtree } private RBNode right_rotate(RBNode y) { // your implementation should be similar to the psuedo code for left_rotate // return the root of the rotated subtree } public Object remove(Object key) { return null; }

 private class RBNode extends MapEntry { private boolean color; private RBNode left; private RBNode right; private RBNode parent; RBNode() {// NIL Node super(null, null); color = BLACK; parent = null; left = null; right = null; } RBNode(String key, String value) { super(key, value); color = RED; } protected RBNode getLeft() {return left;} protected RBNode getRight() {return right;} protected RBNode getParent() {return parent;} protected void setLeft(RBNode l) {left = l;} protected void setRight(RBNode r) {right = r;} protected void setParent(RBNode p) {parent = p;} protected boolean getColor() {return color;} protected void setColor(boolean c) {color = c;} } private class RBNodeComparator implements Comparator { public int compare(Object a, Object b) { String aa = ((RBNode)a).getKey(); String bb = ((RBNode)b).getKey(); if (a == null && b == null) return 0; else if (a == null) return -1; else if (b == null) return 1; else { int size = Math.min(aa.length(), bb.length()); for (int i = 0; i bb.charAt(i)) return 1; else if (aa.charAt(i) < bb.charAt(i)) return -1; } // first size characters are equal to each other if (size == aa.length()) return -1; return 1; } } } } public abstract class AbstractMap { public abstract Object get(Object key); public abstract Object put(Object key, Object value); public abstract Object remove(Object key); public abstract boolean isEmpty(); public abstract int size(); }

public class MapEntry {

private String key;

private String value;

public MapEntry() { this(null,null); }

public MapEntry(String k, String v) { this.key = k; this.value = v; }

public String getKey() { return key; }

public String getValue() { return value; }

public void setKey(String key) { this.key = key; }

public Object setValue(String value) { String old = this.getValue(); this.value = value; return old; }

public int hashCode() {

if(key == null) return 0; int h = 0;

for(int i = 0; i < key.length(); i++) { h = (h << 5) | (h >>> 27); h+= (int) key.charAt(i); }

return h;

}

}