Assume that an ordered dictionary is implemented using a binary search tree, and
ID: 3809840 • Letter: A
Question
Assume that an ordered dictionary is implemented using a binary search tree, and each node v in the tree has the eld v.size. For this problem you goal is to design an algorithm for ndAllElements(k) and countAllElements(k). The rst method should return a container that has all the elements in the dictionary with key equal to k; the second method should return the number of elements in the dictionary with key equal to k. Now the two methods are very similar but your algorithm for ndAllElements(k) should run in O(h + s) time where h is the height of the tree and s is the size of the output while countAllElements(k) should just run in O(h) time.
So why O(h+s) time for ndAllElements(k)? This running time may look odd; if you think about it though not only should the running time for ndAllElements(k) depend on the height of the tree but also on how many items are in the output. If the output is large – say it’s all the items – then the dominant term in h + s is s. But if the output is small, then the dominant term in h + s is h. But 1 because we don’t know in advance what the output will be, the running time is expressed as O(h + s).
But why O(h) time and not O(h+s) time for countAllElements(k)? Basically in ndAllElements(k), you have to at least visit every node that contains an item with key k. These visitations account for the s part in O(h + s) part. For countAllElements(k), however, it is possible to design an algorithm so that the number of nodes that contains an item with key k you visit is just O(h) – i.e., you may not have to visit all such nodes. To do this, take advantage of the size elds.
Explanation / Answer
The method description are not clear. No idea what it meants by " container that has all the elements in the dictionary with key equal to k" . I am assuming that it means return all the child nodes of the Node whose value "startsWith" the value "k". Examples could have been helpful.
You can change the code accordingly if the question meant Key contains, equal, or startswith the string "k". You can find "edit this while condition" above the code where you should change.
CODE STARTS
##############################################################################################
import java.util.ArrayList;
import java.util.List;
public class Chegg_06_03_2017_01 {
static BinaryTree bt;
// Auxiliary Method that return the node which starts with the provided
// string els returns null if no match
public static BinaryNode getNode(String k) {
BinaryNode currentNode = null;
// check if tree is empty
if (bt.root == null)
return null;
else {
currentNode = bt.root;
// Loop will execute until currentNode is null or it finds a String
// which starts with k
// edit this while condition
while (currentNode != null && !currentNode.data.startsWith(k)) {
if (k.compareTo(currentNode.data) > 0) {
currentNode = currentNode.right;
} else {
currentNode = currentNode.left;
}
}
}
return currentNode;
}
public static List<BinaryNode> ndAllElements(String k) {
// get The node which matches the string k
BinaryNode node = getNode(k);
List<BinaryNode> container = new ArrayList<>();
if (node != null) {
// load the container
loadContainer(node, container);
}
return container;
}
// Auxiliary method that stores all the child nodes of the root node.
public static void loadContainer(BinaryNode root, List<BinaryNode> container) {
//simple Pre Order traversal Code.
if (root != null) {
container.add(root);
loadContainer(root.left, container);
loadContainer(root.right, container);
}
}
public static int countAllElements(String k) {
return getNode(k).size;
}
public static void main(String[] args) {
// assign bt with the binary tree
bt = null;
// assign k
String k = "";
System.out.println(ndAllElements(k));
System.out.println(countAllElements(k));
}
}