用manim画一颗AVL树

AVL树

AVL 树，是一种平衡的二叉搜索树。由于各种算法教材上对 AVL 的介绍十分冗长，造成了很多人对 AVL 树复杂、不实用的印象。但实际上，AVL 树的原理简单，实现也并不复杂。

性质
  1. 空二叉树是一个 AVL 树
  2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且\(|{ h(ls)-h(rs) } | 1\)，h 是其左右子树的高度
  3. 树高为\(O(\log{n})\)

节选自OIWIKI

AVL树中，在插入或删除节点后，为了保持树的平衡，通常会对节点进行左旋以及右旋操作，根据平衡因子的不同，我们将其分为四种类型：LL, LR, RR, RL。

上面是正经的解释，但是如标题所言，这篇文章其实是manim的一个练手，正好上课讲到平衡树，就用这四种类型的操作做个小动画。如下，源代码见文末。

动画

LL

AVLTreeLL_ManimCE_v0.17.3

LR

AVLTreeLR_ManimCE_v0.17.3

RR

AVLTreeRR_ManimCE_v0.17.3

RL

AVLTreeRL_ManimCE_v0.17.3

源码

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
# run: manim ./project/scene.py AVLTree    
from manim import *


def config_frame(width, height, dpi: int=300, frame_rate: int=30):
    CM_PER_INCH = 2.54
    from math import ceil
    config.frame_rate = frame_rate
    dpc = dpi / CM_PER_INCH
    config.frame_width, config.frame_height = width, height
    config.pixel_width, config.pixel_height = map(ceil, [config.frame_width * dpc, config.frame_height * dpc])
    # The pixel width and height must be divisible by 2.
    if config.pixel_width & 1:
        config.pixel_width += 1
    if config.pixel_height & 1:
        config.pixel_height += 1
        
class AVLTreeLL(Scene):
    config.format = "gif"  # 保存为 gif
    config_frame(width=5, height=5, dpi=500, frame_rate=60) #设置输出画幅
    config.write_all = True
    def construct(self):
        # LL
        self.next_section("LL", skip_animations=False)
        vertices = [2, 1, 0]
        edges = [(2, 1), (1, 0)]
        lt = {2: [0, 0, 0], 1: [-1, -1, 0], 0: [-2, -2, 0]}
        G = Graph(vertices, edges, layout=lt, labels=True)
        self.play(Create(G))
        self.play(G.animate.center())
        self.wait(1)
        self.play(
            G[2].animate.move_to([1, -1, 0]),
            G[1].animate.move_to([0, 0, 0]),
            G[0].animate.move_to([-1, -1, 0])
        )
        self.wait(1)
        self.play(FadeOut(G))
class AVLTreeLR(Scene):
    def construct(self):
        # LR
        self.next_section("LR", skip_animations=False)
        vertices = [2, 0, 1]
        edges = [(2, 0), (0, 1)]
        lt = {2: [0, 0, 0], 0: [-1, -1, 0], 1: [0, -2, 0]}
        G = Graph(vertices, edges, layout=lt, labels=True)
        self.play(Create(G))

        self.wait(1)
        self.play(
            G.animate.remove_edges((2, 0)),
            G.animate.add_edges((2, 1)))
        self.play(
            G[0].animate.move_to([-2, -2, 0]),
            G[1].animate.move_to([-1, -1, 0])
        )
        self.play(G.animate.center())
        self.play(
            G[2].animate.move_to([1, -1, 0]),
            G[0].animate.move_to([-1, -1, 0]),
            G[1].animate.move_to([0, 0, 0])
        )
        self.wait(1)
        self.play(FadeOut(G))
class AVLTreeRR(Scene):
    def construct(self):
        # RR
        self.next_section("RR", skip_animations=False)
        vertices = [0, 1, 2]
        edges = [(0, 1), (1, 2)]
        lt = {0: [0, 0, 0], 1: [1, -1, 0], 2: [2, -2, 0]}
        G = Graph(vertices, edges, layout=lt, labels=True)
        self.play(Create(G))
        self.play(G.animate.center())
        self.wait(1)
        self.play(
            G[0].animate.move_to([-1, -1, 0]),
            G[1].animate.move_to([0, 0, 0]),
            G[2].animate.move_to([1, -1, 0])
        )
        self.wait(1)
        self.play(FadeOut(G))
class AVLTreeRL(Scene):
    def construct(self):
        # RL
        self.next_section("RL", skip_animations=False)
        vertices = [0, 2, 1]
        edges = [(0, 2), (2, 1)]
        lt = {0: [0, 0, 0], 2: [1, -1, 0], 1: [0, -2, 0]}
        G = Graph(vertices, edges, layout=lt, labels=True)
        self.play(Create(G))
        self.wait(1)
        self.play(
            G.animate.remove_edges((0, 2)),
            G.animate.add_edges((0, 1)))

        self.play(
            G[2].animate.move_to([2, -2, 0]),
            G[1].animate.move_to([1, -1, 0])
        )
        self.play(G.animate.center())
        self.play(
            G[0].animate.move_to([-1, -1, 0]),
            G[2].animate.move_to([1, -1, 0]),
            G[1].animate.move_to([0, 0, 0])
        )
        self.wait(1)
        self.play(FadeOut(G))
#Manim #平衡树 #数据结构 #Python
用manim画一颗AVL树
https://sayaz.site/2023/10/21/用manim画一颗AVL树/
作者
saya
发布于
2023年10月21日
许可协议