C++ Emplotee/Books Database Binary Search
Consider any collection of data that you can organize in at least two ways. For example, you can order employees by name or by Social Security number and books by title or by author. Note that other information about the employees or books is present in the database but is not used to organize these items. This program assumes that the search keys (for example, book title or book author) are unique and are strings. Thus, in the previous examples, the Social Security number must be a string instead of an integer, and only one book per author is permitted. Choose any set of data that conforms to these requirements, and create a text file.
Program behavior. When your program begins execution, it should read your text file. It then should provide some typical database management operations, all under user control via an interface of your design. For example, you should be able to add an item, remove an item, display (that is, retrieve) an item, and display all of the items in search-key order. You should be able to use either of two search keys to designate the item to be removed or displayed.
Implementation notes. The items in the database should be objects that contain two search keys and
additional data, all of which appear in the text file. Thus, you need to design and implement a class of these objects.
Although your program could create two dictionaries from these objects—one organized by one search key (such as the employee name) and the other organized by another search key (such as the Social Security number)—this approach could waste a substantial amount of memory due to the duplication of all of the data in both dictionaries.
A better approach revises the ADT dictionary to provide operations according to two search keys. For
example, you want to be able to remove by name and by Social Security number. The underlying data structure for the dictionary’s implementation should be a binary search tree. Actually, you will want two binary search trees so that you can organize the data in two ways: by name and by Social Security number, for example.
To avoid duplicated data, store the data in an ADT list and let each node in the binary search trees contain the position of the actual data item in the list, instead of the data item itself.
Your program can be specific to the type of database (employees, books, and so on), or it can be more general. For example, you could determine the search-key descriptions that the user interface displays by requiring that they be in the text file.