In this assignment, we will consider both random search trees and splay trees as data structures for maintaining password files. Each time you log on the computer and enter a password, the operating system has to look you up in a password file to check whether your password is correct. Since new users are always being added to the system, we want our password file to support both insertion and query operations. A random or balanced search tree would work, but it would fail to exploit either locality or frequency of reference. Certain people log on far more often than others, and we would want them up near the top of the search tree.
Most people use computers in spurts, ie.
Thus we want people who logged on recently to also, appear high in the tree. Splay trees can take advantage of both these phenomena. These logins were made by approximately 250 different users, so the average user logged on over forty times in this interval. However, the login frequency is very non-uniform. Starting from an empty random search tree and an empty splay tree, your program will read user ids one at a time, and proceed to search for each user in both of the two trees.