加权二叉树的实现与单元测试(python)

加权二叉树，每个节点存储权值(非负整数)。我们定义节点的inbalance作为它的左右子树的和权值的绝对差。一个空子树的权值为0。
我们的实现应该支持以下操作:
•更新节点权值。
•插入新节点。
•移动根节点的子树。
•找到最不平衡的节点，即最inbalance的节点。
因此需要维护一个树，其中树中的每个节点都持有一个权重值作为它的key
“inbalance”的value等同于此节点左右子树的求和权值之差。
Example:
Tree:

Imbalance:

Move subtree

您还必须支持move_subtree(node_a, node_b, left_child)函数，其中以node_a为根的子树被生成为node_b的一个子树。Left_child是一个布尔值，决定node_a是node_b的左子节点还是它的右子节点。如果node_b已经有一个子节点作为node_a的指定位置，那么函数应该什么都不做。
你必须在移动子树之后，确保所有节点的inbalance属性都是正确的。你可以假设node_b不在node_a的子树中，因此你不需要检查这个。
Example:

move_subtree(D,C,false):

Imbalance:

Find Max Imbalance

应该努力使实现尽可能高效。请注意，我们不要使用低效的方法，显式地测试实现的效率实现可能导致Ed超时。
你需要实现以下功能:
node.py
• init
• add_left_child, add_right_child
• update_weight
tree.py
• put
• move_subtree
• find_max_imbalance
(注意，如果需要，可以向类中添加额外的函数和变量，因此请放心修改和扩展这些函数，只要保留现有的函数签名和变量不变。)

Code

node.py

这个文件保存关于树中节点的所有信息。
Properties

Functions

init(weight)

•初始化节点属性。

add_left_child (child_node)

•将子节点添加为该节点的左子节点，如果该节点已经有一个左孩子结点，则不做任何操作。
•运行计算更新inbalance。

add_right_child (child_node)

•将子节点添加为该节点的右子节点，如果该节点已经存在右孩子，则不做任何操作
•运行计算更新不平衡。

is_external ()

•检查节点是否为叶节点。

get_left_child()(或node.left_child)

•返回该节点的左子节点。

get_right_child()(或node.right_child)

•返回该节点的右子节点。

update_weight(weight)

•设置节点的权重。

•运行计算更新不平衡。

get_imbalance()(或node.imbalance)

•返回该节点的不平衡状态。

tree.py

主树文件，保存与树和节点的所有交互。

Properties

root *Node 树的根节点

Functions

put(node, child, left_child)

•将子节点添加为左子节点或右子节点(取决于left_child)

如果节点B也有子节点，则没有。

move_subtree (node_a node_b left_child)

•移动节点A成为节点B的左子节点或右子节点(取决于left_child)，

如果节点B也有子节点，则不执行任何操作。

•运行计算更新不平衡。

find_max_imbalance ()

•返回树的最大不平衡。

测试

我们在此存储库的tests目录中为您提供了一些测试用例。我们

将使用python的unittest包提供的单元测试。

运行测试

从基目录(包含node.py和tree.py的目录)运行

Python -m unittest -v tests/test_sample_tree.py tests/test_sample_node.py
1

或者，通过以下方式运行所有测试:

Python -m unittest -vv
1

测试代码如下：

from Node import Node

import unittest


