代写program、c/c++，Java程序语言代做

日期：2024-11-21 09:41

I&C SCI 46 Fall 2024 Project 4: Finding Balance in Nature

Due at 9:30 AM. You may use late submissions as usual.

Reviewing related material

I encourage you to review your lecture notes for the Binary Search Tree portions of this class,

especially the portions about balancing trees. The data structure we covered this quarter for a

balanced tree is called a Crumple Tree. Supplemental reading is posted on Canvas.

Very important note: it is not enough to implement some type of binary search tree for this

assignment. For the vast majority of the points, your type must be a Crumple Tree. Attempting

to fool the auto-grader is a decidedly bad idea.

Requirements

In this project you will be implementing the Level-balanced tree data structure as a class named

CrumpleTree. The class consists of the following functions which you are responsible for

implementing and have been started for you in CrumpleTree.hpp:

CrumpleTree()

This is the constructor for the class. You should initialize any variables you add to the

class here.

~CrumpleTree()

This is the class destructor. You are responsible for freeing any allocated memory here.

You will most likely be allocating memory to store the nodes within the tree. Since these

allocations need to be dynamic, as we don’t know how large the tree will be, they should

be freed here in the destructor. It’s your job to come up with a traversal algorithm to

accomplish this. Note, if you elect to use shared pointers or unique pointers the compiler

will generate code to deallocate the memory for you if certain conditions are met. You

should only use these features of the standard library if you already understand them or

are willing to put in extra effort. In most industry settings features like these will be used

as opposed to explicitly implemented destructors.

However, be advised that course staff are not expected to know these and might not be

able to help you debug problems with them. If you are unfamiliar with shared or unique

pointers, use traditional (raw) pointers if you are expecting help with debugging.

[[nodiscard]] size_t size() const noexcept

This function returns the number of keys stored in the tree. It returns the count as a

size_t. It is marked const (also known as a constant member function) because it

should not modify any member variables that you’ve added to the class or call any

function functions that are not marked const as well. The advantage of marking this

function as const is that it can be called on constant CrumpleTree instances. It also

allows the compiler to make additional optimizations since it can assume the object this

function is called on is not changed. This is a fairly good StackOverflow answer that

goes into additional detail.

[[nodiscard]] bool empty() const noexcept

This function simply returns whether or not the tree is empty, or in other words, if the tree

contains zero keys. Marked const because it should not change any member data.

Marked noexcept because it should not throw any exceptions.

bool contains(const K & key) const noexcept

Simply checks to see if the key k is stored in the tree. True if so, false if not. Once

again, this function does not modify any member data, so the function is marked const.

Since this is a balanced tree, this function should run in O(log N) time where N is the

number of keys in the tree. This is accomplished through the on-demand balancing

property of Crumple Trees and a consequence of the height of the tree never exceeding

O(log N). IMPORTANT: when comparing keys, you can only assume that the < and ==

operator has been defined. This means you should not use any other comparison

operators for comparing keys.

std::optional<unsigned> Level(const K & key) const

This returns the level on which the given key is stored in the tree. If the tree does not

contain this key, return std::nullopt.

IMPORTANT: when comparing keys, you can only assume that the < and == operator

has been defined. This means you should not use any other comparison operators for

comparing keys.

Value & find(const K & key)

Like contains(), this function searches for key k in the tree. However, this function

returns a reference to the value stored at this particular key. Since this function is not

marked const, and it does not return a const reference, this value is modifiable through

this interface. This function should also run in O(log N) time since it is bound by the

height of the tree. If the key k is not in the tree, a std::runtime_error should be

thrown.

const Value & find(const K & key) const

Same as the constant version of find, but returns a constant reference to the stored

value, which prevents modification. This function is marked const to present the find

(or “lookup”) interface to instances of CrumpleTree which are marked const

themselves. This means that member data should not be modified in this function. For

example, the following code would call the version of find() marked constant:

