Question: P1 Consider a method for a binary search tree that decides whether the tree is height balanced as defined in section 23.10. A tree is
P1
Consider a method for a binary search tree that decides whether the tree is height balanced as defined in section 23.10. A tree is said to be height balanced or simply balanced if the subtrees of each node in the tree differ in height by no more than 1The header of the method could be as follows:
public boolean isBalanced()
Write this method for the class BinarySearchTree in BinarySearchTree.java. It should call a private recursive method of the same name. isBalanced() must run in O(h) time where h is the height of the tree.
P2
Write a method that checks that the underlying tree is a valid binary search tree. The solution should examine each node in the given binary search tree only once.
The header for the method is as follows:
public boolean isBST()
Add the method to the file BinarySearchTree.java
P3
Implement the following method in BinarySearchTree.java
public T getPredecessor(T entry)
which return the inorder predecessor of entry or entry if its, or entry if its the smallest item in the tree, or null if entry is not in the tree. The solution must run in O(h) where h is the height of the tree.
P4
Statisticians often are interested in the median value in a collection of data. In a collection, about the same number of values are greater than the median value as are less than the median value. When the data is sorted, the median value occurs at the midpoint of the collection. But when the data is not sorted, the median is not as easy to find.
A problem more general than finding the median is to find the k th smallest value in a collection of n values, where 0 < k < n. To find the median, k would be [n/2]that is, the smallest integer greater than or equal to n/2. For example, the median value of 11 items is the 6th smallest one.
Design an algorithm that uses a maxheap to find the k th smallest value in a collection of n values. Implement your algorithm as a method
public static Integer getKthSmallest(ArrayList
in the file MaxHeap.java
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class Person implements Comparable
String name;
String id;
public Person(String n, String i) {
name = n;
id = i;
}
public int compareTo(Person p) {
return name.compareTo(((Person)p).name);
}
}
class Test {
public static void main(String [] a) {
Person p1 = new Person("abc", "123");
Person p2 = new Person("abc", "456");
Person p3 = new Person("cde", "789");
System.out.println("p1.compareTo(p2) = " + p1.compareTo(p2));
System.out.println("p1.compareTo(p3) = " + p1.compareTo(p3));
BinarySearchTree
b.add(p2);
b.add(p3);
System.out.println("b.contains(p1) = " + b.contains(p1));
System.out.println("b.contains(p2) = " + b.contains(p2));
}
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//package TreePackage;
class BinaryNode
private T data;
private BinaryNode
private BinaryNode
public BinaryNode() {
this(null); // call next constructor
} // end default constructor
public BinaryNode(T dataPortion) {
this(dataPortion, null, null); // call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode
BinaryNode
data = dataPortion;
left = leftChild;
right = rightChild;
} // end constructor
public T getData() {
return data;
} // end getData
public void setData(T newData) {
data = newData;
} // end setData
public BinaryNode
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode
left = leftChild;
} // end setLeftChild
public boolean hasLeftChild() {
return left != null;
} // end hasLeftChild
public boolean isLeaf() {
return (left == null) && (right == null);
} // end isLeaf
public BinaryNode
return right;
} // end getLeftChild
public void setRightChild(BinaryNode
right = rightChild;
} // end setLeftChild
public boolean hasRightChild()
{
return right != null;
} // end
public int getHeight()
{
return getHeight(this); // call private getHeight
} // end getHeight
private int getHeight(BinaryNode
{
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.left),
getHeight(node.right));
return height;
} // end getHeight
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;
if (left != null)
leftNumber = left.getNumberOfNodes();
if (right != null)
rightNumber = right.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
} // end BinaryNode
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class BinarySearchTree < T extends Comparable < ? super T >>
{
private BinaryNode
public BinarySearchTree () {
root = null;
}
public BinarySearchTree (T rootData) {
root = new BinaryNode
}
public T get(T entry) {
return getEntry (root, entry);
}
private T getEntry (BinaryNode
T result = null;
if (rootNode != null) {
T rootEntry = rootNode.getData ();
if (entry.compareTo(rootEntry) == 0)
result = rootEntry;
else if (entry.compareTo(rootEntry) < 0)
result = getEntry(rootNode.getLeftChild (), entry);
else
result = getEntry(rootNode.getRightChild (), entry);
}
return result;
}
public boolean contains (T entry) {
return get(entry) != null;
}
// Adds newEntry to the nonempty subtree rooted at rootNode.
private T addEntry (BinaryNode< T > rootNode, T newEntry) {
// assume that rootNode is NOT null
T result = null;
int comparison = newEntry.compareTo (rootNode.getData ());
if (comparison == 0) { // duplicates NOT allowed
result = rootNode.getData ();
rootNode.setData (newEntry);
}
else if (comparison < 0) {
if (rootNode.hasLeftChild ())
result = addEntry (rootNode.getLeftChild (), newEntry);
else
rootNode.setLeftChild (new BinaryNode < T > (newEntry));
}
else {
if (rootNode.hasRightChild ())
result = addEntry (rootNode.getRightChild (), newEntry);
else
rootNode.setRightChild (new BinaryNode < T > (newEntry));
} // end if
return result;
} // end addEntry
public T add (T newEntry) {
T result = null;
if (root == null)
root = new BinaryNode
else
result = addEntry (root, newEntry);
return result;
} // end add
class ReturnObject {
T data;
public void set(T newData) { data = newData; }
public T get() { return data; }
}
public T remove (T entry) {
ReturnObject oldEntry = new ReturnObject();
BinaryNode
root = newRoot;
return oldEntry.get ();
} // end remove
// Removes an entry from the tree rooted at a given node.
// rootNode is a reference to the root of a tree.
// entry is the object to be removed.
// oldEntry is an object whose data field is null.
// Returns the root node of the resulting tree; if entry matches
// an entry in the tree, oldEntry's data field is the entry
// that was removed from the tree; otherwise it is null.
//
// Why removeEntry returns BinaryNode
// Answer: To return a new modified tree: example root node removed so root of tree will change
private BinaryNode
if (rootNode != null) {
T rootData = rootNode.getData ();
int comparison = entry.compareTo (rootData);
if (comparison == 0) { // entry == root entry
oldEntry.set (rootData);
rootNode = removeFromRoot (rootNode);
}
else if (comparison < 0) { // entry < root entry
BinaryNode
BinaryNode
rootNode.setLeftChild (newLeftChild);
}
else { // entry > root entry
BinaryNode< T > rightChild = rootNode.getRightChild ();
BinaryNode
rootNode.setRightChild (newRightChild);
}
}
return rootNode;
}
// Removes the entry in a given root node of a subtree.
// rootNode is the root node of the subtree.
// Returns the root node of the revised subtree.
private BinaryNode
{
// Case 1: rootNode has two children
if (rootNode.hasLeftChild () && rootNode.hasRightChild ())
{
// find node with largest entry in left subtree
BinaryNode
BinaryNode
// replace entry in root
rootNode.setData (largestNode.getData ());
// remove node with largest entry in left subtree
rootNode.setLeftChild (removeLargest(leftSubtreeRoot));
} // end if
// Case 2: rootNode has at most one child
else if (rootNode.hasRightChild ())
rootNode = rootNode.getRightChild ();
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
// Finds the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the node containing the largest entry in the tree.
private BinaryNode
{
if (rootNode.hasRightChild ())
rootNode = findLargest (rootNode.getRightChild ());
return rootNode;
}
// Removes the node containing the largest entry in a given tree.
// rootNode is the root node of the tree.
// Returns the root node of the revised tree.
private BinaryNode
if (rootNode.hasRightChild()) {
BinaryNode
BinaryNode
rootNode.setRightChild (root);
}
else
rootNode = rootNode.getLeftChild ();
return rootNode;
}
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public interface MaxHeapInterface
public void add (T newEntry);
public T removeMax ();
public T getMax ();
public boolean isEmpty ();
public int getSize ();
public void clear ();
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.Arrays;
public class MaxHeap < T extends Comparable < ? super T >> implements MaxHeapInterface
{
private T [] heap; // array of heap entries
private int lastIndex; // index of last entry
private static final int DEFAULT_INITIAL_CAPACITY = 25;
public MaxHeap () {
this (DEFAULT_INITIAL_CAPACITY); // call next constructor
} // end default constructor
public MaxHeap (int initialCapacity) {
// the cast is safe because the new array contains all null entries
@ SuppressWarnings ("unchecked")
T [] tempHeap = (T []) new Comparable [initialCapacity + 1];
heap = tempHeap;
lastIndex = 0;
} // end constructor
public void add (T newEntry) {
lastIndex++;
ensureCapacity ();
int newIndex = lastIndex;
int parentIndex = newIndex / 2;
while ((parentIndex > 0) && newEntry.compareTo (heap [parentIndex]) > 0) {
heap [newIndex] = heap [parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
} // end while
heap [newIndex] = newEntry;
} // end add
public T removeMax () {
T root = null;
if (!isEmpty ()) {
root = heap [1]; // return value
heap [1] = heap [lastIndex]; // form a semiheap
lastIndex--; // decrease size
reheap (1); // transform to a heap
} // end if
return root;
} // end removeMax
public T getMax () {
T root = null;
if (!isEmpty ())
root = heap [1];
return root;
} // end getMax
public boolean isEmpty () {
return lastIndex < 1;
} // end isEmpty
public int getSize () {
return lastIndex;
} // end getSize
public void clear () {
for (; lastIndex > -1 ; lastIndex--)
heap [lastIndex] = null;
lastIndex = 0;
} // end clear
// Private methods
private void reheap (int rootIndex) {
boolean done = false;
T orphan = heap [rootIndex];
int leftChildIndex = 2 * rootIndex;
while (!done && (leftChildIndex <= lastIndex))
{
int largerChildIndex = leftChildIndex; // assume larger
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex <= lastIndex) &&
heap [rightChildIndex].compareTo (heap [largerChildIndex]) > 0)
{
largerChildIndex = rightChildIndex;
} // end if
if (orphan.compareTo (heap [largerChildIndex]) < 0)
{
heap [rootIndex] = heap [largerChildIndex];
rootIndex = largerChildIndex;
leftChildIndex = 2 * rootIndex;
}
else
done = true;
} // end while
heap [rootIndex] = orphan;
} // end reheap
} // end MaxHeap
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Thanks
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help