| 99 | self.datas = np.arange(6) |
| 100 | |
| 101 | class SegmentTreeBuild(SegmentTreeBase): |
| 102 | def __init__(self, **kwargs): |
| 103 | super().__init__(**kwargs) |
| 104 | |
| 105 | def travel(self, n:AlgoSegTreeNode): |
| 106 | if n.l == n.r: |
| 107 | # leaf |
| 108 | node = self.tree.get_node(n.id) |
| 109 | node.set_color(BLUE) |
| 110 | self.tree.show_node(n.id) |
| 111 | return |
| 112 | self.travel(n.left) |
| 113 | self.travel(n.right) |
| 114 | # parent |
| 115 | self.tree.show_node(n.id) |
| 116 | self.tree.show_edge(n.id, n.left.id) |
| 117 | self.tree.show_edge(n.id, n.right.id) |
| 118 | |
| 119 | def build_segment_tree(self): |
| 120 | array = AlgoVector(self, self.datas) |
| 121 | array.set_color(BLUE) |
| 122 | self.play(ShowCreation(array)) |
| 123 | self.play(array.to_edge, UP) |
| 124 | self.array = array |
| 125 | |
| 126 | self.show_message("后序创建二叉树", delay=0) |
| 127 | self.tree = AlgoSegTree(self, self.datas) |
| 128 | self.tree.scale(0.9) |
| 129 | self.tree.shift(UP*0.5) |
| 130 | self.add(self.tree) |
| 131 | self.tree.hide_all() |
| 132 | self.travel(self.tree.root) |
| 133 | |
| 134 | self.play(Uncreate(self.tree), Uncreate(array)) |
| 135 | self.show_message("再来看看如何更新线段树") |
| 136 | |
| 137 | def find_element(self, node, val, new_val): |
| 138 | if node.l==node.r and node.v == val: |
| 139 | n = self.tree.get_node(node.id) |
| 140 | self.play(n.set_color, RED) |
| 141 | self.show_message("修改元素") |
| 142 | n.set_text(str(new_val)) |
| 143 | n.v = new_val |
| 144 | return |
| 145 | self.find_element(node.l, val, new_val) |
| 146 | self.find_element(node.r, val, new_val) |
| 147 | node.v = node.l.v + node.r.v |
| 148 | n = self.tree.get_node(node.id) |
| 149 | n.set_text(str(node.v)) |
| 150 | self.show_message("更新节点") |
| 151 | self.play(FocusOn(n)) |
| 152 | |
| 153 | def construct(self): |
| 154 | self.start_logo(animate=False) |
| 155 | self.init_message("构造线段树") |
| 156 | self.build_segment_tree() |
| 157 | |
| 158 | class SegmentTreeUpdate(SegmentTreeBase): |
nothing calls this directly
no outgoing calls
no test coverage detected