Use the trie data structure to devise a program to sort variable-length strings. The program’s running time should be proportional to the total number of letters in all of the strings. Note that some...

Use the trie data structure to devise a program to sort variable-length strings. The program’s running time should be proportional to the total number of letters in all of the strings. Note that some strings might be very long while most are short.

Revise the BST class of Section 5.4 to use the AVL tree rotations. Your new implementation should not modify the original BST class ADT. Compare your AVL tree against an implementation of the standard BST over a wide variety of input data. Under what conditions does the splay tree actually save time?