Hello there, I am taking Data Structures & Algorithms in Java this semester and

ID: 3717825 • Letter: H

Question

Hello there,

I am taking Data Structures & Algorithms in Java this semester and we were just introduced to Hash Tables. We were given an assignment and I need a lot of help with the second part. I have provided the assignment sheet and sample code that is discussed in the prompt of the assignment.

Thank you!

Assignment Sheet:

HashTableWithChaining Project Code:

public class Link
{                                   // (could be other items)
int iData;                  // data item
Link next;                   // next link in list
//-------------------------------------------------------------
public Link(int it)                 // constructor
    { iData= it; }
//-------------------------------------------------------------
public int getKey()
    { return iData; }
//-------------------------------------------------------------
public void displayLink()           // display this link
    { System.out.print(iData + " "); }
} // end class Link

public class SortedList
{
private Link first;               // ref to first list item
//-------------------------------------------------------------
public void SortedList()          // constructor
  { first = null; }
//-------------------------------------------------------------
public void insert(Link theLink) // insert link, in order
    {
    int key = theLink.getKey();
    Link previous = null;          // start at first
    Link current = first;
                                   // until end of list,
    while( current != null && key > current.getKey() ) //make the list item sorted
       {                           // or current > key,
       previous = current;
       current = current.next;     // go to next item
       }
    if(previous==null)             // if beginning of list,
       first = theLink;            //    first --> new link
    else                           // not at beginning,
       previous.next = theLink;    //    prev --> new link
    theLink.next = current;        // new link --> current
    } // end insert()
//-------------------------------------------------------------
public void delete(int key)       // delete link
    {                              // (assumes non-empty list)
    Link previous = null;          // start at first
    Link current = first;
                                   // until end of list,
    while( current != null && key != current.getKey() )
       {                           // or key == current,
       previous = current;
       current = current.next;     // go to next link
       }
                                   // disconnect link
    if(previous==null)             //   if beginning of list
       first = first.next;         //      delete first link
    else                           //   not at beginning
       previous.next = current.next; //    delete current link
    } // end delete()
//-------------------------------------------------------------
public Link find(int key)         // find link
    {
    Link current = first;          // start at first
                                   // until end of list,
    while(current != null && current.getKey() <= key)
       {                           // or key too small,
       if(current.getKey() == key)    // is this the link?
          return current;          // found it, return link
       current = current.next;     // go to next item
       }
    return null;                   // didn't find it
    } // end find()
//-------------------------------------------------------------
public void displayList()
    {
    System.out.print("List (first-->last): ");
    Link current = first;       // start at beginning of list
    while(current != null)      // until end of list,
       {
       current.displayLink();   // print data
       current = current.next; // move to next link
       }
    System.out.println("");
    }
} // end class SortedList

public class HashTableWithChaining {

    private SortedList[] hashArray;   // array of lists
    private int arraySize;
// -------------------------------------------------------------
    public HashTableWithChaining(int size)        // constructor
       {
       arraySize = size;
       hashArray = new SortedList[arraySize]; // create array
       for(int j=0; j<arraySize; j++)          // fill array
          hashArray[j] = new SortedList();     // with lists
       }
// -------------------------------------------------------------
    public void displayTable()
       {
       for(int j=0; j<arraySize; j++) // for each cell,
          {
          System.out.print(j + ". "); // display cell number
          hashArray[j].displayList(); // display list
          }
       }
// -------------------------------------------------------------
    public int hashFunc(int key)      // hash function
       {
       return key % arraySize;
       }
// -------------------------------------------------------------
    public void insert(Link theLink) // insert a link
       {
       int key = theLink.getKey();
       int hashVal = hashFunc(key);   // hash the key
       hashArray[hashVal].insert(theLink); // insert at hashVal
       } // end insert()
// -------------------------------------------------------------
    public void delete(int key)       // delete a link
       {
       int hashVal = hashFunc(key);   // hash the key
       hashArray[hashVal].delete(key); // delete link
       } // end delete()
// -------------------------------------------------------------
    public Link find(int key)         // find link
       {
       int hashVal = hashFunc(key);   // hash the key
       Link theLink = hashArray[hashVal].find(key); // get link
       return theLink;                // return link
       }
// -------------------------------------------------------------
} // end class HashTable

BinarySearchTreeProject Code

public class IntTreeNode {

int key;  //store this node's key value
IntTreeNode leftChild; //store the reference
       // to this node's left child
IntTreeNode rightChild; //store the reference
       // to this node's right child

//constructor
public IntTreeNode(int key)
{
  this.key = key;
  this.leftChild = null;
  this.rightChild = null;
}

public IntTreeNode(int key, IntTreeNode left, IntTreeNode right)
{
  this.key = key;
  this.leftChild = left;
  this.rightChild = right;
}

//display itself
public void display()
{
  System.out.print("(" + key + ")");
}

//remove a node from the subtree
public IntTreeNode remove(int delKey, IntTreeNode parent)
{
  if (delKey < this.key){

   if (leftChild != null)
    return leftChild.remove(delKey, this);
   else
    return null;
  }
  else if (delKey > this.key) {

   if (rightChild != null)
    return rightChild.remove(delKey, this);
   else
    return null;
  }
  else {   //find the node

   if (leftChild != null && rightChild != null) {

        IntTreeNode min = rightChild.minRightSubTree();
     this.key = min.key;
     return rightChild.remove(this.key, this);

   }
   else if (this == parent.leftChild) {
    parent.leftChild = (leftChild != null) ? leftChild : rightChild;
    return this;
   }
   else if (this == parent.rightChild) {
    parent.rightChild = (leftChild != null) ? leftChild : rightChild;
    return this;
   }
  }

  return null;

}

//find a minimum value in the right subtree
public IntTreeNode minRightSubTree()
{
  if (this.leftChild == null)
   return this;
  else
   return leftChild.minRightSubTree();
}

}

