Using the templates below, create an AVL Tree Map in java (fill in the places wh
ID: 3844236 • Letter: U
Question
Using the templates below, create an AVL Tree Map in java (fill in the places where it says // fix this). In other words, create an AVL Tree which implements the Map interface. The Map interface as well as a template AVLTreeMap.java class is given below.
public class AVLTreeMap implements Map {
class Node {
String key;
String value;
int height;
Node parent; // delete this variable for extra credit
Node left;
Node right;
public Node(String key, String value) {
this.key = key;
this.value = value;
this.height = 1;
this.parent = null;
this.left = null;
this.right = null;
}
public int balance() {
// FIXME
return -1;
}
}
private int size;
private Node root;
public AVLTreeMap() {
// FIXME
}
public int size() {
// FIXME
return -1;
}
public void put(String key, String value) {
// FIXME
}
public String get(String key) {
// FIXME
return null;
}
public void print() {
this.print(this.root, "", 0);
}
private void print(Node node, String prefix, int depth) {
if (node == null) {
return;
}
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
if (!prefix.equals("")) {
System.out.print(prefix);
System.out.print(":");
}
System.out.print(node.key);
System.out.print(" (");
System.out.print("H:");
System.out.print(node.height);
System.out.print(", B:");
System.out.print(node.balance());
System.out.println(")");
this.print(node.left, "L", depth + 1);
this.print(node.right, "R", depth + 1);
}
public static void main(String[] args) {
AVLTreeMap map = new AVLTreeMap();
String[] keys = {"7", "9", "6", "0", "4", "2", "1"};
String[] values = {"seven", "nine", "six", "zero", "four", "two", "one"};
for (int i = 0; i < keys.length; i++) {
map.put(keys[i], values[i]);
map.print();
System.out.println();
}
for (int i = 0; i < keys.length; i++) {
System.out.print(keys[i]);
System.out.print(" ");
System.out.println(map.get(keys[i]));
}
}
}
Explanation / Answer
public class AVLTreeMap implements Map {
class Node {
String key;
String value;
int height;
Node parent; // delete this variable for extra credit
Node left;
Node right;
public Node(String key, String value) {
this.key = key;
this.value = value;
this.height = 1;
this.parent = null;
this.left = null;
this.right = null;
}
}
private int size;
private Node root;
public AVLTreeMap() {
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) return 0;
return x.size;
}
public void put(String key, String value) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (value == null) {
delete(key);
return;
}
root = put(root, key, value);
assert check();
}
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 0, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
}
else if (cmp > 0) {
x.right = put(x.right, key, val);
}
else {
x.val = val;
return x;
}
x.size = 1 + size(x.left) + size(x.right);
x.height = 1 + Math.max(height(x.left), height(x.right));
return balance(x);
}
private Node balance(Node x) {
if (balanceFactor(x) < -1) {
if (balanceFactor(x.right) > 0) {
x.right = rotateRight(x.right);
}
x = rotateLeft(x);
}
else if (balanceFactor(x) > 1) {
if (balanceFactor(x.left) < 0) {
x.left = rotateLeft(x.left);
}
x = rotateRight(x);
}
return x;
}
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
y.size = x.size;
x.size = 1 + size(x.left) + size(x.right);
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
y.size = x.size;
x.size = 1 + size(x.left) + size(x.right);
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}
private int balanceFactor(Node x) {
return height(x.left) - height(x.right);
}
private int height(Node x) {
if (x == null) return -1;
return x.height;
}
public String get(String key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
Node x = get(root, key);
if (x == null) return null;
return x.val;
}
private Node get(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x;
}
public void print() {
this.print(this.root, "", 0);
}
private void print(Node node, String prefix, int depth) {
if (node == null) {
return;
}
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
if (!prefix.equals("")) {
System.out.print(prefix);
System.out.print(":");
}
System.out.print(node.key);
System.out.print(" (");
System.out.print("H:");
System.out.print(node.height);
System.out.print(", B:");
System.out.print(node.balance());
System.out.println(")");
this.print(node.left, "L", depth + 1);
this.print(node.right, "R", depth + 1);
}
public static void main(String[] args) {
AVLTreeMap map = new AVLTreeMap();
String[] keys = {"7", "9", "6", "0", "4", "2", "1"};
String[] values = {"seven", "nine", "six", "zero", "four", "two", "one"};
for (int i = 0; i < keys.length; i++) {
map.put(keys[i], values[i]);
map.print();
System.out.println();
}
for (int i = 0; i < keys.length; i++) {
System.out.print(keys[i]);
System.out.print(" ");
System.out.println(map.get(keys[i]));
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.