数据结构与算法代写-代写Python code-algorithm代写
数据结构与算法代写

数据结构与算法代写-代写Python code-algorithm代写

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 ==

  1. Every node given as an argument WILL be in the tree, you do not have to check whether it exists in the tree.
  1. Every node will be initialised with a parent (unless it is the root node of the tree).
  1. 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:

  1. RED (R)
  2. GREEN (G)
  3. BLUE (B)
  4. CYAN (C)
  5. 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代写 论文代写 写手招聘 英国留学生代写

数据结构与算法代写
数据结构与算法代写

发表回复