def assert_equal(got, expected, msg):
    """
    Simple assert helper
    """
    assert expected == got, \
        "[{}] 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)
        """

        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
        """
        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
        """
        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")
'''
    def test_get_imbalance(self):
        """
        Test that the sample tree returns the correct imbalance
        """
        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
        """
        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)
        /   \
        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))
        """
        Tree:
        A(5)
        /   \
        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
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
40
41
42
43
44
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
88
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
119
120
121

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):
        """
        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)

    def test_construction(self):
        """
        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)1
            /   \
            C(2) D(8)
            /  \
          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")

1
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
40
41
42
43
44
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
88

测试成功图
nodetest

treetest

树的建立(只是我的版本，你们可以写不同的)

Node.py

#Node class


class Node:
    weight: int
    imbalance: int
    # These are the defined properties as described above


    #Initialises the properties of the node.
    def __init__(self, weight):
        """
        The constructor for the Node class.
        :param weight: If no input value.
        """
        self.weight = weight
        # the subtree total weight
        self.sum = weight
        self.left_child = None
        self.right_child = None
        self.parent = None
        self.imbalance = 0

    #Adds the child node as the left child of the node, does nothing if the node already has a left child.
    def add_left_child(self,child_node):
        if self.left_child is not None:
            return False
        else:
            self.left_child = child_node
            child_node.parent = self
        #Runs calculations for updating the imbalance.
            self.parent_imbalance()
            return True

    #Adds the child node as the right child of the node, does nothing if the node already has a right child.
    def add_right_child(self,child_node):
        if self.right_child is not None:
            return False
        else:
            self.right_child = child_node
            child_node.parent = self
        # Runs calculations for updating the imbalance.
            self.parent_imbalance()
            return True

    # Checks if the node is a leaf.
    def is_external(self):
        if self.right_child is None and self.left_child is None:
            return True
        else:
            return False

    def get_left_child(self):
        return self.left_child

    def get_right_child(self):
        return self.right_child

    def update_weight(self,weight):
        self.sum +=(weight-self.weight)
        self.weight = weight
        self.parent_imbalance()

    def get_imbalance(self) -> int:
        return self.imbalance

    def parent_imbalance(self):
        p = self
        if p is None:
            return
        while p.parent is not None:
            fun.reimbalance(p)
            p = p.parent
        fun.reimbalance(p)   #root

class fun:
    def reimbalance(rot: Node) -> int:
        if rot.left_child is None and rot.right_child is None:
            rot.imbalance = 0
            rot.sum = rot.weight
            return rot.sum

        if rot.left_child is not None and rot.right_child is None:
            #fun.reimbalance(rot.left_child)
            rot.imbalance = rot.left_child.sum
            rot.sum = rot.weight + rot.left_child.sum
            return rot.sum

        if rot.left_child is None and rot.right_child is not None:
            #fun.reimbalance(rot.right_child)
            rot.imbalance = rot.right_child.sum
            rot.sum = rot.weight + rot.right_child.sum
            return rot.sum

        l_sum = fun.reimbalance(rot.left_child)
        r_sum = fun.reimbalance(rot.right_child)
        rot.sum = l_sum + r_sum + rot.weight
        rot.imbalance = abs(l_sum - r_sum)
        return rot.sum

1
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
40
41
42
43
44
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101

Tree.py

from Node import Node
"""
Tree
----------

This class represents the Binary Tree

Each Tree consists of the following properties:
    - root: The root of the Tree

The class also supports the following functions:
    - put(node, child, left_child): Adds child to the given node as the left or right child depending on the value of left_child
    - move_subtree(node_a, node_b, left_child): Move node_a to the left or right child of node_b depending on the value of left_child
    - find_max_imbalance(): Finds the node with the maximum imbalance in the tree
"""


class Tree():
    # These are the defined properties as described above
    root: Node
    global m
    m = -1

    def __init__(self, root: Node = None) -> None:
        """
        The constructor for the Tree class.
        :param root: The root node of the Tree.
        """
        self.root = root
        self.m = -1

    def put(self, node: Node, child: Node, left_child: bool) -> None:
        """
        You are guranteed that the given node is not already part of the tree
        :param node: The node to add the child to.
        :param child: The child to add to the node.
        :param left_child: True if the child should be added to the left child, False otherwise.
        """

        if left_child is True:
            if node.get_left_child() is None:
                node.add_left_child(child)
                #node.left_child.update_weight(child.weight)
                node.left_child.parent = node

            else:
                return
        else:
            if node.get_right_child() is None:
                node.add_right_child(child)
                #node.right_child.update_weight(child.weight)
                node.right_child.parent = node

            else:
                return
        # TODO Add the child to the node as the left or right child depending on the value of left_child

    def move_subtree(self, node_a: Node, node_b: Node, left_child: bool) -> None:
        """
        Moves the subtree rooted at node_a to the left or right child of node_b depending on the value of left_child.
        If node_b already has a child at the indicated position, this function should do nothing
        You can safely assume that node_b is not descendent of node_a.
        :param node_a: The root of the subtree to move.
        :param node_b: The node to add the subtree to.
        :param left_child: True if the subtree should be added to the left child, False otherwise.
        """
        a = p = node_b
        if not node_b.root:  #if root == null , directly insert
            node_b = node_a
            return
        elif left_child is True:
            if node_b.get_left_child() is None:
                node_b.add_left_child(node_a)
                node_b.left_child.parent = node_b
                a.parent_imbalance()

            else:
                return
        else:
            if node_b.get_right_child() is None:
                node_b.add_right_child(node_a)
                node_b.right_child.parent = node_b
                p.parent_imbalance()

            else:
                return
        # TODO Move the subtree rooted at node_a to the left or right child of node_b

    def find_max_imbalance(self) -> int:
        """
        Finds the node with the maximum imbalance in the tree.
        :return: The node with the maximum imbalance.
        """
        return c.findmax(self.root)
        # TODO Find the node with the maximum imbalance


class c():
    def findmax(rot: Node) -> int:
        global m
        compare = rot.get_imbalance()
        m = compare if m < compare else m
        if rot.left_child is not None:
            left = c.findmax(rot.get_left_child())
            m = left if m < left else m
        if rot.right_child is not None:
            right = c.findmax(rot.get_right_child())
            m = right if m < right else m
        return m
1
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
40
41
42
43
44
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109