ou will see that this file contains a main method, which will be used to test th
ID: 3888047 • Letter: O
Question
ou will see that this file contains a main method, which will be used to test the changes you're going to make.Modify the Program3BST.java code as follows:
Add to the node object two instance variables: height, an integer storing the height of that node, and size, an integer storing the size of the tree at that node. Make sure you modify the Node constructor to set these values to 0.
Complete the method private void setSizes() that traverses the entire tree to set the size field for each node. The size of a node is 1 + the size of its left child + the size of its right child. The size of a null node reference is 0.
Complete the method private void setHeights() that traverses the entire tree to set the height field for each node. The height of a node is 1 plus the maximum of the heights of its children. The height of a null node reference is -1.
Modify the private drawTree method so that, for each node, it prints the key, the height, and the size. This is done by modifying this statement in drawTree:
StdDraw.text(x, y, n.key.toString()); The third argument is a string to draw next to a node.
Program3BST.java
package program3;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
*
* This is an implementation of a binary search tree.
* For the third program, you are to modify this class
* as described in the assignment.
*
*************************************************************************/
public class Program3BST<K extends Comparable<? super K>, V> {
private Node<K,V> root; // root of BST
private static class Node<K extends Comparable<? super K>,V> {
public K key; // sorted by key
public V val; // associated data
public Node<K,V> left, right; // left and right subtrees
public Node(K key, V val, int N) {
this.key = key;
this.val = val;
}
}
// is the symbol table empty?
public boolean isEmpty() { return root == null; }
/* *********************************************************************
* Search BST for given key, and return associated value if found,
* return null if not found
***********************************************************************/
// does there exist a key-value pair with given key?
public boolean contains(K key) {
return get(key) != null;
}
// return value associated with the given key, or null if no such key exists
public V get(K key) { return get(root, key); }
private V get(Node<K,V> x, K 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.val;
}
/* *********************************************************************
* Insert key-value pair into BST
* If key already exists, update with new value
***********************************************************************/
public void put(K key, V val) {
if (val == null) { delete(key); return; }
root = put(root, key, val);
}
private Node<K,V> put(Node<K,V> x, K key, V val) {
if (x == null) return new Node<>(key, val, 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;
}
public void delete(K key) {
root = delete(root, key);
}
private Node<K,V> delete(Node<K,V> x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
// Key to delete is to the left of x.
x.left = delete(x.left, key);
return x;
}
else if (cmp > 0) {
// Key to delete is to the right of x.
x.right = delete(x.right, key);
return x;
}
else {
// x contains the key we wish to delete.
if (x.left == null && x.right == null) {
// x is a leaf.
return null;
}
else if (x.left == null) {
// x has only a right child.
return x.right;
}
else if (x.right == null) {
// x has only a left child.
return x.left;
}
else {
// x has two children.
Node<K,V> leftTreeMaxNode = x.left;
// Find the node with the largest key to the left.
while (leftTreeMaxNode.right != null) {
leftTreeMaxNode = leftTreeMaxNode.right;
}
// Copy that largest key and its value to x.
K leftTreeMaxKey = leftTreeMaxNode.key;
x.key = leftTreeMaxNode.key;
x.val = leftTreeMaxNode.val;
// Delete the node copied from.
x.left = delete(x.left, leftTreeMaxKey);
return x;
}
}
}
public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
setSizes();
setHeights();
drawTree(root, .5, 1, .3, 0);
}
}
private void drawTree (Node<K,V> n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.setPenColor(StdDraw.RED);
StdDraw.text(x, y, n.key.toString());
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius (.007);
if (n.left != null && depth != CUTOFF) {
StdDraw.line (x-range, y-.08, x-.01, y-.01);
drawTree (n.left, x-range, y-.1, range*.5, depth+1);
}
if (n.right != null && depth != CUTOFF) {
StdDraw.line (x+range, y-.08, x+.01, y-.01);
drawTree (n.right, x+range, y-.1, range*.5, depth+1);
}
}
private void setHeights() {
// *** Add your code here.
}
private void setSizes() {
// *** Add your code here.
}
/* ***************************************************************************
* Test client
*****************************************************************************/
public static void main(String[] args) {
StdIn.fromString ("D F B G E A C");
Program3BST<String, Integer> st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Balancedtree.png");
StdIn.fromString ("G A B C E F D H");
st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Unbalancedtree.png");
}
} ou will see that this file contains a main method, which will be used to test the changes you're going to make.
Modify the Program3BST.java code as follows:
Add to the node object two instance variables: height, an integer storing the height of that node, and size, an integer storing the size of the tree at that node. Make sure you modify the Node constructor to set these values to 0.
Complete the method private void setSizes() that traverses the entire tree to set the size field for each node. The size of a node is 1 + the size of its left child + the size of its right child. The size of a null node reference is 0.
Complete the method private void setHeights() that traverses the entire tree to set the height field for each node. The height of a node is 1 plus the maximum of the heights of its children. The height of a null node reference is -1.
Modify the private drawTree method so that, for each node, it prints the key, the height, and the size. This is done by modifying this statement in drawTree:
StdDraw.text(x, y, n.key.toString()); The third argument is a string to draw next to a node.
Program3BST.java
package program3;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
*
* This is an implementation of a binary search tree.
* For the third program, you are to modify this class
* as described in the assignment.
*
*************************************************************************/
public class Program3BST<K extends Comparable<? super K>, V> {
private Node<K,V> root; // root of BST
private static class Node<K extends Comparable<? super K>,V> {
public K key; // sorted by key
public V val; // associated data
public Node<K,V> left, right; // left and right subtrees
public Node(K key, V val, int N) {
this.key = key;
this.val = val;
}
}
// is the symbol table empty?
public boolean isEmpty() { return root == null; }
/* *********************************************************************
* Search BST for given key, and return associated value if found,
* return null if not found
***********************************************************************/
// does there exist a key-value pair with given key?
public boolean contains(K key) {
return get(key) != null;
}
// return value associated with the given key, or null if no such key exists
public V get(K key) { return get(root, key); }
private V get(Node<K,V> x, K 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.val;
}
/* *********************************************************************
* Insert key-value pair into BST
* If key already exists, update with new value
***********************************************************************/
public void put(K key, V val) {
if (val == null) { delete(key); return; }
root = put(root, key, val);
}
private Node<K,V> put(Node<K,V> x, K key, V val) {
if (x == null) return new Node<>(key, val, 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;
}
public void delete(K key) {
root = delete(root, key);
}
private Node<K,V> delete(Node<K,V> x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
// Key to delete is to the left of x.
x.left = delete(x.left, key);
return x;
}
else if (cmp > 0) {
// Key to delete is to the right of x.
x.right = delete(x.right, key);
return x;
}
else {
// x contains the key we wish to delete.
if (x.left == null && x.right == null) {
// x is a leaf.
return null;
}
else if (x.left == null) {
// x has only a right child.
return x.right;
}
else if (x.right == null) {
// x has only a left child.
return x.left;
}
else {
// x has two children.
Node<K,V> leftTreeMaxNode = x.left;
// Find the node with the largest key to the left.
while (leftTreeMaxNode.right != null) {
leftTreeMaxNode = leftTreeMaxNode.right;
}
// Copy that largest key and its value to x.
K leftTreeMaxKey = leftTreeMaxNode.key;
x.key = leftTreeMaxNode.key;
x.val = leftTreeMaxNode.val;
// Delete the node copied from.
x.left = delete(x.left, leftTreeMaxKey);
return x;
}
}
}
public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
setSizes();
setHeights();
drawTree(root, .5, 1, .3, 0);
}
}
private void drawTree (Node<K,V> n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.setPenColor(StdDraw.RED);
StdDraw.text(x, y, n.key.toString());
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius (.007);
if (n.left != null && depth != CUTOFF) {
StdDraw.line (x-range, y-.08, x-.01, y-.01);
drawTree (n.left, x-range, y-.1, range*.5, depth+1);
}
if (n.right != null && depth != CUTOFF) {
StdDraw.line (x+range, y-.08, x+.01, y-.01);
drawTree (n.right, x+range, y-.1, range*.5, depth+1);
}
}
private void setHeights() {
// *** Add your code here.
}
private void setSizes() {
// *** Add your code here.
}
/* ***************************************************************************
* Test client
*****************************************************************************/
public static void main(String[] args) {
StdIn.fromString ("D F B G E A C");
Program3BST<String, Integer> st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Balancedtree.png");
StdIn.fromString ("G A B C E F D H");
st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Unbalancedtree.png");
}
} ou will see that this file contains a main method, which will be used to test the changes you're going to make.
Modify the Program3BST.java code as follows:
Add to the node object two instance variables: height, an integer storing the height of that node, and size, an integer storing the size of the tree at that node. Make sure you modify the Node constructor to set these values to 0.
Complete the method private void setSizes() that traverses the entire tree to set the size field for each node. The size of a node is 1 + the size of its left child + the size of its right child. The size of a null node reference is 0.
Complete the method private void setHeights() that traverses the entire tree to set the height field for each node. The height of a node is 1 plus the maximum of the heights of its children. The height of a null node reference is -1.
Modify the private drawTree method so that, for each node, it prints the key, the height, and the size. This is done by modifying this statement in drawTree:
StdDraw.text(x, y, n.key.toString()); The third argument is a string to draw next to a node.
Program3BST.java
package program3;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
*
* This is an implementation of a binary search tree.
* For the third program, you are to modify this class
* as described in the assignment.
*
*************************************************************************/
public class Program3BST<K extends Comparable<? super K>, V> {
private Node<K,V> root; // root of BST
private static class Node<K extends Comparable<? super K>,V> {
public K key; // sorted by key
public V val; // associated data
public Node<K,V> left, right; // left and right subtrees
public Node(K key, V val, int N) {
this.key = key;
this.val = val;
}
}
// is the symbol table empty?
public boolean isEmpty() { return root == null; }
/* *********************************************************************
* Search BST for given key, and return associated value if found,
* return null if not found
***********************************************************************/
// does there exist a key-value pair with given key?
public boolean contains(K key) {
return get(key) != null;
}
// return value associated with the given key, or null if no such key exists
public V get(K key) { return get(root, key); }
private V get(Node<K,V> x, K 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.val;
}
/* *********************************************************************
* Insert key-value pair into BST
* If key already exists, update with new value
***********************************************************************/
public void put(K key, V val) {
if (val == null) { delete(key); return; }
root = put(root, key, val);
}
private Node<K,V> put(Node<K,V> x, K key, V val) {
if (x == null) return new Node<>(key, val, 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;
}
public void delete(K key) {
root = delete(root, key);
}
private Node<K,V> delete(Node<K,V> x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
// Key to delete is to the left of x.
x.left = delete(x.left, key);
return x;
}
else if (cmp > 0) {
// Key to delete is to the right of x.
x.right = delete(x.right, key);
return x;
}
else {
// x contains the key we wish to delete.
if (x.left == null && x.right == null) {
// x is a leaf.
return null;
}
else if (x.left == null) {
// x has only a right child.
return x.right;
}
else if (x.right == null) {
// x has only a left child.
return x.left;
}
else {
// x has two children.
Node<K,V> leftTreeMaxNode = x.left;
// Find the node with the largest key to the left.
while (leftTreeMaxNode.right != null) {
leftTreeMaxNode = leftTreeMaxNode.right;
}
// Copy that largest key and its value to x.
K leftTreeMaxKey = leftTreeMaxNode.key;
x.key = leftTreeMaxNode.key;
x.val = leftTreeMaxNode.val;
// Delete the node copied from.
x.left = delete(x.left, leftTreeMaxKey);
return x;
}
}
}
public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
setSizes();
setHeights();
drawTree(root, .5, 1, .3, 0);
}
}
private void drawTree (Node<K,V> n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.setPenColor(StdDraw.RED);
StdDraw.text(x, y, n.key.toString());
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius (.007);
if (n.left != null && depth != CUTOFF) {
StdDraw.line (x-range, y-.08, x-.01, y-.01);
drawTree (n.left, x-range, y-.1, range*.5, depth+1);
}
if (n.right != null && depth != CUTOFF) {
StdDraw.line (x+range, y-.08, x+.01, y-.01);
drawTree (n.right, x+range, y-.1, range*.5, depth+1);
}
}
private void setHeights() {
// *** Add your code here.
}
private void setSizes() {
// *** Add your code here.
}
/* ***************************************************************************
* Test client
*****************************************************************************/
public static void main(String[] args) {
StdIn.fromString ("D F B G E A C");
Program3BST<String, Integer> st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Balancedtree.png");
StdIn.fromString ("G A B C E F D H");
st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Unbalancedtree.png");
}
}
Explanation / Answer
Given below is the completed code after implementing setHeights() setSizes() and modifying drawTree() to show height and size of a node. Since the question did not provide a needed class StdDraw, I could generate the output.
The height is displayed as H = ... and size as S = ... after the node's key.
Please check the code and let me know through comments if any issues. I will help to resolve it. If the answer helped, please do rate it . Thank you very much.
package program3;
import stdlib.*;
import algs13.Queue;
/* ***********************************************************************
*
* This is an implementation of a binary search tree.
* For the third program, you are to modify this class
* as described in the assignment.
*
*************************************************************************/
public class Program3BST<K extends Comparable<? super K>, V> {
private Node<K,V> root; // root of BST
private static class Node<K extends Comparable<? super K>,V> {
public K key; // sorted by key
public V val; // associated data
public Node<K,V> left, right; // left and right subtrees
private int height, size; //the height and size of this subtree
public Node(K key, V val, int N) {
this.key = key;
this.val = val;
this.height = 0;
this.size = 0;
}
}
// is the symbol table empty?
public boolean isEmpty() { return root == null; }
/* *********************************************************************
* Search BST for given key, and return associated value if found,
* return null if not found
***********************************************************************/
// does there exist a key-value pair with given key?
public boolean contains(K key) {
return get(key) != null;
}
// return value associated with the given key, or null if no such key exists
public V get(K key) { return get(root, key); }
private V get(Node<K,V> x, K 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.val;
}
/* *********************************************************************
* Insert key-value pair into BST
* If key already exists, update with new value
***********************************************************************/
public void put(K key, V val) {
if (val == null) { delete(key); return; }
root = put(root, key, val);
}
private Node<K,V> put(Node<K,V> x, K key, V val) {
if (x == null) return new Node<>(key, val, 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;
}
public void delete(K key) {
root = delete(root, key);
}
private Node<K,V> delete(Node<K,V> x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
// Key to delete is to the left of x.
x.left = delete(x.left, key);
return x;
}
else if (cmp > 0) {
// Key to delete is to the right of x.
x.right = delete(x.right, key);
return x;
}
else {
// x contains the key we wish to delete.
if (x.left == null && x.right == null) {
// x is a leaf.
return null;
}
else if (x.left == null) {
// x has only a right child.
return x.right;
}
else if (x.right == null) {
// x has only a left child.
return x.left;
}
else {
// x has two children.
Node<K,V> leftTreeMaxNode = x.left;
// Find the node with the largest key to the left.
while (leftTreeMaxNode.right != null) {
leftTreeMaxNode = leftTreeMaxNode.right;
}
// Copy that largest key and its value to x.
K leftTreeMaxKey = leftTreeMaxNode.key;
x.key = leftTreeMaxNode.key;
x.val = leftTreeMaxNode.val;
// Delete the node copied from.
x.left = delete(x.left, leftTreeMaxKey);
return x;
}
}
}
public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
setSizes();
setHeights();
drawTree(root, .5, 1, .3, 0);
}
}
private void drawTree (Node<K,V> n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.setPenColor(StdDraw.RED);
//display the height as H and size as S along with the key
StdDraw.text(x, y, n.key.toString() + ", H = "+ n.height + ", S = " + n.size);
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius (.007);
if (n.left != null && depth != CUTOFF) {
StdDraw.line (x-range, y-.08, x-.01, y-.01);
drawTree (n.left, x-range, y-.1, range*.5, depth+1);
}
if (n.right != null && depth != CUTOFF) {
StdDraw.line (x+range, y-.08, x+.01, y-.01);
drawTree (n.right, x+range, y-.1, range*.5, depth+1);
}
}
private void setHeights() {
// *** Add your code here.
setHeight(root);
}
private int setHeight(Node<K,V> n)
{
if(n == null) //height of a null ref is -1
return -1;
else
{
//get heights of left and right subtree and find which is maximum
int leftHeight = setHeight(n.left);
int rightHeight = setHeight(n.right);
int maxHeight;
if(leftHeight > rightHeight)
maxHeight = leftHeight;
else
maxHeight = rightHeight;
//set the node's height
n.height = 1 + maxHeight;
return n.height;
}
}
private void setSizes() {
// *** Add your code here.
setSizes(root);
}
private int setSizes(Node<K,V> n)
{
if(n == null) //size of null ref is 0
return 0;
else
{
//get the sizes of the left and right subtree.
int leftSize = setSizes(n.left);
int rightSize = setSizes(n.right);
//set the size for this node
n.size = 1 + leftSize + rightSize;
return n.size;
}
}
/* ***************************************************************************
* Test client
*****************************************************************************/
public static void main(String[] args) {
StdIn.fromString ("D F B G E A C");
Program3BST<String, Integer> st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Balancedtree.png");
StdIn.fromString ("G A B C E F D H");
st = new Program3BST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
st.drawTree ();
StdDraw.save("data/Program3Unbalancedtree.png");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.