CrumpleTree<int, int> tree;

const CrumpleTree<int, int> & treeRef= tree;

treeRef.find(1);

Warning: this function will not be compiled until you explicitly call it on a constant

CrumpleTree as in the example above. If you submit code to GradeScope, and that

system says it does not compile, make sure you've done this. You will end up with a

zero on the assignment if your code does not compile when I pair it with test cases that

call every function. Testing comprehensively is your responsibility!

void insert(const K & key, const V & value)

Adds a (key, value) pair to the tree. If the key already exists in the tree, you may do as

you please (no test cases in the grading script will deal with this situation). The key k

should be used to identify the location where the pair should be stored, as in a normal

binary search tree insertion. Since this is an level-balanced tree, the tree should be

rebalanced if this insertion results in an unbalanced tree.

Note: this is by far the most difficult part of this project.

void remove(const K & key)

Removes the given key from the tree, fixing the balance if needed. If the parameter does

not exist in the tree, do not modify the tree.

I recommend you work on both insert and remove in parts; do not attempt to do the

entire insert, or entire remove, in one session. Test that you are able to get some cases

to pass before moving onto other types of cases.

[[nodiscard]] std::vector<K> inOrder() const

Returns a vector consisting of the keys in the order they would be explored during an

in-order traversal as mentioned in class. Since the traversal is “in-order”, the keys should

be in ascending order.

IMPORTANT: this function, as well as preOrder() and postOrder(), are easy to forget to

test separately. Be very careful with these three, as their value (in terms of test cases

that rely on them) is disproportionately high. Please be absolutely sure you got these

right.

[[nodiscard]] std::vector<K> preOrder() const

Returns a pre-ordering of the tree. For the purpose of this assignment, the left subtree

should be explored before the right subtree.

[[nodiscard]] std::vector<K> postOrder() const

Returns a post-ordering of the tree. For the purpose of this assignment, the left subtree

should be explored before the right subtree.

Additional Notes

● Your implementation must be templated as provided.

○ Be sure yours works for non-numeric types! char is a numeric type.

○ Review the warnings in the lab manual, the grading policies, and in particular the

warning about templated code in the “Grading Environment” section.

● You do not need to write a copy constructor or an assignment operator on this project,

but knowing how to do so is generally a good thing.

● As stated in the contains() function: for comparing keys, use the “natural” comparison

offered by <. You should assume that < and == are defined for any object used for Key.

Any test cases provided will have something for the key that has this defined.

● The project will not build by default because a reference to a local variable is returned in

the find() functions. You will need to write an implementation that doesn’t do this.

Restrictions

Your implementation must be implemented via linked nodes in the tree format from the lecture.

That is, you may not have a “vector-based tree.” This means you will probably need to create a

new structure inside of your CrumpleTree class which will represent the nodes.

You may use smart pointers if you would like to do so. However, course staff are not required to

help you with smart pointers, including debugging code that uses them. I advise students who

are not already familiar with smart pointers to not use them for this project; they're good to

learn, but this is not the project on which to learn them.

You may not use any containers in the C++ standard template library in this assignment except

for std::vector. Furthermore, std::vector may only be used when implementing the

three traversals (in-order, pre-order, post-order). For what it’s worth, you won’t miss it for this

assignment. As always, if there’s an exception that you think is within the spirit of this

assignment, please let me know.

Your implementation does not have to be the most efficient thing ever, but it cannot be “too

slow.” In general, any test case that takes 30 seconds on GradeScope may be deemed a

wrong answer, even if it will later return a correct one. The memory check cases have a