public class IntBinarySearchTree {

private IntTreeNode root; //first node of the tree
private int numItems; //number of nodes in the tree

//constructor
public IntBinarySearchTree()
{
  root = null;
  numItems = 0;
}

//getters
public IntTreeNode getRoot() {
  return root;
}

public int getNumItems() {
return numItems;
}

//check whether this binary tree is a binary search tree
public boolean isBST()
{
  return isBST(root);
}

//helper method: recursive check isBST
private boolean isBST(IntTreeNode root)
{
  if(root == null)
   return true;
  if( isSubTreeLess(root.leftChild, root.key) &&
         isSubTreeGreater(root.rightChild, root.key) &&
                  isBST (root.leftChild) &&
                  isBST (root.rightChild) )
   return true;
  else
   return false;
}

//helper for isBST(IntTreeNode)
private boolean isSubTreeLess(IntTreeNode subRoot, int value)
{
  if(subRoot == null)
   return true;
  if(subRoot.key < value &&
    isSubTreeLess(subRoot.leftChild, value) &&
    isSubTreeLess(subRoot.rightChild, value))
   return true;
  else
   return false;
}

//helper for isBST(IntTreeNode)
private boolean isSubTreeGreater(IntTreeNode subRoot, int value)
{
  if(subRoot == null)
   return true;
  if(subRoot.key >= value &&
    isSubTreeGreater(subRoot.leftChild, value) &&
    isSubTreeGreater(subRoot.rightChild, value))
   return true;
  else
   return false;
}

//insert a node into this binary search tree
public void addBST(int newKey)
{
  root = addBST(newKey, root);
  numItems++;
}

//helper method: recursive insert
private IntTreeNode addBST(int newKey, IntTreeNode subTreeRoot)
{
  if (subTreeRoot==null)
  {
   //create a new node
   subTreeRoot = new IntTreeNode(newKey);
  }
  else if (newKey < subTreeRoot.key)
   subTreeRoot.leftChild = addBST(newKey, subTreeRoot.leftChild);
  else
   subTreeRoot.rightChild = addBST(newKey, subTreeRoot.rightChild);

  return subTreeRoot;
}

//search a node in this binary search tree
public IntTreeNode inBST(int searchKey)
{
  return inBST(searchKey, root);
}

//helper method: recursive search
private IntTreeNode inBST(int searchKey, IntTreeNode subTreeRoot)
{
  if (subTreeRoot == null)
  {
   return null;
  }
  else
  {
   if (searchKey == subTreeRoot.key)
    return subTreeRoot;
   else if (searchKey < subTreeRoot.key)
   {
    return inBST(searchKey, subTreeRoot.leftChild);
   }
   else
   {
    return inBST(searchKey, subTreeRoot.rightChild);
   }
  }
}

//traverse this binary search tree in different ways
public void traverse(int traverseType)
    {
  switch(traverseType)
        {
        case 1: System.out.print(" Preorder traversal: ");
                preOrder(root);
                break;
        case 2: System.out.print(" Inorder traversal: ");
                inOrder(root);
                break;
        case 3: System.out.print(" Postorder traversal: ");
                postOrder(root);
                break;
        }
  System.out.println();
    }

//helper method: recursive preorder traverse
private void preOrder(IntTreeNode subTreeRoot)
     {
       if(subTreeRoot != null)
         {
        subTreeRoot.display();
        preOrder(subTreeRoot.leftChild);
        preOrder(subTreeRoot.rightChild);
         }
      }

//helper method: recursive inorder traverse
      private void inOrder(IntTreeNode subTreeRoot)
   {
       if(subTreeRoot != null)
        {
          inOrder(subTreeRoot.leftChild);
          subTreeRoot.display();
          inOrder(subTreeRoot.rightChild);
        }
      }

    //helper method: recursive postorder traverse
   private void postOrder(IntTreeNode subTreeRoot)
   {
       if(subTreeRoot != null)
        {
          postOrder(subTreeRoot.leftChild);
          postOrder(subTreeRoot.rightChild);
          subTreeRoot.display();
        }
      }

2. Instead of using a linked list to resolve collisions, as in separate chaining, we could also use a binary search tree. It means to create a hash table that is an array of trees. You can use the hashTableWithChaining.java program as a starting point and the tree class in BinarysearchTree project. To display a small tree-based hash table, you could use an in- order traversal of each tree The advantage of a tree over a linked list is that it can be searched in O(logN) instead of O(N) time. The time savings can be a significant advantage if very high load factors are encountered. Checking 15 items takes a maximum of 15 comparisons in a list but only 4 in a tree. Duplicates should not be a problem because binary search tree supports duplicate keys (put in the right subtree) For shorten your coding for this program, you can ignore deletion, which for trees requires a lot of code.

Explanation / Answer

Try this. It should work.

BinarySearchTreeProject Code

//find a minimum value in the right subtree
public IntTreeNode minRightSubTree()
{
  if (this.leftChild == null)
   return this;
  else
   return leftChild.minRightSubTree();
}

}

public class IntBinarySearchTree {

private IntTreeNode root; //first node of the tree
private int numItems; //number of nodes in the tree

//constructor
public IntBinarySearchTree()
{
  root = null;
  numItems = 0;
}

//getters
public IntTreeNode getRoot() {
  return root;
}

public int getNumItems() {
return numItems;
}

Navigate

Hello there, I am struggling with some toxicology study questions. I have put an

Hello there, I am taking a Data Structures & Algorithms class in Java this semes

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Hello there, I am taking Data Structures & Algorithms in Java this semester and

Question

Explanation / Answer

Related Questions

Navigate