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() 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

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 (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; /umber 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 && 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

//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