1. Describe the general strategy for the two O(n log n) sorting algorithms (quickSort and mergeSort).
2. Identify the characteristics of a binary search tree.
3. Consider the following Binary Search Tree:
root_ 67 / \ / \ 43 76 / \ / \ 12 55 70 90Also, consider the following declaration of treeNode:
class treeNode {
Keyed element_;
treeNode left_;
treeNode right_;
treeNode (Keyed k, treeNode l, treeNode r) {
left_=l;
right_=r;
element_=k;
}
}
a. Insert a 75 into the above tree. No Code, simply redraw the tree
with 75.
b. What is in root_.right_.right_.element_?
c. Delete 43 from the original tree shown above. Redraw the complete tree with your changes.
d. Write the method that returns the element with the largest key in a BST.
public elementType largest (treeNode root) {
if (root == null) return null;
}
e. Write a recursive method that would print all elements of a tree
in the ascending order of their keys.
public void print (treeNode root) {
if (root == null) return;
4.How would you print all elements in a hash table?
5.Remember that Tree is a class that implements the interface Set. Here is the definition of Set:
public interface Set {
public void add(comparable e);
public void remove(comparable e);
public comparable find (Comparable e);
public int size();
public void dump();
public comparable[] toArray();
}
Consider the following wordAndMeaning class that implements the
comparable interface:
public class wordAndMeaning implements comparable {
public String word_;
public String meaning_;
public int compareTo (Object e) {return word__.compareTo((wordAndMeaning)e).word_);}
public String toString() {return "word= " + word_ + " meaing= " + meaning_;}
public wordAndMeaning (){}
}
Assume that we already have a Tree object constructed (list_).
Complete a code segment that would ask a user for and read a word and a
meaning for the word and creates a wordAndMeaning object.; if this object
already exists in list_, delete it first; either way, store it in
list_.
System.out.println("Enter word: ");
String word=istream.readLine();
System.out.println("Enter new Meaning: ");
String meaning=istream.readLine();
wordAndMeaning w_and_m = new wordAndMeaning();