Write a C++ program that create, store and manipulate a set of n fixed-length records as Modified B-tree index on a binary file. Each record consists of 5 descendants (5 Keys and 5 addresses to the actual records on a data file) + 1 integer to indicate leaf / non-leaf status (The first integer of each node, 0 means a leaf node, 1 a non-leaf node). The file at creation time (if number of records = 10) should contain the following: -1 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 - 1 - 1 -1 -1 1 -1 3 -1 -1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 4 -1 - 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 5 -1 - 1 -1 -1 1 1 6 -1 -1 -1 - 1 - 1 -1 - 1 -1 -1 7 -1 -1 - 1 - 1 -1 -1 8 - 1 -1 -1 -1 - 1 - 1 -1 -1 1 1 9 -1 -1 -1 -1 - 1 - 1 -1 -1 -1 1 -1 -1 - 1 -1 -1 -1 -1 -1 -1 -1 The first node (Node with index ZERO) will always have the index of the first empty node (at its second integer) to add a new record. Node with index ZERO will only be used to tell the next free node and no data to be added into it. Each empty node will have the index of the next empty node (at its second integer), forming a linked list of empty nodes. The index of the root node will be always the first node to insert into which is node with index 1. Your Program should handle the cases on insertion, deletion and Search For Example, Consider the following Insertions: Insert: 3, 12 Insert: 7,24 Insert: 10, 48 Insert: 24,60 Insert: 14,72 3 3 7 10 14 24 2 -1 The index file should look as follow: -1 2| 3 12 -1 -1 -1 -1 -1 -1 -1 7 24 10 48 72 24 60 14 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 4 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 After the previous insertions, Node 1 is a leaf node and all the references in it are pointing to records on data file. Consider the following Insertion: Insert: 19,84 10 24 | 10 19 124 The index file should look as follow: -1 1 10 2 -1 -1 -1 -1 -1 -1 1 24 3 -1 -1 -1 -1 -1 -1 0 3 12 7 24 10 48 -1 -1 0 14 72 19 84 24 60 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -- -1 -1 -1 9 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 After the previous insertions, Node 1 is a non-leaf node and all the references in it are pointing to other nodes on the index file. Consider the following Insertions: Insert: 30,96 Insert: 15, 108 Insert: 1, 120 Insert: 5, 132 10 30 10 14 15 19 24 30 The index file should look as follow: 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 10 2 30 3 -1 -1 -1 - 1 -1 - 1 0 1 120 3 12 5 132 7 24 10 48 0 14 72 15 108 19 84 24 60 30 196 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 - 1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 - 1 8 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 9 -1 -1 - 1 - 1 -1 -1 -1 -1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 2,144 3 10 30 1 2 2 3 3 14 15 19 24 30 10 The index file should look as follow: -1 5 5 -1 - 1 1 1 1 -1 1 3 3 2 10 4 30 3 -1 -1 -1 -1 O 1 120 2 144 3 12 1 -1 1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 10 48 -1 -1 -1 24 -1 -1 -1 - 1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 - 1 -1 1 -1 00 -1 - 1 -1 - 1 -1 1 - 1 9 -1 -1 -1 -1 -1 1 - 1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 2,144 3 10 30 1 2 2 3 3 14 15 19 24 30 10 The index file should look as follow: -1 5 5 -1 - 1 1 1 1 -1 1 3 3 2 10 4 30 3 -1 -1 -1 -1 O 1 120 2 144 3 12 1 -1 1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 10 48 -1 -1 -1 24 -1 -1 -1 - 1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 - 1 -1 1 -1 00 -1 - 1 -1 - 1 -1 1 - 1 9 -1 -1 -1 -1 -1 1 - 1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertions: Insert: 8, 156 Insert: 9,168 3 10 30 3 14 15 19 24 30 7 9 10 The index file should look as follow: 5 -1 - 1 -1 -1 -1 -1 -1 -1 1 -1 3 3 2 10 4 30 -1 -1 0 1 120 2 144 3 12 -1 -1 -1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 24 00 156 9 168 10 48 6 -1 -1 -1 -1 1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 8 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 6, 180 10 30 2 2 3 5 14 15 19 24 30 6 8 9 10 The index file should look as follow: 5 -1 -1 -1 -1 -1 1 -1 -1 1 5 2 10 4 30 -1 -1 -1 3 12 0 1 120 2 144 3 5 132 -1 0 14 72 15 108 19 84 60 30 196 24 9 0 6 180 7 24 8 156 168 10 48 6 -1 -1 -1 1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 8 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 Consider the following insertion: Irtsett: 4, 192 5 10 30 14 15 19 24 30 1 2 3 5 7 00 9 10 The index file should look as follow: 1 5 1 -1 -1 -1 1 -1 -1 -1 - 1 1 5 2 10 4 30 3 -1 -1 - 1 -1 0 1 120 2 144 3 12 4 192 5 132 0 14 72 15 108 19 84 24 60 30 196 0 6 180 7 24 8 156 9 168 10 48 -1 6 -1 -1 -1 -1 - 1 -1 -1 -1 7 -1 - 1 -1 -1 -1 -1 -1 -1 -1 8 -1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 9 -1 -1 -1 1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 - 1 -1 Consider the following insertion: Insert: 11, 204 10 15 30 3 30 1924 N 4 5 11 14 15 6 7 8 00 9 9 10 The index file should look as follow: - 1 6 -1 -1 1 -1 1 -1 -1 -1 -1 1 5 5 2 10 4 15 3 30 5 -1 -1 0 1 120 2 144 3 12 4 192 5 132 0 11 204 14 72 15 108 -1 -1 0 6 180 7 24 8 156 9 168 10 48 0 19 84 24 60 30 196 -1 -1 -1 - 1 7 -1 -1 -1 - 1 -1 -1 - 1 -1 -1 00 -1 -1 -1 -1 - 1 -1 -1 -1 -1 9 - 1 -1 -1 -1 -1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 - 1 Consider the following insertions: Insert: 12, 216 Insert: 13, 228 Insert: 17,240 Insert: 18, 252 10 15 30 2 19 3 3 17 N 4 18 5 24 30 11. 12 13 14 15 00 9 10 The index file should look as follow: - 1 -1 -1 - 1 -1 -1 6 5 -1 4 -1 5 1 1 1 2 10 15 3 30 1 0 1 120 2 144 3 12 4 192 5 132 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 00 156 9 168 10 48 0 17 240 18 252 19 84 24 60 30 196 - 1 7 -1 -1 1 - 1 -1 1 - 1 -1 11 1 8 -1 -1 -1 - 1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 16, 264 10 15 18 30 19 24 30 2 2 3 3 4 S 16 17 18 11 12 13 14 15 00 9 10 The index file should look as follow: 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 5 2 10 4 15 3 18 5 30 6 0 1 120 2 144 3 12 4 192 5 132 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 8 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 0 19 84 24 60 30 196 -1 - 1 -1 -1 -1 8 -1 - 1 -1 -1 -1 - 1 - 1 - 1 -1 -1 9 -1 -1 -1 -1 - 1 -1 -1 -1 -1 - 1 - 1 -1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 -1 Consider the following insertion: Insert: 0,276 10 30 10 18 30 O 19 24 30 16 17 18 9 10 12 13 14 15 The index file should look as follow: - 1 -1 -1 -1 -1 - 1 -1 -1 -1 1 10 00 30 9 -1 -1 -1 -1 - 1 -1 0 0 276 1 120 2 144 -1 -1 - 1 -1 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 00 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 -1 0 19 84 24 60 30 196 - 1 O 3 12 4 192 5 132 -1 -1 -1 1 2 2 5 10 4 -1 -1 -1 7 5 -1 1 1 15 3 18 30 6 -1 -1 -1 Consider the following Deletion: Delete: 13 10 30 10 30 19 20 16 17 18 20 12 14 15 The index fide should look as follow -1 -1 -1 - 1 -1 - 1 1 10 00 30 9 -1 -1 -1 -1 -1 -1 0 0 276 1 120 2 144 1 - 1 0 11 204 12 216 14 72 15 108 -1 -1 0 6 180 7 24 8 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 0 19 84 24 60 30 196 -1 -1 -1 -1 0 3 12 4 192 5 132 -1 -1 1 -1 -1 1 2 2 5 7 10 -1 1 4 6 1 1 1 15 3 18 5 30 -1 -1 1 8 -1 -1 -1 - 1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 16, 264 10 15 18 30 19 24 30 2 2 3 3 4 S 16 17 18 11 12 13 14 15 00 9 10 Write a C++ program that create, store and manipulate a set of n fixed-length records as Modified B-tree index on a binary file. Each record consists of 5 descendants (5 Keys and 5 addresses to the actual records on a data file) + 1 integer to indicate leaf / non-leaf status (The first integer of each node, 0 means a leaf node, 1 a non-leaf node). The file at creation time (if number of records = 10) should contain the following: -1 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 - 1 - 1 -1 -1 1 -1 3 -1 -1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 4 -1 - 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 5 -1 - 1 -1 -1 1 1 6 -1 -1 -1 - 1 - 1 -1 - 1 -1 -1 7 -1 -1 - 1 - 1 -1 -1 8 - 1 -1 -1 -1 - 1 - 1 -1 -1 1 1 9 -1 -1 -1 -1 - 1 - 1 -1 -1 -1 1 -1 -1 - 1 -1 -1 -1 -1 -1 -1 -1 The first node (Node with index ZERO) will always have the index of the first empty node (at its second integer) to add a new record. Node with index ZERO will only be used to tell the next free node and no data to be added into it. Each empty node will have the index of the next empty node (at its second integer), forming a linked list of empty nodes. The index of the root node will be always the first node to insert into which is node with index 1. Your Program should handle the cases on insertion, deletion and Search For Example, Consider the following Insertions: Insert: 3, 12 Insert: 7,24 Insert: 10, 48 Insert: 24,60 Insert: 14,72 3 3 7 10 14 24 2 -1 The index file should look as follow: -1 2| 3 12 -1 -1 -1 -1 -1 -1 -1 7 24 10 48 72 24 60 14 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 4 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 After the previous insertions, Node 1 is a leaf node and all the references in it are pointing to records on data file. Consider the following Insertion: Insert: 19,84 10 24 | 10 19 124 The index file should look as follow: -1 1 10 2 -1 -1 -1 -1 -1 -1 1 24 3 -1 -1 -1 -1 -1 -1 0 3 12 7 24 10 48 -1 -1 0 14 72 19 84 24 60 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -- -1 -1 -1 9 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 After the previous insertions, Node 1 is a non-leaf node and all the references in it are pointing to other nodes on the index file. Consider the following Insertions: Insert: 30,96 Insert: 15, 108 Insert: 1, 120 Insert: 5, 132 10 30 10 14 15 19 24 30 The index file should look as follow: 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 10 2 30 3 -1 -1 -1 - 1 -1 - 1 0 1 120 3 12 5 132 7 24 10 48 0 14 72 15 108 19 84 24 60 30 196 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 - 1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 - 1 8 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 9 -1 -1 - 1 - 1 -1 -1 -1 -1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 2,144 3 10 30 1 2 2 3 3 14 15 19 24 30 10 The index file should look as follow: -1 5 5 -1 - 1 1 1 1 -1 1 3 3 2 10 4 30 3 -1 -1 -1 -1 O 1 120 2 144 3 12 1 -1 1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 10 48 -1 -1 -1 24 -1 -1 -1 - 1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 - 1 -1 1 -1 00 -1 - 1 -1 - 1 -1 1 - 1 9 -1 -1 -1 -1 -1 1 - 1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 2,144 3 10 30 1 2 2 3 3 14 15 19 24 30 10 The index file should look as follow: -1 5 5 -1 - 1 1 1 1 -1 1 3 3 2 10 4 30 3 -1 -1 -1 -1 O 1 120 2 144 3 12 1 -1 1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 10 48 -1 -1 -1 24 -1 -1 -1 - 1 6 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 - 1 -1 1 -1 00 -1 - 1 -1 - 1 -1 1 - 1 9 -1 -1 -1 -1 -1 1 - 1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertions: Insert: 8, 156 Insert: 9,168 3 10 30 3 14 15 19 24 30 7 9 10 The index file should look as follow: 5 -1 - 1 -1 -1 -1 -1 -1 -1 1 -1 3 3 2 10 4 30 -1 -1 0 1 120 2 144 3 12 -1 -1 -1 -1 0 14 72 15 108 19 84 24 60 30 196 0 5 132 7 24 00 156 9 168 10 48 6 -1 -1 -1 -1 1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 8 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 6, 180 10 30 2 2 3 5 14 15 19 24 30 6 8 9 10 The index file should look as follow: 5 -1 -1 -1 -1 -1 1 -1 -1 1 5 2 10 4 30 -1 -1 -1 3 12 0 1 120 2 144 3 5 132 -1 0 14 72 15 108 19 84 60 30 196 24 9 0 6 180 7 24 8 156 168 10 48 6 -1 -1 -1 1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 8 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 -1 Consider the following insertion: Irtsett: 4, 192 5 10 30 14 15 19 24 30 1 2 3 5 7 00 9 10 The index file should look as follow: 1 5 1 -1 -1 -1 1 -1 -1 -1 - 1 1 5 2 10 4 30 3 -1 -1 - 1 -1 0 1 120 2 144 3 12 4 192 5 132 0 14 72 15 108 19 84 24 60 30 196 0 6 180 7 24 8 156 9 168 10 48 -1 6 -1 -1 -1 -1 - 1 -1 -1 -1 7 -1 - 1 -1 -1 -1 -1 -1 -1 -1 8 -1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 9 -1 -1 -1 1 - 1 -1 - 1 -1 -1 -1 -1 -1 -1 - 1 -1 Consider the following insertion: Insert: 11, 204 10 15 30 3 30 1924 N 4 5 11 14 15 6 7 8 00 9 9 10 The index file should look as follow: - 1 6 -1 -1 1 -1 1 -1 -1 -1 -1 1 5 5 2 10 4 15 3 30 5 -1 -1 0 1 120 2 144 3 12 4 192 5 132 0 11 204 14 72 15 108 -1 -1 0 6 180 7 24 8 156 9 168 10 48 0 19 84 24 60 30 196 -1 -1 -1 - 1 7 -1 -1 -1 - 1 -1 -1 - 1 -1 -1 00 -1 -1 -1 -1 - 1 -1 -1 -1 -1 9 - 1 -1 -1 -1 -1 -1 - 1 - 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 - 1 Consider the following insertions: Insert: 12, 216 Insert: 13, 228 Insert: 17,240 Insert: 18, 252 10 15 30 2 19 3 3 17 N 4 18 5 24 30 11. 12 13 14 15 00 9 10 The index file should look as follow: - 1 -1 -1 - 1 -1 -1 6 5 -1 4 -1 5 1 1 1 2 10 15 3 30 1 0 1 120 2 144 3 12 4 192 5 132 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 00 156 9 168 10 48 0 17 240 18 252 19 84 24 60 30 196 - 1 7 -1 -1 1 - 1 -1 1 - 1 -1 11 1 8 -1 -1 -1 - 1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 16, 264 10 15 18 30 19 24 30 2 2 3 3 4 S 16 17 18 11 12 13 14 15 00 9 10 The index file should look as follow: 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 5 2 10 4 15 3 18 5 30 6 0 1 120 2 144 3 12 4 192 5 132 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 8 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 0 19 84 24 60 30 196 -1 - 1 -1 -1 -1 8 -1 - 1 -1 -1 -1 - 1 - 1 - 1 -1 -1 9 -1 -1 -1 -1 - 1 -1 -1 -1 -1 - 1 - 1 -1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 -1 Consider the following insertion: Insert: 0,276 10 30 10 18 30 O 19 24 30 16 17 18 9 10 12 13 14 15 The index file should look as follow: - 1 -1 -1 -1 -1 - 1 -1 -1 -1 1 10 00 30 9 -1 -1 -1 -1 - 1 -1 0 0 276 1 120 2 144 -1 -1 - 1 -1 0 11 204 12 216 13 228 14 72 15 108 0 6 180 7 24 00 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 -1 0 19 84 24 60 30 196 - 1 O 3 12 4 192 5 132 -1 -1 -1 1 2 2 5 10 4 -1 -1 -1 7 5 -1 1 1 15 3 18 30 6 -1 -1 -1 Consider the following Deletion: Delete: 13 10 30 10 30 19 20 16 17 18 20 12 14 15 The index fide should look as follow -1 -1 -1 - 1 -1 - 1 1 10 00 30 9 -1 -1 -1 -1 -1 -1 0 0 276 1 120 2 144 1 - 1 0 11 204 12 216 14 72 15 108 -1 -1 0 6 180 7 24 8 156 9 168 10 48 0 16 264 17 240 18 252 -1 -1 -1 -1 0 19 84 24 60 30 196 -1 -1 -1 -1 0 3 12 4 192 5 132 -1 -1 1 -1 -1 1 2 2 5 7 10 -1 1 4 6 1 1 1 15 3 18 5 30 -1 -1 1 8 -1 -1 -1 - 1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 Consider the following insertion: Insert: 16, 264 10 15 18 30 19 24 30 2 2 3 3 4 S 16 17 18 11 12 13 14 15 00 9 10