Question

Copy the file SimplerBST.java from the week 1 examples package and rename the file and class...

Copy the file SimplerBST.java from the week 1 examples package and rename the file and class A3BST. Add two public methods:

  • one named countTwins that takes no parameters and that, when called, traverses every node of the tree to count the number of nodes having two children.
  • one named lessThanValueCount that takes a paremeter of generic type V, and that, when called, traverses every node of the tree to count the number of nodes whose value (not its key) is less than the value passed as a parameter.

package assignment3;
import algs4.*;

public class A3BST, V> {
  
  
   private Node root; // root of BST

   private static class Node,V> {
       public K key;            // sorted by key
       public V val;        // associated data
       public Node left, right;     // left and right subtrees

       public Node(K key, V val) {
           this.key = key;
           this.val = val;
       }
   }
  
   public A3BST() {}

   /* *********************************************************************
   * 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 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 put(Node x, K key, V val) {
       if (x == null) return new Node<>(key, val);
       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;
   }

   /* *********************************************************************
   * Delete
   ***********************************************************************/

   public void delete(K key) {
       root = delete(root, key);
   }
  
   private Node delete(Node x, K key) {
       if (x == null) return null;
       int cmp = key.compareTo(x.key);
       if (cmp < 0) x.left = delete(x.left, key);
       else if (cmp > 0) x.right = delete(x.right, key);
       else {
           // x is the node to be deleted.
           // The value returned in each of these cases below
           // becomes the value of the child reference from
           // the parent of x. Returning a null makes that
           // reference a null and so cuts x off, causing its
           // automatic deletion.
          
           // Determine how many children x has.
           if (x.right == null && x.left == null){
               // This is a leaf node.
               return null;
           } else if (x.right == null) {
               // One child, to the left.
               return x.left;
           } else if (x.left == null) {
               // One child, to the right.
               return x.right;
           } else {
               // Node x has two children.
               // Find the node in x's right subtree with
               // the minimum key.
               Node rightTreeMinNode = findMin(x.right);
               x.key = rightTreeMinNode.key;
               x.val = rightTreeMinNode.val;
               x.right = delete(x.right, rightTreeMinNode.key);
           }
       }
       return x;
   }
  
   private Node findMin(Node x) {
       if (x.left == null) return x;
       else return findMin(x.left);
   }

   public void printKeys() {
       printKeys(root);
   }
  
   private void printKeys(Node x) {
       if (x == null) return;
       printKeys(x.left);
       StdOut.println(x.key);
       printKeys(x.right);
   }
  
   public Iterable keys() {
       Queue q = new Queue<>();
       inOrder(root, q);
       return q;
   }

   private void inOrder(Node x, Queue q) {
       if (x == null) return;
       inOrder(x.left, q);
       q.enqueue(x.key);
       inOrder(x.right, q);
   }
  
   public int height() {
       return height(root);
   }
  
   private int height(Node x) {
       if (x == null) return -1;
       return 1+Math.max(height(x.left), height(x.right));
   }

   /* ***************************************************************************
   * Visualization
   *****************************************************************************/

   public void drawTree() {
       if (root != null) {
           StdDraw.setPenColor (StdDraw.BLACK);
           StdDraw.setCanvasSize(1200,700);
           drawTree(root, .5, 1, .25, 0);
       }
   }
   private void drawTree (Node n, double x, double y, double range, int depth) {
       int CUTOFF = 10;
       StdDraw.text (x, y, n.key.toString ());
       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);
       }
   }
  
   /* ***************************************************************************
   * countTwins method
   *****************************************************************************/
   public int countTwins(Node node) {
      
       //traverse every node of the tree and count
       //nodes having two children
      
       //run time O(n) --- n nodes are visited --- understand the structure of the tree
      
       if(node == null) {
           return 0;
       }
      
       //set the condition if the both left and right are populated
       if (node.left != null && node.right != null) {
           //return the count
           return 1 + countTwins(node.left) + countTwins(node.right);
       }
      
   //else traverse
       return countTwins(node.left) + countTwins(node.right);
      
   }
  
  
  
   /* ***************************************************************************
   * lessThanValueCount method
   *****************************************************************************/
   public int lessThanValueCount(Node x, V key) {
      
       if (x == null) {
   return 0;
   }
          
   if (x.val.equals(key)) {
   return 1 + lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
   }
   return lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
   }
   }
  

Homework Answers

Answer #1

//if you have any query regarding the answer then let me know.

//if you like it, then give a thumbs up.

package assignment3;
import algs4.*;

