- 作业标题：Data Structures and Algorithms - Assignment 2 - Baby Mobiles
- 课程名称：The university of Sydney COMP2123 Data Structures and Algorithms
- 完成周期：2天
All submitted work must be done individually without consulting someone else’s solutions
in accordance with the University’s Academic Dishonesty and Plagiarism policies.
Story
We are asked to test whether mobiles designed for baby cribs are balanced or not. We
model a mobile as a binary tree and each node stores the weight (a non-negative integer)
of the component of the mobile that it corresponds to. We define the imbalance of a node
as the absolute difference between the summed weight of its left and right subtrees. An
empty subtree has weight 0.
Informally, our implementation should support the following operations:
• Update the weight of a node.
• Insert a new node.
• Move the subtree rooted at a given node. This allows us to play around with the
design of the mobile.
• Find the most unbalanced node, i.e., the one with the largest imbalance. This is an
important query, since if the maximum imbalance is too high, the mobile might not
be stable enough, which could be harmful to the baby.
Your Task
Maintain a tree where each node in the tree holds a weight value as its key, as well as
the property imbalance. The value of the “imbalance” is equivalent to the absolute
difference between the summed weight of the left and right subtree of this node.
Example:
。。。
Testing
We have provided you with some test cases in the tests directory of this repository. We
will be using unit tests provided with the unittest package of python.
Running Tests
From the base directory (the one with node.py and tree.py), run
python -m unittest -v tests/test_sample_tree.py tests/test_sample_node.py
Or, running all the tests by:
python -m unittest -vv
Marking
You will be marked using a range of public and hidden tests. There won’t be additional
tests added after the due date.
All tests are between 1 to 4 marks each.