significantly higher timeout period, and are cases which your code will very likely complete (if we

aren't running memcheck on the same code) in milliseconds.

For any assignment in this class, including this one, you may not use the directive using

namespace std; anywhere in your code. Doing so will earn you a zero for the project.

If you are found to be attempting to fool the auto-grader, perhaps by implementing a

different type of balanced binary search tree, this will be treated as a serious case of

academic dishonesty -- it will result in a report to AISC and an F in the class.

In the past, a small subset of students have attempted to contact the inventors of Crumple Trees

to get help on this project. This does not qualify as seeking reasonable help, and there are

plenty of UCI course resources available to you.

Additional Grading Note

This is an additional warning that the public tests are not comprehensive. Remember that the

compiler does not compile functions which are not used. Thus, at the bare minimum you should

add additional unit tests which get all of your code to compile. This has been a problem in the

past; do not ignore that warning. Using different template types will help to make sure you

don’t accidentally bake in assumptions about the type of the Key or Value. Always commit your

unit tests with your code.

The points available for this project are broken down into three categories:

● Basic BST functionality. To have your code tested to earn these points, you must pass

all test cases marked [RequiredBasicFunctionality]. Nothing in this portion requires that

you have a balanced tree, although it is possible that a poor implementation of balancing

could "break" this; please be careful. This portion is worth 1 point

● Crumple Tree functionality. To have your code tested to earn these points, you must

pass all test cases marked [RequiredCrumpleTree]. This portion is worth YY points.

Note that you do not need full CrumpleTree functionality to pass the required cases,

which would allow you to be evaluated on the remaining ones. This is one reason we

recommend you work with cases. This portion is worth 4 points.

○ There may be test cases within this that require only insertion procedure to work

correctly. However, the required case prerequisite requires you to get at least one

delete case to work properly. This is on purpose.

● Memory check. Some of these cases will require some simple functionality to be

reasonably efficient; this is due to a constraint with how long GradeScope will run a

submission. We test with small cases that would run quickly if we were not checking for

memory, and we give a good maximum amount of time for each to run (7-10 minutes

each). This portion is worth 1 point.

Frequently Asked Questions (FAQs)

Q1. Does _____ make problem-solving in this project trivial or is it allowed?

The following parts are permitted for use in this project: std::pair, std::max, std::abs,

std::swap. If you have another part of the standard library in mind, please ask on edStem.

Q2. Are we allowed to include the <functional> library so I can make a lambda function recursive?

Sure, if you think it will help you.

Q3. Can I include parts of the standard library to test my trees?

You can use any library for debugging purposes. The only disallowed functions are for the

final, active submission, submitted to GradeScope.

Q4. Can you use the vectors you got from the in-order, pre-order, or post-order functions in other

functions?

No. You also don't need to. However, you may use std::vector within helper functions of

in/pre/post order traversals.

Q5. Are we allowed to use stacks/queues for the inorder/postorder/preorder functions?

No. You are not allowed to use any standard containers except for in your traversal

implementations where you are allowed only std::vector.

Q6. Are we allowed to use vectors or arrays to store shapes?

No, but I'm sure you could do the same without using an array or vector.

Q7. Are > (greater than) and <= (equal to or greater than) off-limits when comparing keys?

Yes, any other operators other than < (less than) and == (equal to) are off-limits when

comparing keys.

Q8. Can I use recursion to destruct the trees?

You can use recursion for a destructor. However, you should also consider the off chance that

the stack size is exceeded and the destruction fails resulting in unfreed memory.

Q9. What to do if the passed in key does not exist in the remove() function?

You can handle this case as desired; we will not be testing it.

Q10. If the deleted node is not a leaf and has two children, should we replace it with successor or

predecessor?

Both are correct to do, and the grading script will accept either.

Q11. Do we need to have O(log n) time complexity for insert and remove?

That is the target time for balanced binary search trees, including Crumple trees.

Q12. Are we allowed to implement other level-balancing binary search trees on project 4?

No.

Q13. Are we expected to handle very large trees?

Yes, you can assume that the size of the tree will not exceed the maximum uint64_t value.

Q14. Am I permitted to add my new function to the class?

Yes. Also, it doesn’t matter where you make the helper functions as long as you don't change

the public functions and their parameters.