Could someone check that my code works? I\'ve written junit tests, but my rotate
ID: 3820805 • Letter: C
Question
Could someone check that my code works? I've written junit tests, but my rotateLeft and rotateRight method checks are not working.
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
/** OrderedMap implementation AVL Tree Map.
* @author....
* @param type for keys.
* @param type for values.
*/
public class AvlTreeMap, V> implements OrderedMap {
//Inner node class
private class Node { //change back to private
Node left;
Node right;
K key;
V value;
int height;
//constructor node creation
Node(K k, V v) {
this.key = k;
this.value = v;
this.height = 0;
this.left = null;
this.right = null;
}
public String toString() {
return "Node this.value + ">";
}
}
private Node root;
private int size;
private StringBuilder stringBuilder;
public V rootValue() {
return this.root.value;
}
public K rootKey() {
return this.root.key;
}
@Override
public int size() {
return this.size;
}
/**
* Get height of given node.
* @param n node.
* @return height of subtree/tree.
*/
private int height(Node n) {
if (n == null) {
return -1;
}
return n.height;
}
/** Get balance factor of a node.
* @param n the node
* @return the balance factor
*/
private int getBalance(Node n) {
if (n == null) {
return 0;
}
return height(n.left) - height(n.right);
}
/** Return node for given key.
* @param k the key.
* @return node for the given key.
*/
private Node find(K k) {
if (k == null) {
throw new IllegalArgumentException("cannot handle null key");
}
Node n = this.root;
while (n != null) {
int cmp = k.compareTo(n.key);
if (cmp < 0) {
n = n.left;
} else if (cmp > 0) {
n = n.right;
} else {
return n;
}
}
return null;
}
@Override
public boolean has(K k) {
if (k == null) {
return false;
}
return this.find(k) != null;
}
/** find for sure
* @param k the key
* @return node for given key
* @throws IllegalArgumentException
*/
private Node findForSure(K k) {
Node n = this.find(k);
if (n == null) {
throw new IllegalArgumentException("cannot find key " + k);
}
return n;
}
/**
* Update the value associated with a key.
* @param k The key.
* @param v The value to be associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public void put(K k, V v) throws IllegalArgumentException {
Node n = this.findForSure(k);
n.value = v;
}
/**
* Get the value associated with a key.
* @param k The key.
* @return The value associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public V get(K k) throws IllegalArgumentException {
Node n = this.findForSure(k);
return n.value;
}
private Node rotateRight(Node c2) {
if (c2 == null) {
return null;
}
Node c1 = c2.left; // left child of parent a
if (c1 == null) {
return null;
}
c2.left = c1.right;
c1.right = c2;
c2.height = height(max(c2)) + 1;
c1.height = height(max(c1)) + 1;
return c1;
}
private Node rotateLeft(Node c1) {
if (c1 == null) {
return null;
}
Node c2 = c1.right; //right child of parent b
if (c2 == null) {
return null;
}
c1.right = c2.left;
c2.left = c1;
c1.height = height(max(c1)) + 1; //height of node with maximum key
c2.height = height(max(c2)) + 1; //height of node with max key
return c2;
}
private Node rotateLeftRight(Node c3) {
c3.left = rotateLeft(c3.left);
return rotateRight(c3);
}
private Node rotateRightLeft(Node c1) {
c1.right = rotateRight(c1.right);
return rotateLeft(c1);
}
/** Method to insert given key and value into subtree rooted at given node.
* If balance factor > 1, we have l-l case or l-r case.
* If balance factor < -1, we have r-r case or r-l case.
* @param n the node whose subtree key and value will be inserted.
* @param k the key to be inserted into subtree at given node.
* @param v value that corresponds with key.
* @return modified subtree with new node.
*/
private Node insert(Node n, K k, V v) {
if (n == null) {
return new Node(k, v);
}
int cmp = k.compareTo(n.key);
if (cmp < 0) {
n.left = this.insert(n.left, k, v);
} else if (cmp > 0) {
n.right = this.insert(n.right, k, v);
} else {
throw new IllegalArgumentException("duplicate key " + k);
}
int balance = getBalance(n);
//left left case
if (balance > 1 && cmp < 0) {
n = rotateRight(n);
}
//right right case
if (balance < -1 && cmp > 0) {
n = rotateLeft(n);
}
//left right case
if (balance > 1 && cmp > 0) {
n = rotateLeftRight(n);
}
//right left case
if (balance < -1 && cmp < 0) {
n = rotateRightLeft(n);
}
return n;
}
/**
* Insert a new key/value pair.
*
* @param k The key.
* @param v The value to be associated with k.
* @throws IllegalArgumentException If k is null or already mapped.
*/
public void insert(K k, V v) throws IllegalArgumentException {
if (k == null) {
throw new IllegalArgumentException("cannot handle null key");
}
this.root = this.insert(this.root, k, v);
this.size++;
}
// Return node with maximum key in subtree rooted at given node.
// (Iterative because once again recursion has no advantage.)
private Node max(Node n) {
while (n.right != null) {
n = n.right;
}
return n;
}
// Remove given node and return the remaining tree. Easy if the node
// has 0 or 1 child; if it has two children, find the predecessor,
// copy its data to the given node (thus removing the key we need to
// get rid off), the remove the predecessor node.
private Node remove(Node n) {
// 0 and 1 child
if (n.left == null) {
return n.right;
}
if (n.right == null) {
return n.left;
}
// 2 children
Node max = this.max(n.left);
n.key = max.key;
n.value = max.value;
n.left = this.remove(n.left, max.key);
return n;
}
// Remove node with given key from subtree rooted at given node;
// return changed subtree with given key missing. (Again doing this
// recursively makes it easier to add fancy rebalancing code later.)
private Node remove(Node n, K k) {
if (n == null) {
throw new IllegalArgumentException("cannot find key " + k);
}
int cmp = k.compareTo(n.key);
if (cmp < 0) {
n.left = this.remove(n.left, k);
} else if (cmp > 0) {
n.right = this.remove(n.right, k);
} else {
n = this.remove(n);
}
int balance = getBalance(n);
//left left case
if ((balance > 1) && (getBalance(n.left) >=0)) {
return rotateRight(n);
}
//left right case
if ((balance > 1) && (getBalance(n.left) < 0)) {
return rotateLeftRight(n);
}
//right right case
if ((balance < -1) && (getBalance(n.right) <= 0)) {
return rotateLeft(n);
}
//right left
if ((balance < -1) && (getBalance(n.right) > 0)) {
return rotateRightLeft(n);
}
return n;
}
/**
* Remove an existing key/value pair.
*
* @param k The key.
* @return The value that was associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public V remove(K k) throws IllegalArgumentException {
V v = this.findForSure(k).value;
this.root = this.remove(this.root, k);
this.size--;
return v;
}
// Recursively add keys from subtree rooted at given node into the
// given list in order.
private void iteratorHelper(Node n, List keys) {
if (n == null) {
return;
}
this.iteratorHelper(n.left, keys);
keys.add(n.key);
this.iteratorHelper(n.right, keys);
}
@Override
public Iterator iterator() {
List keys = new ArrayList();
this.iteratorHelper(this.root, keys);
return keys.iterator();
}
// If we don't have a StringBuilder yet, make one;
// otherwise just reset it back to a clean slate.
private void setupStringBuilder() {
if (this.stringBuilder == null) {
this.stringBuilder = new StringBuilder();
} else {
this.stringBuilder.setLength(0);
}
}
// Recursively append string representations of keys and values from
// subtree rooted at given node in order.
private void toStringHelper(Node n, StringBuilder s) {
if (n == null) {
return;
}
this.toStringHelper(n.left, s);
s.append(n.key);
s.append(": ");
s.append(n.value);
s.append(", ");
this.toStringHelper(n.right, s);
}
@Override
public String toString() {
this.setupStringBuilder();
this.stringBuilder.append("{");
this.toStringHelper(this.root, this.stringBuilder);
int length = this.stringBuilder.length();
if (length > 1) {
// If anything was appended at all, get rid of the last ", "
// toStringHelper put in; easier to correct this after the
// fact than to avoid making the mistake in the first place.
this.stringBuilder.setLength(length - 2);
}
this.stringBuilder.append("}");
return this.stringBuilder.toString();
}
}
Explanation / Answer
Modified code made bold..
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
/**
* OrderedMap implementation AVL Tree Map.
*
* @author....
* @param type for keys.
* @param type for values.
*/
public class AvlTreeMap<K, V> implements OrderedMap {
//Inner node class
private class Node { //change back to private
Node left;
Node right;
K key;
V value;
int height;
//constructor node creation
Node(K k, V v) {
this.key = k;
this.value = v;
this.height = 0;
this.left = null;
this.right = null;
}
public String toString() {
return "Node" + this.value + ">";
}
}
private Node root;
private int size;
private StringBuilder stringBuilder;
public V rootValue() {
return this.root.value;
}
public K rootKey() {
return this.root.key;
}
@Override
public int size() {
return this.size;
}
/**
* Get height of given node.
*
* @param n node.
* @return height of subtree/tree.
*/
private int height(Node n) {
if (n == null) {
return -1;
}
return n.height;
}
/**
* Get balance factor of a node.
*
* @param n the node
* @return the balance factor
*/
private int getBalance(Node n) {
if (n == null) {
return 0;
}
return height(n.left) - height(n.right);
}
/**
* Return node for given key.
*
* @param k the key.
* @return node for the given key.
*/
private Node find(K k) {
if (k == null) {
throw new IllegalArgumentException("cannot handle null key");
}
Node n = this.root;
while (n != null) {
int cmp = k.compareTo(n.key);
if (k < n.key) {
n = n.left;
} else if (cmp > 0) {
n = n.right;
} else {
return n;
}
}
return null;
}
public boolean has(K k) {
if (k == null) {
return false;
}
return this.find(k) != null;
}
/**
* find for sure
*
* @param k the key
* @return node for given key
* @throws IllegalArgumentException
*/
private Node findForSure(K k) {
Node n = this.find(k);
if (n == null) {
throw new IllegalArgumentException("cannot find key " + k);
}
return n;
}
/**
* Update the value associated with a key.
*
* @param k The key.
* @param v The value to be associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public void put(K k, V v) throws IllegalArgumentException {
Node n = this.findForSure(k);
n.value = v;
}
/**
* Get the value associated with a key.
*
* @param k The key.
* @return The value associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public V get(K k) throws IllegalArgumentException {
Node n = this.findForSure(k);
return n.value;
}
private Node rotateRight(Node c2) {
if (c2 == null) {
return null;
}
Node c1 = c2.left; // left child of parent a
if (c1 == null) {
return null;
}
/* this condition was missed in your code*/
if(c1.left == c2){
c1.left = c2.left;
}
else{
c1.right = c2.left;
}
c2.height = height(max(c2)) + 1;
c1.height = height(max(c1)) + 1;
return c1;
}
private Node rotateLeft(Node c1) {
if (c1 == null) {
return null;
}
Node c2 = c1.right; //right child of parent b
if (c2 == null) {
return null;
}
/* This condition was missing */
if(c1.left == c2){
c1.left = c2.right;
}
else{
c1.right = c2.right;
}
c1.height = height(max(c1)) + 1; //height of node with maximum key
c2.height = height(max(c2)) + 1; //height of node with max key
return c2;
}
private Node rotateLeftRight(Node c3) {
c3.left = rotateLeft(c3.left);
return rotateRight(c3);
}
private Node rotateRightLeft(Node c1) {
c1.right = rotateRight(c1.right);
return rotateLeft(c1);
}
/**
* Method to insert given key and value into subtree rooted at given node.
* If balance factor > 1, we have l-l case or l-r case. If balance factor <
* -1, we have r-r case or r-l case. @param n the node whose subtree
*
* key and value will be inserted.
* @param k the key to be inserted into subtree at given node.
* @param v value that corresponds with key.
* @return modified subtree with new node.
*/
private Node insert(Node n, K k, V v) {
if (n == null) {
return new Node(k, v);
}
int cmp = k.compareTo(n.key);
if (cmp < 0) {
n.left = this.insert(n.left, k, v);
} else if (cmp > 0) {
n.right = this.insert(n.right, k, v);
} else {
throw new IllegalArgumentException("duplicate key " + k);
}
int balance = getBalance(n);
//left left case
if (balance > 1 && cmp < 0) {
n = rotateRight(n);
}
//right right case
if (balance < -1 && cmp > 0) {
n = rotateLeft(n);
}
//left right case
if (balance > 1 && cmp > 0) {
n = rotateLeftRight(n);
}
//right left case
if (balance < -1 && cmp < 0) {
n = rotateRightLeft(n);
}
return n;
}
/**
* Insert a new key/value pair.
*
* @param k The key.
* @param v The value to be associated with k.
* @throws IllegalArgumentException If k is null or already mapped.
*/
public void insert(K k, V v) throws IllegalArgumentException {
if (k == null) {
throw new IllegalArgumentException("cannot handle null key");
}
this.root = this.insert(this.root, k, v);
this.size++;
}
// Return node with maximum key in subtree rooted at given node.
// (Iterative because once again recursion has no advantage.)
private Node max(Node n) {
while (n.right != null) {
n = n.right;
}
return n;
}
// Remove given node and return the remaining tree. Easy if the node
// has 0 or 1 child; if it has two children, find the predecessor,
// copy its data to the given node (thus removing the key we need to
// get rid off), the remove the predecessor node.
private Node remove(Node n) {
// 0 and 1 child
if (n.left == null) {
return n.right;
}
if (n.right == null) {
return n.left;
}
// 2 children
Node max = this.max(n.left);
n.key = max.key;
n.value = max.value;
n.left = this.remove(n.left, max.key);
return n;
}
// Remove node with given key from subtree rooted at given node;
// return changed subtree with given key missing. (Again doing this
// recursively makes it easier to add fancy rebalancing code later.)
private Node remove(Node n, K k) {
if (n == null) {
throw new IllegalArgumentException("cannot find key " + k);
}
int cmp = k.compareTo(n.key);
if (cmp < 0) {
n.left = this.remove(n.left, k);
} else if (cmp > 0) {
n.right = this.remove(n.right, k);
} else {
n = this.remove(n);
}
int balance = getBalance(n);
//left left case
if ((balance > 1) && (getBalance(n.left) >= 0)) {
return rotateRight(n);
}
//left right case
if ((balance > 1) && (getBalance(n.left) < 0)) {
return rotateLeftRight(n);
}
//right right case
if ((balance < -1) && (getBalance(n.right) <= 0)) {
return rotateLeft(n);
}
//right left
if ((balance < -1) && (getBalance(n.right) > 0)) {
return rotateRightLeft(n);
}
return n;
}
/**
* Remove an existing key/value pair.
*
* @param k The key.
* @return The value that was associated with k.
* @throws IllegalArgumentException If k is null or not mapped.
*/
public V remove(K k) throws IllegalArgumentException {
V v = this.findForSure(k).value;
this.root = this.remove(this.root, k);
this.size--;
return v;
}
// Recursively add keys from subtree rooted at given node into the
// given list in order.
private void iteratorHelper(Node n, List keys) {
if (n == null) {
return;
}
this.iteratorHelper(n.left, keys);
keys.add(n.key);
this.iteratorHelper(n.right, keys);
}
public Iterator iterator() {
List keys = new ArrayList();
this.iteratorHelper(this.root, keys);
return keys.iterator();
}
// If we don't have a StringBuilder yet, make one;
// otherwise just reset it back to a clean slate.
private void setupStringBuilder() {
if (this.stringBuilder == null) {
this.stringBuilder = new StringBuilder();
} else {
this.stringBuilder.setLength(0);
}
}
// Recursively append string representations of keys and values from
// subtree rooted at given node in order.
private void toStringHelper(Node n, StringBuilder s) {
if (n == null) {
return;
}
this.toStringHelper(n.left, s);
s.append(n.key);
s.append(": ");
s.append(n.value);
s.append(", ");
this.toStringHelper(n.right, s);
}
@Override
public String toString() {
this.setupStringBuilder();
this.stringBuilder.append("{");
this.toStringHelper(this.root, this.stringBuilder);
int length = this.stringBuilder.length();
if (length > 1) {
// If anything was appended at all, get rid of the last ", "
// toStringHelper put in; easier to correct this after the
// fact than to avoid making the mistake in the first place.
this.stringBuilder.setLength(length - 2);
}
this.stringBuilder.append("}");
return this.stringBuilder.toString();
}
}