public class A3BST, V> {
  
  
private Node root; // root of BST

private static class Node,V> {
public K key; // sorted by key
public V val; // associated data
public Node left, right; // left and right subtrees

public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
  
public A3BST() {}

/* *********************************************************************
* 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 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 put(Node x, K key, V val) {
if (x == null) return new Node<>(key, val);
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;
}

/* *********************************************************************
* Delete
***********************************************************************/

public void delete(K key) {
root = delete(root, key);
}
  
private Node delete(Node x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else {
// x is the node to be deleted.
// The value returned in each of these cases below
// becomes the value of the child reference from
// the parent of x. Returning a null makes that
// reference a null and so cuts x off, causing its
// automatic deletion.
  
// Determine how many children x has.
if (x.right == null && x.left == null){
// This is a leaf node.
return null;
} else if (x.right == null) {
// One child, to the left.
return x.left;
} else if (x.left == null) {
// One child, to the right.
return x.right;
} else {
// Node x has two children.
// Find the node in x's right subtree with
// the minimum key.
Node rightTreeMinNode = findMin(x.right);
x.key = rightTreeMinNode.key;
x.val = rightTreeMinNode.val;
x.right = delete(x.right, rightTreeMinNode.key);
}
}
return x;
}
  
private Node findMin(Node x) {
if (x.left == null) return x;
else return findMin(x.left);
}

public void printKeys() {
printKeys(root);
}
  
private void printKeys(Node x) {
if (x == null) return;
printKeys(x.left);
StdOut.println(x.key);
printKeys(x.right);
}
  
public Iterable keys() {
Queue q = new Queue<>();
inOrder(root, q);
return q;
}

private void inOrder(Node x, Queue q) {
if (x == null) return;
inOrder(x.left, q);
q.enqueue(x.key);
inOrder(x.right, q);
}
  
public int height() {
return height(root);
}
  
private int height(Node x) {
if (x == null) return -1;
return 1+Math.max(height(x.left), height(x.right));
}

/* ***************************************************************************
* Visualization
*****************************************************************************/

public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
drawTree(root, .5, 1, .25, 0);
}
}
private void drawTree (Node n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.text (x, y, n.key.toString ());
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);
}
}
  
/* ***************************************************************************
* countTwins method
*****************************************************************************/
public int countTwins(Node node) {
  
//traverse every node of the tree and count
//nodes having two children
  
//run time O(n) --- n nodes are visited --- understand the structure of the tree
  
if(node == null) {
return 0;
}
  
//set the condition if the both left and right are populated
if (node.left != null && node.right != null) {
//return the count
return 1 + countTwins(node.left) + countTwins(node.right);
}
  
//else traverse
return countTwins(node.left) + countTwins(node.right);
  
}



//---------------------*****************----------------------------
// CountTwin() with no parameter
//---------------------*****************----------------------------

public int countTwins()
{
   Node node=root;
   int count=0;
     
   //talking queue.
   Queue<Node> q=new LinkedList<Node>;   
   q.add(node);
     
   while(q.isEmpty()!=true)
   {
       Node temp=q.poll();
       if(temp.left!=null && temp.right!=null)
       {
       count++;     
       }
         
       if(temp.left!=null)
       {
           q.add(temp.left);
       }
       if(temp.right!=null)
       {
           q.add(temp.right);
       }
   }
     
   return count;
}

  
/* ***************************************************************************
* lessThanValueCount method
*****************************************************************************/
public int lessThanValueCount(Node x, V key) {
  
if (x == null) {
return 0;
}
  
if (x.val.equals(key)) {
return 1 + lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
}
return lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
}
}




//---------------------*****************----------------------------
// lessThanValueCount that take V
//---------------------*****************----------------------------

public int lessThanValueCount(V v)
{
  
   Node node=root;
   int count=0;
     
   Queue<Node> q=new LinkedList<Node>;
   q.add(node);
     
   while(q.isEmpty()!=true)
   {
       Node temp=q.poll();
       if(temp.val<v)
       {
           count++;
       }
       if(temp.left!=null)
       {
           q.add(temp.left);
       }
       if(temp.right!=null)
       {
           q.add(temp.right);
       }
   }
     
   return count;
     
}

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting element by element and printing the results with (1) S E A R C H E X A M P L E (where the value is the index of the letter in the initial word) and (2) K R I S T E N public class RedBlackBST<Key extends Comparable<Key>, Value> { private Node root; private class Node // BST node with color bit (see...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
This is my current code and im having trouble inserting the findMin, findMax, and Search functions...
This is my current code and im having trouble inserting the findMin, findMax, and Search functions in main to output them. #include<iostream> using namespace std; /*Define the class for BST*/ class BST_TREE {    /*Structure of the tree*/    struct tree    {        int value;        tree* left;        tree* right;    };    tree* root;    /*Method to clear the tree*/    tree* Empty(tree* t)    {        if (t == NULL)       ...
Please ask the user to input a low range and a high range and then print...
Please ask the user to input a low range and a high range and then print the range between them. Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys from the inventory.txt file. (Both low key and high key do not have to be a key on the list). ****Please seperate the information in text file by product id,...
How do I implement this method BalancedByNodeCount() ? public class BinarySearchTree { private Node root; private...
How do I implement this method BalancedByNodeCount() ? public class BinarySearchTree { private Node root; private boolean isBalancedByNodeCount() { /**************************************************************************** Implement this method and replace the return statement below with your code. * Definition of Balance tree (On page 372 of book): * An unbalanced tree is created when most of the nodes are on one side of the root or the other. ****************************************************************************/    return false; }       public static void main(String args[]) { int[] values1 = {50,...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
Question: I get a Segmentation fault error sometimes when I addElementBack or print. Am I using...
Question: I get a Segmentation fault error sometimes when I addElementBack or print. Am I using pointers correctly and deleting memory properly? #ifndef DYNAMICARRAY_H #define DYNAMICARRAY_H #include <cstdlib> #include <iostream> using namespace std; // Node class class Node { int data; Node* next; Node* prev; public: Node(); Node(int); void SetData(int newData) { data = newData; }; void SetNext(Node* newNext) { next = newNext; }; void SetPrev(Node* newPrev) { prev = newPrev; }; int getData() { return data; }; Node* getNext()...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue class . Call your class Queue. it must be a template class. public class Queue { } I have put a driver program in the module . It is called CircularQueue.java This driver program should then run with your Queue class (no modifications allowed to the driver program). Your Queue class should have at least the following methods: one or more constructors, enqueue, dequeue,...
You will be traversing through an integer tree to print the data. Given main(), write the...
You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 - 85 -...