(self)
| 91 | self.play(*animations, run_time=1.5) |
| 92 | |
| 93 | def construct(self): |
| 94 | self.start_logo(subtitle="红黑树", tex=True, tex_map={"红":RED_D}) |
| 95 | self.init_message("红黑树的性质", tex=True, tex_map={"红":RED_D}) |
| 96 | tree = AlgoRBTree(self) |
| 97 | tree.ctx.insert_message = False |
| 98 | tree.ctx.delete_message = False |
| 99 | tree.ctx.animate = False |
| 100 | |
| 101 | self.add(tree) |
| 102 | max_value = 100 |
| 103 | n = 8 |
| 104 | random.seed(3) |
| 105 | arr = np.random.choice(max_value, size=n, replace=False) |
| 106 | tree.shift(UP*2) |
| 107 | for i in arr: |
| 108 | tree.set(i, i) |
| 109 | tree.ctx.animate = True |
| 110 | tree.update_nodes() |
| 111 | |
| 112 | self.show_message("红黑树是一种二叉查找树", tex=True, tex_map={"红":RED_D}) |
| 113 | root = tree.get_node(tree.root.id) |
| 114 | left = tree.get_node(tree.root.left.id) |
| 115 | right = tree.get_node(tree.root.right.id) |
| 116 | |
| 117 | self.show_message("左孩子的值小于根节点", tex=True, tex_map={"左孩子":BLUE_D, "根节点":BLUE_D}) |
| 118 | self.compare_nodes(left, root, "<") |
| 119 | |
| 120 | self.show_message("右孩子的值大于根节点", tex=True, tex_map={"右孩子":BLUE_D, "根节点":BLUE_D}) |
| 121 | self.compare_nodes(right, root, ">") |
| 122 | |
| 123 | self.show_message("任意节点左右子树分别为二叉查找树", tex=True, tex_map={"二叉查找树":BLUE_D}) |
| 124 | self.hide_and_show(tree, root) |
| 125 | |
| 126 | self.show_message("红黑树有5条性质", tex=True, tex_map={"红":RED_D, "5": BLUE_D}) |
| 127 | |
| 128 | text_list = [ |
| 129 | "1 每个节点是红色或者黑色", |
| 130 | "2 根节点是黑色", |
| 131 | "3 叶子nil节点是黑色", |
| 132 | "4 如果一个节点是红色，则其子节点都是黑色", |
| 133 | "5 对于每一个节点，从该节点到叶子节点的所有路径上，黑色节点数量相同", |
| 134 | ] |
| 135 | |
| 136 | self.play(ApplyMethod(self.camera.frame.shift, RIGHT*3.0)) |
| 137 | panel = AlgoPropertyPanel(self, text_list).scale(0.7) |
| 138 | panel.next_to(tree).shift(UP+LEFT*1.5) |
| 139 | self.play(ShowCreation(panel)) |
| 140 | |
| 141 | self.show_message("1 每个节点是红色或者黑色，包括叶子nil节点", tex=True, tex_map={"红色":RED_D, "黑色": GREY_E, "nil": BLUE_D}) |
| 142 | panel.light(0, color="#93582e") |
| 143 | |
| 144 | self.show_message("2 根节点是黑色", tex=True, tex_map={"黑色":GREY_E, "根节点":BLUE_D}) |
| 145 | root_node = tree.get_node(tree.root.id) |
| 146 | self.play(ApplyWave(root_node), CircleIndicate(root_node, color=RED, run_time=2)) |
| 147 | panel.light(1, color="#93582e") |
| 148 | |
| 149 | self.show_message("3 叶子nil节点是黑色", tex=True, tex_map={"黑色":GREY_E, "nil":BLUE_D}) |
| 150 | self.indicate_nils(tree) |
nothing calls this directly
no test coverage detected