Project 1-Comparing Different Search Trees

Project 1 - Comparing Different Search Trees

本人并没完成，这里面比较有难度的是B+的删除以及红黑树的实现代码.

Project Description

Because the complete binary search tree is expensive to insert and delete, so we use avl-tree, splay-tree, red-black-tree and b-plus-tree to replace the function of complete binary search tree.

This project requires you to implement four types of search tree as above: avl-tree, splay-tree, red-black-tree and 2-3-4 b-plus-tree. You are to analyze and compare the performances of a sequence of insertions and deletions on these search tree structures. The testing must be done on a set of N distinct integers in the following ways:

• insert N integers in increasing order and delete them in the same order;
• Insert N integers in increasing order and delete them in the reverse order;
• Insert N integers in random order and delete them in random order.

The size of input can be taken from 1000 to 10000. The run times must be plotted with respect to the sizes to illustrate the difference.

Finally you should analyze in what scenarios would these four types of search tree be more appropriate respectively.

Group Presentation Submission

You should upload zip to 1-1 and slides to 1-2.

You are required to upload your submission materials in a zip file that contains the project report (in pdf format), the source code (including the implementation and the testing code), and the testing data. The file structure should be organized as follows:

PxGyy.zip
├── code
│   ├── source code files (*.c, *.h, ...)
│   └── readme.txt (Instructions on how to build the executable file and how to run it)
├── documents
│   ├── PxGyy.pdf
│   └── Other materials if necessary
└── testcases
    ├── 1.in (Input file 1, plain text in UTF-8, the same below)
    ├── 1.out (Output file 1)
    ├── 2.in
    ├── 2.out
    ├── ...
    └── readme.txt (Simple specification of testing data)

In the name of report document and zip PxGyy.pdf/zip, x is the project number (1 for this project) and yy is your group number with 2 digits, 01 for example. E.g. P1G01.zip.

• report

  The report should be written clearly and neatly in English. It should starts with a title page containing the title, the group id if you work as a group, the author names, and an abstract summarizing your work. Within the main text following the title page, the report should present the following contents.

  • A brief description of implement.
    
  • A detailed description of your experiments, including how they are designed, how the testing data are generated, how the results are obtained.
    
  • Results of your experiment and an analysis of these results.
    
  • An analysis of in what scenarios would these four types of search tree be more appropriate respectively.
    
  • Conclusion and discussion.

  You are encouraged to write your report using \(\LaTeX\) (try overleaf.com), but Microsoft Word is also fine.

• code

  Generally, you are required to implement in C or C++. You should not use any STL if you implement in C++. You may ask TA for permission if you want to use a language other than C or C++. The source code should be in good style, and have sufficient comments.

• test

  All the testing data should be stored and uploaded (even if they are randomly generated).

  A readme.txt that simply specifies the testing data is required.

• slides

  The slides should be named as PxGyy.pptx, where x is the project id and yy is your group number with 2 digits, 01 for example. E.g. P0G01.pptx. The slides should submitted to 1-2.

  Pay attention that only the group leader needs to upload the materials and submit them. Other group members do not need to upload anything, but should click the "submit" button of 1-1 and 1-2 to be graded.

Individual Bonus Submit

You should submit a zip to 1-3, and the requirement of zip is the same as above. The zip file should be named as Px_id_name.zip instead, where id is your student id and name is in English without spaces. E.g. P1_3240100000_ZhangSan.zip.

Solution