In python test_sample_node.py

Post by **answerhappygod** » Wed Mar 30, 2022 9:19 am

In python

: In Python Test Sample Node Py 1 (142.88 KiB) Viewed 28 times

: In Python Test Sample Node Py 2 (70.05 KiB) Viewed 28 times

: In Python Test Sample Node Py 3 (61.55 KiB) Viewed 28 times

: In Python Test Sample Node Py 4 (65.31 KiB) Viewed 28 times

test_sample_node.py

: In Python Test Sample Node Py 5 (126.9 KiB) Viewed 28 times

: In Python Test Sample Node Py 6 (110.1 KiB) Viewed 28 times

: In Python Test Sample Node Py 7 (104.75 KiB) Viewed 28 times

: In Python Test Sample Node Py 8 (202.93 KiB) Viewed 28 times

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: Tree: A(5) / C(2) D(8) / B(10)
Imbalance: A(4) C(10) D(0) / B(O) Move Subtree You must also support the move_subtree (node_a, node_b, left_child) function, where the subtree rooted at node_a is made into a child of node_b. left_child is a boolean value determining if node_a is the left child of node_b or its right child. If node_b already has a child as the intended position of node_a, your function should do nothing. You must ensure that the imbalance property is correct for all nodes, after moving the subtree. You can assume that node_b isn't in the subtree of node_a and you don't have to check for this. Example: A(5) / C(2) D(8) / B(10) move_subtree (D,C,false): A(5) / C(2) B(10) D(8)
Imbalance: A(20) / C(2) / B(0) D(0) Find Max Imbalance Your tree must support the find_max_imbalance() operation that returns an integer. When called, the function returns the maximum imbalance in the tree. Example: A(5) II C(2) D(8) 1 B(10) find_max_imbalance() returns 10
TO IMPLEMENT: You will need to implement these functions: node.py • __init_ add_left_child, add_right_child • update_weight tree.py . put • move_subtree find_max_imbalance (Note, you can add additional functions and variables to the classes if required, so feel free to modify and extend those as long as you leave the existing function signatures and variables intact.) Code node.py This file holds all information about the node in the tree. Properties Name Type *Node left_child right_child *Node *Node parent weight imbalance Description Pointer to the left child Pointer to the right child Pointer to the parent Weight of the node Absolute different between the weight of the left and right subtree int int Functions -_init__(weight) Initialises the properties of the node.
add_left_child(child_node) • Adds the child node as the left child of the node, does nothing if the node already has a left child. Runs calculations for updating the imbalance. add_right_child(child_node) . Adds the child node as the right child of the node, does nothing if the node already has a right child. . Runs calculations for updating the imbalance. is external) . Checks if the node is a leaf. get_left_child() (OR node.left_child) Returns the left child of that node. get_right_child() (OR node.right_child) . Returns the right child of that node. update_weight(weight) Sets the weight of the node. . Runs calculations for updating the imbalance. get_imbalance() (OR node. imbalance) Returns the imbalance of that node. tree.py The main tree file, holds all interaction with trees and nodes. Properties Name Type *Node Description Root node of the tree root
Functions put(node, child, left_child) • Add the child as the left or right child (depending on left_child) to the node, does nothing if node B also has a child there. move_subtree (node_a, node_b, left_child) Move node A to become the left or right child (depending on left_child) node B, does nothing if node B also has a child there. Runs calculations for updating the imbalance. find_max_imbalance() Returns the maximum imbalance of the tree.
1 2 from Node import Node import unittest 3 4 5 def assert_equal(got, expected, msg): 6 7 Simple assert helper 8 9 assert expected got, I "[{}] Expected: {}, got: {}".format(msg, expected, got) class SampleNodeTestCases (unittest. TestCase): Testing functionality of the Node class def setUp(self): Set up the tree to be used throughout the test This is the tree given in the sample A(5) C(2) D(8) / B(10) 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 self. A = Node (5) self.B = Node (10) self.c = Node (2) self.D = Node(8) self.C.add_left_child(self.B) self.A.add_left_child(self.c) self.A.add_right_child(self.D) def test_is_external(self): Test that the sample tree has been correctly classified assert_equal(self.A. is external(), False, "A is not external") assert_equal(self.B.is_external(), True, "B is external") assert_equal(self.c.is_external(), False, "C is not external") assert_equal(self.D.is external(), True, "D is external")
def test_get_left_child(self): Test that the sample tree returns the correct left child 46 47 48 49 50 51 52 53 54 55 56 57 58 59 assert_equal(self.A.get_left_child(), self.c, "A's left child is C") assert_equal(self.C.get_left_child(), self.B, "C's left child is B") assert_equal(self.D.get_left_child(), None, "D has no left child") assert_equal(self.B.get_left_child(), None, "B has no left child") def test_get_right_child(self): Test that the sample tree returns the correct right child 60 61 assert_equal(self.A.get_right_child(), self.D, "A's right child is D") assert_equal(self.C.get_right_child(), None, "C has no right child") assert_equal(self.D.get_right_child(), None, "D has no right child") assert_equal(self.B.get_right_child(), None, "B has no right child") 62 63 64 def test_get_imbalance(self): 65 66 Test that the sample tree returns the correct imbalance 67 68 69 assert_equal(self.A.get_imbalance(), 4, "A has an imbalance of 4") assert_equal(self.C.get_imbalance(), 10, "C has an imbalance of 10") assert_equal(self.D.get_imbalance(), 0, "D has no imbalance") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance") def test_update_weight(self): Test that the sample tree updates the weight correctly 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 self.A.update_weight(10) assert_equal(self.A.get_imbalance(), 4, "A has an imbalance of 4") assert_equal(self.C.get_imbalance(), 10, "C has an imbalance of 10") assert_equal(self.D.get_imbalance(), 0, "D has no imbalance") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance") self.B.update_weight(3) assert_equal(self.A.get_imbalance(), 3, "A has an imbalance of 3") assert_equal(self.C.get_imbalance(), 3, "C has an imbalance of 3") assert_equal(self.D.get_imbalance(), 0, "D has no imbalance") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance")
Final Tree: A(10) I C(2) D(8) / B(3) def test_propagate_imbalance(self): Test that the sample tree propagates the imbalance correctly when adding children self.D.add_right_child(Node (7)) 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 Tree: A(5) I C(2) D(8) B(10) E(7) assert_equal(self.A.get_imbalance(), 3, "A has an imbalance of 3") assert_equal(self.C.get_imbalance(), 10, "C has an imbalance of 10") assert_equal(self.D.get_imbalance(), 7, "D has an imbalance of 7") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance") assert_equal(self.D.get_right_child().get_imbalance(), 0, "E has no imbalance")
1 from Node import Node from Tree import Tree import unittest def assert_equal(got, expected, msg): Simple assert helper assert expected == got, \ "[{}] Expected: {}, got: {}".format(msg, expected, got) class SampleTreeTestCases (unittest. TestCase): Testing functionality of the Tree class def setUp(self): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 Set up the tree to be used throughout the test This is the tree given in the sample A(5) C(2) D(8) / B(10) self. A = Node (5) self.tree = Tree(self.A) self.B = Node (10) self.C = Node(2) self.D = Node(8) self.tree.put(self.A, self.c, True) self.tree.put(self.A, self.D, False) self.tree.put(self.c, self.B, True) 40 def test_construction(self): 41 42 43 44 Test that the sample tree has been correctly constructed
assert_equal(self.A.is_external(), False, "A is not external") assert_equal(self.B. is external(), True, "B is external") assert_equal(self.c.is external(), False, "C is not external") assert_equal(self.D. is external(), True, "D is external") assert_equal(self.A.get_imbalance(), 4, "A has an imbalance of 4") assert_equal(self.C.get_imbalance(), 10, "C has an imbalance of 10") assert_equal(self.D.get_imbalance(), 0, "D has no imbalance") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance") def test_put(self): Test that the sample tree puts nodes correctly E = Node(7) self.tree.put(self.c, E, False) A(5) C(2) D(8) 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 B(10) E(7) assert_equal(self.A. is external(), False, "A is not external") assert_equal(self.B.is_external(), True, "B is external") assert_equal(self.C.is_external(), False, "C is not external") assert_equal(self.D.is_external(), True, "D is external") assert_equal(E. is external(), True, "E is external") assert_equal(self.A.get_imbalance(), 11, "A has an imbalance of 11") assert_equal(self.C.get_imbalance(), 3, "C has an imbalance of 3") assert_equal(self.D.get_imbalance(), 0, "D has no imbalance") assert_equal(self.B.get_imbalance(), 0, "B has no imbalance") assert_equal(E.get_imbalance(), 0, "E has no imbalance") def test_find_max_imbalance(self): Test that the sample tree finds the correct node with the maximum imbalance assert_equal(self.tree.find_max_imbalance(), 10, "C has the maximum imbalance with value 10")