Please Answer in C++!

14 Laboratory 9 A database is a collection of related pieces of information that is organized for easy ret set of accounts records shown below (from accounts.dat), for instance, form an acco Programming Exercise 1 an accounts database Last name First name Account ID 6274 2843 4892 8837 1892 9523 3165 3924 6023 5290 8529 1144 Record # Johnsorn James Marcus Maurcenn 9217.23 Albright Douglas Smith Gold Carlson 51462.56 27.26 918.26 0 Mary Bruce 1496.24 386.85 9.65 16110.68 86.77 4114.26 Simon George Ellen Donald Edgar Truman Fairchild Williams 10 Each record in the accounts database is assigned a record number based on that record's relative position within the database file. You could use a record number to retrieve a record directly, much as you can use an array index to reference an array data item directly. Record numbers are assigned by the database file mechanism and are not part of the account information. As a resul they are not meaningful to database users. These users require a different record retrieval mechanism, one that is based on an account ID (the key for the database) rather than a record num Retrievals based on account ID require an index that associates each account ID with the corresponding record number. You can implement this index using a binary search tree in which each data item contains the two fields: an account ID (the key) and a record number. struct IndexBntry (Key) Account identifier // Record number int acctID; long reckum int getKey const f return acctID: Return key field BSTree IndexEntry.int> index: // Database index You build the index by reading through the database account-by-account, inserting laccount ID, record number) pairs into the tree as you progress through the file. The followi index tree, for instance, was produced by inserting account records 0-5 (shown previously) into an successive (initially) empty tree