Assignment: Colour Trees
数据结构与算法代写 There is a hierarchy of colours, and an ordering exists to determine which is the dominating colour that will be propagated.
Story
We are asked to design a tree capable of storing a certain propagating colour. Which colour is propagated is determined by the colours sorted in its subtree. There is a hierarchy of colours, and an ordering exists to determine which is the dominating colour that will be propagated. This tree is used to do some elemental property checking to run some “what if” scenarios.
Informally, our implementation should support the following:
- Update the colour of a node.
- Insert a new node.
- Swap two subtrees. This is intended to help us answer questions such as “What changes to the propagating colors if the descendants were different?”.
- Property checking: Given a node, does every descendant (up to k levels deeper) of this node have a certain color.
About the tree 数据结构与算法代写
The tree contains a colour propagation, based on the hierarchy:
- RED (R)
- GREEN (G)
- BLUE (B)
- CYAN (C)
- YELLOW (Y)
With RED being the strongest colour.
The tree:
Will produce the propagations:
Code
You are asked to implement 2 major files, node.py and tree.py.node.py.
node.py
This is the implementation of an element in the tree, or a node of the tree.
Properties
- colour – The colour of the node.
- propagated_colour – The colour that has been propagated.
- parent – A pointer to the parent node, None if it is the root.
- children – A list of pointers to the children of this node.
Functions
set_parent(self, parent: ‘Node’) -> None
Sets the parent of the node, takes a parent Pointer (type Node).
update_colour(self, colour: Colour) -> None
Updates/Changes the colour of the node, by setting the colour attribute and performing any relevant calculations for that node.
add_child(self, child_node: ‘Node’) -> None
Adds the child_node to the list of children for the node.
remove_child(self, child_node: ‘Node’) -> None
Removes the child_node from the list of children of this node.
Tree
This is the tree implementation, and where most of the interaction will come from.
Properties 数据结构与算法代写
- root – A pointer to the root node of the tree.
Functions
update_node_colour(self, n: Node, new_colour: Colour) -> None
Updates the colour of the given node n with the colour new_colour. Should also perform any relevant actions relating to the tree.
put(self, parent: Node, child: Node) -> None
Adds a node into the tree, by adding child to parent. This should also perform any relevant calculations that are required.rm(self, child: Node) -> None
Removes the child from the tree. PLEASE NOTE if this node has children, they are removed at the same time, we can consider this entire subtree rooted at this child node removed from the tree.
swap(self, subtree_a: Node, subtree_b: Node) -> None
Swaps the tree rooted at subtree_a with the tree rooted at subtree_b and performs any relevant calculations.
is_coloured_to_depth_k(self, start_node: Node, colour: Colour, k: int) -> bool
Perform the property checks to see whether all nodes in the subtree (up and including level k starting from the start node) have the same colour!
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 will not be additional
tests added after the due date.
All tests are between 1 to 5 marks each.
Tree.py
“””
Tree
—-
This file contains the tree data structure that will be used for interacting with our coloured nodes.
The tree contains a “root” node, which is the topmost node of the tree.
It is interconnected through children and finally ends at external nodes ending at the leaves.
*** Assignment Notes ***
This is the main file that will be tested, you must implement the related functions with a TODO annotated.
Your task is to implement these methods.
“””
from node import Node
from colours import Colour
class Tree:
“””
Tree Class 数据结构与算法代写
———-
Contains the data structure of a tree, where each node of the tree has a parent and children.
If a node has no parent, it is considered the “root” of the tree. If a node has zero (0) children, it is a leaf (or is “external”).
Each node in the tree has the type `Node`, which is defined in `node.py`.
====== Functions ======
– __init__ : Sets up the tree with a specified root.
– put(node, child) : Adds the `child` to the `node`.
– swap(subtree_a, subtree_b) : Swaps the position of the subtrees.
– is_coloured_to_depth_k(node, colour, k) : Checks that the subtree rooted
at `node` has the same colour until `k` levels deep.
== Things to note ==
- Every node given as an argument WILL be in the tree, you do not have to check whether it exists in the tree.
- Every node will be initialised with a parent (unless it is the root node of the tree).
- The ordering of the children does not matter.
“””
def __init__(self, root: Node) -> None:
“””
Initialises the tree with a root of type `Node` from `node.py`
:param root: The root node of our tree.
“””
self.root = root 数据结构与算法代写
def update_node_colour(self, n: Node, new_colour: Colour) -> None:
“””
Update the colour of a node.
:param n: The node to change the colour of.
:param new_colour: The new colour to change to.
“””
# Call update_colour() on the node
# TODO implement me please.
def put(self, parent: Node, child: Node) -> None:
“””
Inserts a node into the tree.
Adds `child` to `parent`.
:param parent: The parent node currently in the tree. 数据结构与算法代写
:param child: The child to add to the tree.
“””
# TODO implement me please.
def rm(self, child: Node) -> None:
“””
Removes child from parent.
:param child: The child node to remove.
“””
# TODO implement me please.
def swap(self, subtree_a: Node, subtree_b: Node) -> None:
“””
Swaps subtree A with subtree B :param subtree_a : Root of the subtree A.
:param subtree_b : Root of the subtree B. 数据结构与算法代写
Example:
A
/ \
B C
/ / \
D J K
SWAP(B, C)
A
/ \
C B
/ | \
J K D
SWAP(D, C)
A
/ \
D B
\
C
/ \
J K
“””
# TODO implement me please.
def is_coloured_to_depth_k(self, start_node: Node, colour: Colour, k: int) -> bool: “””
Checks whether all nodes in the subtree (up and including level `k`
starting from the start node) have the same colour!
(This checks node.colour)
:param start_node : The node to start checking.
:param colour: The colour to compare a node’s colour to. 数据结构与算法代写
:param k: The depth we should check until.
=== Examples ===
(start)—> G
/ \
G G
/| |
G R G
|
R
is_coloured_to_depth_k(start, Colour.GREEN, 0) => True
is_coloured_to_depth_k(start, Colour.RED, 0) => False
is_coloured_to_depth_k(start, Colour.GREEN, 1) => True
is_coloured_to_depth_k(start, Colour.GREEN, 2) => False
” ” ”
# TODO implement me please.
return False
node.py
” ” ”
Tree Node
———
This file contains the information for the tree nodes.
Each node contains a property (colour), the parent and list of children (unordered list).
This node comes with the operations required for basic functionality.
You need to finish off some of those functions though 🙂
” ” ”
from colours import Colour
class Node:
” ” ”
Node Class
———-
Contains the relevant functions to provide a node in the tree.
The node has a property, “colour”, which represents the colour of the node. 数据结构与算法代写
IMPORANT: **Every node MUST have a colour, there are no blank nodes**
Functions:
* add_child(child_node: Node) : adds the child node to the list of children.
* update_colour(colour: Colour) : changes the colour of this node.
* is_external() -> bool : Checks if the node is a leaf, returns true if is leaf.
* children() -> list(Node) : Returns the list of children in this node.
“””
def __init__(self, colour: Colour) -> None:
” ” ”
Initialises the node with the required elements.
:param colour: The colour of the node.
“””
self.colour = colour
self.parent = None
self.children = []
self.propagated_colour = colour
def set_parent(self, parent: ‘Node’) -> None:
“””
Sets a node’s parent to the given node. 数据结构与算法代写
:param parent: The pointer to the parent of this node.
“””
self.parent = parent
def update_colour(self, colour: Colour) -> None:
“””
Updates the colour of the node.
(HINT) if we don’t give a colour, you shouldn’t update it. 数据结构与算法代写
:param colour: The new colour to set the node.
“””
# TODO implement me please
def add_child(self, child_node: ‘Node’) -> None:
“””
Adds a child node to the list of children of this node.
(HINT) this should also perform some _things_.
:param child_node: The pointer to the child node to add to children.
“””
# TODO implement me please def remove_child(self, child_node: ‘Node’) -> None:
“””
Removes the child from the list of children.
NOTE: You don’t have to worry about adding the subtree of this node to the children, we are removing this child_node and all its subtree from existence.
:param child_node: The pointer to the child node to remove. 数据结构与算法代写
“””
# TODO implement me
def get_children(self) -> list:
“””
Returns the list of children for this current node.
:return: The list of children
“””
# Note: this is also accessible with `node.children`, but we want to
# keep this here for usage in other languages people may be used to.
return self.childrenREADME.md
Assignment : Colour Trees 数据结构与算法代写
————————–
All submitted work must be *done individually* without consulting someone else’s solutions in accordance with the University’s [Academic Dishonesty and Plagiarism](https://sydney.edu.au/students/academic-dishonesty.html) policies.
## Story
We are asked to design a tree capable of storing a certain propagating colour. Which colour is propagated is determined by the colours sorted in its subtree. There is a hierarchy of colours, and an ordering exists to determine which is the dominating colour that will be propagated. This tree is used to do some elemental property checking to run some “what if” scenarios.
Informally, our implementation should support the following:
* Update the colour of a node.
* Insert a new node.
* Swap two subtrees. This is intended to help us answer questions such as “What changes to the
propagating colors if the descendants were different?”. 数据结构与算法代写
* **Property checking**: Given a node, does every descendant (up to k levels deeper) of this node have a certain color.
### About the tree
The tree contains a colour propagation, based on the hierarchy:
- RED (R)
- GREEN (G)
- BLUE (B)
- CYAN (C)
- YELLOW (Y)With **RED** being the strongest colour.
The tree:
“`
Y
/ \
C G
\ \
R Y
“`
Will produce the propagations:
“`
R
/ \
R G
\ \
R Y
“`
## Code
You are asked to implement 2 major files, `node.py` and `tree.py`.
### node.py
This is the implementation of an element in the tree, or a node of the tree.**Properties**
* `colour` – The colour of the node.
* `propagated_colour` – The colour that has been propagated.
* `parent` – A pointer to the parent node, `None` if it is the root.
* `children` – A list of pointers to the children of this node.
#### Functions
**set_parent(self, parent: ‘Node’) -> None**
Sets the parent of the node, takes a parent Pointer (type Node).
**update_colour(self, colour: Colour) -> None**
Updates/Changes the colour of the node, by setting the `colour` attribute and performing any relevant calculations for that node.
**add_child(self, child_node: ‘Node’) -> None** 数据结构与算法代写
Adds the `child_node` to the list of children for the node.
**remove_child(self, child_node: ‘Node’) -> None**
Removes the `child_node` from the list of children of this node.
### Tree
This is the tree implementation, and where most of the interaction will come from.**Properties**
* `root` – A pointer to the root node of the tree.
#### Functions
**update_node_colour(self, n: Node, new_colour: Colour) -> None**
Updates the colour of the given node `n` with the colour `new_colour`.
Should also perform any *relevant actions* relating to the tree.
**put(self, parent: Node, child: Node) -> None**
Adds a node into the tree, by adding `child` to `parent`.
This should also perform any relevant calculations that are required. 数据结构与算法代写
**rm(self, child: Node) -> None**
Removes the child from the tree.
**PLEASE NOTE** if this node has children, they are removed at the same time, we can consider this entire subtree rooted at this `child` node removed from the tree.
**swap(self, subtree_a: Node, subtree_b: Node) -> None**
Swaps the tree rooted at `subtree_a` with the tree rooted at `subtree_b` and performs any relevant calculations.
**is_coloured_to_depth_k(self, start_node: Node, colour: Colour, k: int) -> bool**
Perform the property checks to see whether all nodes in the subtree (up and including level `k`
starting from the start node) have the same colour!
## 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 will **not** be additional tests added after the due date.
All tests are **between 1 to 5 marks each**.
更多代写：文科网课代修 lsat代考 物理代上网课价格 信息技术专业essay代写 新西兰音乐学论文代写 海外论文代写
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
