CMSC-341 Spring 2001

Project 4

Assigned Monday 16 April, 2001
Preview Sessions Wed 18 April 20001
Thurs 19 April 2001
Due Midnight, Sunday 29 April 2001

Revision 23 April 2001

Please echo the command being processed from the file to your output.  This is something you should be doing as part of your development in any case.
Example -- when you read the command  I 45  from the file, output a line such as Inserting 45.

Revision -- 17 April 2001

Based on inquiries from several students, we have decided to make a revision to project 4 which is intended to make your life easier. If you are one of the few whose life is made a bit harder, we apologize

The definition of Lazy Deletion has been modified to mean "delete the value from the leaf, but do not update any interior nodes".
This has some ripple effect which hopefully make your job easier

The project document has been updated to reflect this change.

Background

B-Trees are a form of general M-Way trees that are primarily used for accessing data which is stored on the disk or other slow external storage device.  In some cases, all the node are stored on disk and in some applications the interior nodes are kept in memory and only the leaves which contain the data are stored on disk
In this project, you will implement a version of a B-Tree that keeps both interior nodes and data nodes in memory.  As usual, we will store integers in our tree and use integers as our keys.  You should be aware that the data stored in the leaves can be any data type and the keys are often a different data type

Description

In this project, you will implement B-tree algorithms to support insertion, deletion, and searching.  In addition, a print routine is required to print the B-tree for testing and verification purposes.  Your program will accept three command line arguments
  1. The name of a file that contains operations to perform (format below)
  2. The value of M - the maximum number of subtrees an interior node will support
  3. The value of L -- the maximum number of data elements a leaf will hold


Here are your tasks:

  1. Read and understand section 4.7 of the Weiss text (be sure to note the errors in the text on pages 166 and 167) regarding B-trees as well as any class notes or notes posted on the web for your benefit
  2. Design and implement a B-Tree as a class template which supports the ADT below..
  3. Design and implement a B-Tree node as a class template.  You may use the MWayNode discussed in class and found in Dr. Anastasio's notes as a starting point.
  4. Design and implement Proj4.C which contains main( ).  This program reads the file of operations, interprets and executes them.  You should of course provide all necessary command line argument validation.  Your program should ignore any and all blank lines and any and all invalid commands found in the file.
  5. Create a makefile for your project.

Definition of the ADT

  B-Tree ADT
            The B-Tree supports the following operations. The prototypes of these functions is left to you.

 B-Tree Node ADT
            Since the B-Tree Node is used only by the B-Tree, the B-Tree Node has NO PUBLIC INTERFACE. All B-Tree Node methods should be private.  You may make the B-Tree a friend of the B-Tree Node.  You must support the Big-4.


Command File format

The command file consists of insert, remove, search and print commands.  Blank lines may appear in the file (almost always by accident, but your program should handle them).  Invalid commands may also appear (also probably by accident).
 
  • I   XXX -  insert integer XXX
  • R XXX  - remove integer XXX – a message should be printed if XXX is not in the tree
  • S XXX  - search for integer XXX – it is only necessary to print FOUND or NOT FOUND
  • P     -  print the current B-tree according to the format described below

    • Sample Output (generated by print function)

    For each node in the B-tree, print a line in the following format
            NodeNumber Value0 Value1 Value2 Value3 . . . Value N

    Only nodes and values present in the nodes should be printed.

    Nodes are numbered as follows

    0     root node
    00   child 0 of root node
    01   child 1 of root node
    02   child 2 of root node
    03   child 3 of root node
    04   child 4 of root node
    000 child 0 of node 00
    001 child 1 of node 00
        etc.
     
    To simplify the printing, no particular order of the nodes is required.

    The output for the above B tree should be:  (order may be different; make it neat)
    0           29
    00           9    23
    01         35    44    61
    000         2      4      5      6
    001          9   16    21
    002       23    24    25
    010       29    30    31   33
    011       35    40    42
    012       44    56    58
    013       61    66    69    73
     
     

    Lazy Deletion (modified 4/17/01)

    Lazy deletion means that the data value is deleted from the leaf, but no interior nodes are updated. This does not cause a problem with further inserts, deletes or finds.

    Available Files

    The following files are available in Mr. Frey's public directory (/afs/umbc.edu/users/d/e/dennis/pub/CMSC341).  Feel free to use them as is or modify them as you wish.  In either case, be sure to submit them with your other source code.


    Files To Be Submitted

    You should submit only the files you have written, a makefile, and the file containing your answers to the questions. If you use the Linked List files from Mr. Frey's public directory, DO NOT submit them, but have your makefile reference them.  The files to be submitted are: If your makefile is set up correctly, you should be able to execute the command make submit.

    Questions

    Copy the file /afs/umbc.edu/users/d/e/dennis/CMSC341/Proj3/341-Spring01-proj4_questions.txtto your directory, then edit the file to add you answers.  Be sure to submit your file.

     

    Grading and Academic Integrity

    Project grading is described in the Project Policy handout.

    Your answers to 341-Spring01-proj4_questions.txt are worth 10% of your project grade.

    Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

    Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time. 

    Last modified on Tuesday April 17, 2001 by Dennis Frey

    email: frey@cs.umbc.edu