Introduction to Algorithm

package Autocompleter; import java.util.ArrayList; class Autocompleter { public // A helper class that stores a string and a frequency. class Entry { public String s; int freq; Entry(String word, int x){ s = word; freq = x; } } // A helper class that implements a binary search tree node. class Node { public Node() { height = 0; left = right = null; } Node(Entry temp) { e = temp; height = 0; left = right = null; } Entry e; int height; Node left; Node right; } // For the mandatory running times below: // n is the number of strings in the dictionary. // Assume that the length of every string is O(1). Node root; // Root of the binary-search-tree-based data structure Autocompleter() { root = null; } // A convenience method for getting the height of a subtree. // Useful for rebalance(). int height(Node cur) { if (cur == null) return -1; return cur.height; } //A convenience method for in-order traversing the tree. void inorder() { inorder_recurse(root); } void inorder_recurse(Node cur) { if (cur != null) { inorder_recurse(cur.left); for(int i=0; i<height(cur); i++) System.out.print(" "); System.out.println(cur.e.s); inorder_recurse(cur.right); } } // Adds a string x to the dictionary. // If x is already in the dictionary, does nothing. // // Run in O(log(n)) time if your insert_recurse(e, root) takes O(log n) time. void insert(String x, int freq) { Entry e = new Entry(x, freq); root = insert_recurse(e, root); } // To fill insert_recurse(e, cur) for inserting an Entry e // into an AVL tree rooted at cur. // // Must run in O(log(n)) time. Node insert_recurse(Entry e, Node cur) { } // To fill rebalance() for rebalancing the AVL tree rooted at cur. // Helpful for insert_recurse(). // Should be called on every node visited during // the search in reverse search order. // // Must run in O(1) time. Node rebalance(Node cur) { } // To fill right_rotate(cur) for the right rotation around the node cur // of an AVL tree (helpful for implementing rebalance). // // Must run in O(1) time. Node right_rotate(Node cur) { } // To fill left_rotate(cur) for the left rotation around the node cur // of an AVL tree (helpful for implementing rebalance). // // Must run in O(1) time. Node left_rotate(Node cur){ } // Returns the number of strings in the dictionary // // // Run in O(n) time if your size_recurse(root) takes O(n) time. int size() { return size_recurse(root); } // To fill size_recurse() to calculate the size of // the binary tree rooted at cur recursively. // // Must run in O(n) time. int size_recurse(Node cur) { } // Function completions(x, T) fills the Arraylist T with the three most-frequent completions of x. // If x has less than three completions, then // T is filled with all completions of x. // The completions appear in T from most to least frequent. // // It runs in O(log(n) + k) time if your completions_recurse(String x, Node cur, ArrayList<Entry> C) // takes O(log (n) +k) time, // where k is the number of completions of x in the dictionary. void completions(String x, ArrayList<String> T) { ArrayList<Entry> E = new ArrayList<Entry>(); completions_recurse(x, root, E); T.clear(); for (int i =0 ; i<E.size(); i++) { T.add(E.get(i).s); } } // To fill completions_recurse(String x, Node cur, ArrayList<Entry> C) for // Filling C with the completions of x in the BST rooted at cur. // Note Entrys in C are in ascending order by their freqs. // // Must run in O(log(n) + k), where // -n is the size of the BST rooted at root. // -k is the number of Entrys in the BST rooted at cur // whose strings start with x. void completions_recurse(String x, Node cur, ArrayList<Entry> C){ } }