-We store the key,value pairs in the nodes of the BST -then to traverse through the tree we can compare the keys. (The keys are also unique)
2)What is the complexity of the operations, put(), remove() and height()? Answer the previous for a guaranteed balanced and unbalanced tree
put()-O(log n) remove()-O(log n) height()-O(log n)
put()-worst case O(h) h is the height of the tree remove()-worst case O(h) h is the height of the tree height()-worst case O(h) h is the height of the tree
1)What is the complexity of verifying a word of length k k is in the Trie? Is there a structure we've covered in class that can beat this? Justify your answer. Be sure to consider k k in your answer.
The complexity is O(k),A hashtable is faster with a lookup of O(1)
A tree(a prefix tree)
The user interface should function properly, when typing in letters it should make suggestions. Attach a screenshot showing the working application.
