萤火

有一份热，发一分光

0%

算法基础 4 - 二叉树 Binary Tree

发表于 更新于 分类于 阅读次数： Valine：

二叉树基本要点

  • 组成：
    • 一个表示该节点的数据项
    • 三个指针，分别指向父节点，以及左、右两个子节点
  • 概念：
    • 根节点（root）：唯一缺少父节点的节点
    • 叶节点（left）：没有子节点的节点
    • 节点祖先（ancestors）：由根节点到达某个节点所经过的一系列节点
    • 节点深度（depth）：由根节点到达某个节点的路径长度
    • 树高度（height）：所有节点的最大深度
  • 遍历顺序（Traversal Order）：
    • 每个节点的左子树节点的访问顺序早于该节点
    • 每个节点的左子树节点的访问顺序晚于该节点
  • 接口实现：
    • 遍历顺序关联序列顺序，用于实现序列（Sequence Interface）
    • 遍历顺序关联排序顺序，用于实现集合（Set Interface）
  • 平衡二叉树 - AVL Tree
    • 倾斜度（skew）：节点右子树高度减去节点左子树的高度
    • 高度平衡（AVL特性）：节点/所有节点的倾斜度属于集合[-1, 0, 1]
    • 旋转：在保持遍历顺序的同时，通过变换节点的父子关系，减小树的高度
    • 高度：h = logn
  • 效率性：
    • 二叉树所有操作的时间复杂度均为O(h)，进一步平衡二叉树为O(logn)

二叉树的操作

  • 基础元素：
1
2
3
4
5
6
class Binary_Node:
    def __init__(A, x):
        A.item = x
        A.left = None
        A.right = None
        A.parent = None
  • 遍历访问（迭代）：
    • 如果该节点含有左节点，遍历访问该节点的左节点
    • 输出该节点数据
    • 如果该节点含有右节点，遍历访问该节点的右节点
1
2
3
4
5
6
def subtree_iter(self):
    if self.left:
        yield from self.left.subtree_iter()
    yield self
    if self.right:
        yield from self.right.subtree_iter()
  • 查找子树最首/最尾的遍历节点（遍历）
1
2
3
4
5
6
7
8
9
10
11
def subtree_first(A):
    if A.left:
        return A.left.subtree_first()
    else:
        return A

def subtree_last(A):
    if A.right:
        return A.right.subtree_last()
    else:
        return A
  • 查找下一个/上一个遍历节点
    • 如果该节点存在右节点，则下一个节点为右子树的首节点
    • 如果该节点不存在右节点，则下一个节点为左分支上的祖先节点
1
2
3
4
5
6
7
8
9
10
11
12
13
def successor(A):
    if A.right:
        return A.right.subtree_first()
    while A.parent and (A is A.parent.right):
        A = A.parent
    return A.parent

def predecessor(A):
    if A.left:
        return A.left.subtree_last()
    while A.parent and (A is A.parent.left):
        A = A.parent
    return A.parent
  • 旋转节点
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
def subtre_rotate_right(D):
    if D.left:
        B, E = D.left, D.right
        A, C = B.left, B.right
        D, B = B, D
        D.item, B.item = B.item, D.item
        B.left, B.right = A, D
        D.left, D.right = C, E
        if A:
            A.parent = B
        if E:
            E.parent = D

def subtree_rotate_left(B):
    if B.right:
        A, D = B.left, B.right
        C, E = D.left, D.right
        B, D = D, B
        B.item, D.item = D.item, B.item
        D.left, D.right = B, E
        B.left, B.right = A, C
        if A:
            A.parent = B
        if E:
            E.parent = D

  • AVL树平衡

    • Case 1: 该节点skew为2，且该节点的右子节点skew为0或1，将该节点左旋

    • Case 2: 该节点skew为2，且该节点的右子节点skew为-1，将该节点的右子节点右旋，再将该节点左旋

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
def height(A):
    if A:
        return A.height
    else:
        return -1

######
def subtree_update(A):
    A.height = 1 + max(height(A.left), height(A.right))

def skew(A):
    return height(A.right) - height(A.left)

def rebalance(A):
    if A.skew == 2:
        if A.right.skew() < 0:
            A.right.subtre_rotate_right()
        A.subtree_rotate_left()
    elif A.skew() == -2:
        if A.left.skew() > 0:
            A.left.subtree_rotate_left()
        A.subtre_rotate_right()

def maintain(A):
        A.rebalance()
      A.subtree_update()
      if A.parent:
          A.parent.maintain()
  • 插入 - 以在节点之前插入为例
    • 若该节点不存在左子节点，插入位置为该节点的左子节点
    • 若该节点存在左子节点，插入位置为左子树最末节点的右子节点
    • 重新平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subtree_insert_before(A, B):
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left, B.parent = B, A
        A.maintain()

    def subtree_insert_after(A, B):
        if A.right:
            A = A.right.subtree_first()
            A.left, B.parent = B, A
        else:
            A.right, B.parent = B, A
        A.maintain()

  • 删除()

    • 若该节点为叶节点，则直接删除

    • 若该节点非叶节点，则将该节点和其前一个/后一个遍历节点交换后删除（一定是叶节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subtree_delete(A):
    if A.left or A.right:
        if A.left:
            B = A.predecessor()
        else:
            B = A.successor()
        A.item, B.item = B.item, A.item
        return B.subtree_delete()
    if A.parent:
        if A is A.parent.left:
            A.parent.left = None
        else:
            A.parent.right = None
        A.maintain()
    return A

AVL平衡的完整实现

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
122
123
124
125
126
def height(A):
    if A:
        return A.height
    else:
        return -1

class Binary_Node:
    def __init__(A, x):
        A.item = x
        A.left = None
        A.right = None
        A.parent = None
        A.subtree_update()

    def subtree_update(A):
        A.height = 1 + max(height(A.left), height(A.right))

    def skew(A):
        return height(A.right) - height(A.left)

    def subtree_iter(A):
        if A.left:
            yield from A.left.subtree_iter()
        yield A
        if A.right:
            yield from A.right.subtree_iter()

    def subtree_first(A):
        if A.left:
            return A.left.subtree_first()
        else:
            return A

    def subtree_last(A):
        if A.right:
            return A.right.subtree_last()
        else:
            return A

    def successor(A):
        if A.right:
            return A.right.subtree_first()
        while A.parent and (A is A.parent.right):
            A = A.parent
        return A.parent

    def predecessor(A):
        if A.left:
            return A.left.subtree_last()
        while A.parent and (A is A.parent.left):
            A = A.parent
        return A.parent

    def subtre_rotate_right(D):
        if D.left:
            B, E = D.left, D.right
            A, C = B.left, B.right
            D, B = B, D
            D.item, B.item = B.item, D.item
            B.left, B.right = A, D
            D.left, D.right = C, E
            if A:
                A.parent = B
            if E:
                E.parent = D

    def subtree_rotate_left(B):
        if B.right:
            A, D = B.left, B.right
            C, E = D.left, D.right
            B, D = D, B
            B.item, D.item = D.item, B.item
            D.left, D.right = B, E
            B.left, B.right = A, C
            if A:
                A.parent = B
            if E:
                E.parent = D

    def rebalance(A):
        if A.skew == 2:
            if A.right.skew() < 0:
                A.right.subtre_rotate_right()
            A.subtree_rotate_left()
        elif A.skew() == -2:
            if A.left.skew() > 0:
                A.left.subtree_rotate_left()
            A.subtre_rotate_right()

    def maintain(A):
        A.rebalance()
        A.subtree_update()
        if A.parent:
            A.parent.maintain()

    def subtree_insert_before(A, B):
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left, B.parent = B, A
        A.maintain()

    def subtree_insert_after(A, B):
        if A.right:
            A = A.right.subtree_first()
            A.left, B.parent = B, A
        else:
            A.right, B.parent = B, A
        A.maintain()

    def subtree_delete(A):
        if A.left or A.right:
            if A.left:
                B = A.predecessor()
            else:
                B = A.successor()
            A.item, B.item = B.item, A.item
            return B.subtree_delete()
        if A.parent:
            if A is A.parent.left:
                A.parent.left = None
            else:
                A.parent.right = None
            A.maintain()
        return A

面向集合接口的二叉树

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
def height(A):
    if A:
        return A.height
    else:
        return -1

class Binary_Node:
    def __init__(A, x):
        A.item = x
        A.left = None
        A.right = None
        A.parent = None
        A.subtree_update()

    def subtree_update(A):
        A.height = 1 + max(height(A.left), height(A.right))

    def skew(A):
        return height(A.right) - height(A.left)

    def subtree_iter(A):
        if A.left:
            yield from A.left.subtree_iter()
        yield A
        if A.right:
            yield from A.right.subtree_iter()

    def subtree_first(A):
        if A.left:
            return A.left.subtree_first()
        else:
            return A

    def subtree_last(A):
        if A.right:
            return A.right.subtree_last()
        else:
            return A

    def successor(A):
        if A.right:
            return A.right.subtree_first()
        while A.parent and (A is A.parent.right):
            A = A.parent
        return A.parent

    def predecessor(A):
        if A.left:
            return A.left.subtree_last()
        while A.parent and (A is A.parent.left):
            A = A.parent
        return A.parent

    def subtree_rotate_right(D):
        if D.left:
            B, E = D.left, D.right
            A, C = B.left, B.right
            D, B = B, D
            D.item, B.item = B.item, D.item
            B.left, B.right = A, D
            D.left, D.right = C, E
            if A:
                A.parent = B
            if E:
                E.parent = D

    def subtree_rotate_left(B):
        if B.right:
            A, D = B.left, B.right
            C, E = D.left, D.right
            B, D = D, B
            B.item, D.item = D.item, B.item
            D.left, D.right = B, E
            B.left, B.right = A, C
            if A:
                A.parent = B
            if E:
                E.parent = D

    def rebalance(A):
        if A.skew == 2:
            if A.right.skew() < 0:
                A.right.subtree_rotate_right()
            A.subtree_rotate_left()
        elif A.skew() == -2:
            if A.left.skew() > 0:
                A.left.subtree_rotate_left()
            A.subtree_rotate_right()

    def maintain(A):
        A.rebalance()
        A.subtree_update()
        if A.parent:
            A.parent.maintain()

    def subtree_insert_before(A, B):
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left, B.parent = B, A
        A.maintain()

    def subtree_insert_after(A, B):
        if A.right:
            A = A.right.subtree_first()
            A.left, B.parent = B, A
        else:
            A.right, B.parent = B, A
        A.maintain()

    def subtree_delete(A):
        if A.left or A.right:
            if A.left:
                B = A.predecessor()
            else:
                B = A.successor()
            A.item, B.item = B.item, A.item
            return B.subtree_delete()
        if A.parent:
            if A is A.parent.left:
                A.parent.left = None
            else:
                A.parent.right = None
            A.maintain()
        return A

class BST_Node(Binary_Node):
    def subtree_find(A, k):
        if k < A.item.key:
            if A.left:
                return A.left.subtree_find(k)
        elif k > A.item.key:
            if A.right:
                return A.right.subtree_find(k)
        else:
            return A
        return None

    def subtree_find_next(A, k):
        if A.item <= k:
            if A.right:
                return A.right.subtree_find_next(k)
            else:
                return None
        elif A.left:
            B = A.left.subtree_find_next(k)
            if B:
                return B
        return A

    def subtree_find_prev(A, k):
        if A.item >= k:
            if A.left:
                return A.left.subtree_find_prev(k)
            else:
                return None
        elif A.right:
            B = A.right.subtree_find_prev(k)
            if B:
                return B
        return A

    def subtree_insert(A, B):
        if B.item < A.item:
            if A.left:
                A.left.subtree_insert(B)
            else:
                A.subtree_insert_before(B)
        elif B.item > A.item:
            if A.right:
                A.right.subtree_insert(B)
            else:
                A.subtree_insert_after(B)
        else:
            A.item = B.item

class Binary_Tree:
    def __init__(T, Node_Type=Binary_Node):
        T.root = None
        T.size = 0
        T.Node_Type = Node_Type

    def __len__(T): return T.size

    def __iter__(T):
        if T.root:
            for A in T.root.subtree_iter():
                yield A.item

class Set_Binary_Set(Binary_Tree):
    def __init__(self):
        super().__init__(BST_Node)

    def iter_order(self): yield from self

    def build(self, X):
        for x in X:
            self.insert(x)

    def find_min(self):
        if self.root:
            return self.root.subtree_first().item

    def find_max(self):
        if self.root:
            return self.root.subtree_last().item

    def find(self, k):
        if self.root:
            node = self.root.subtree_find(k)
            if node:
                return node.item

    def find_next(self, k):
        if self.root:
            node = self.root.subtree_find_next(k)
            if node:
                return node.item

    def find_prev(self, k):
        if self.root:
            node = self.root.subtree_find_prev(k)
            if node:
                return node.item

    def insert(self, x):
        new_node = self.Node_Type(x)
        if self.root:
            self.root.subtree_insert(new_node)
            if new_node.parent is None:
                return False
        else:
            self.root = new_node
        self.size += 1
        return True

    def delete(self, k):
        if self.root:
            node = self.root.subtree_find(k)
            if node:
                ext = node.subtree_delete()
                if ext.parent is None:
                    self.root = None
                self.size -= 1
                return ext.item

面向序列接口的二叉树

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
def height(A):
    if A:
        return A.height
    else:
        return -1

class Binary_Node:
    def __init__(A, x):
        A.item = x
        A.left = None
        A.right = None
        A.parent = None
        A.subtree_update()

    def subtree_update(A):
        A.height = 1 + max(height(A.left), height(A.right))

    def skew(A):
        return height(A.right) - height(A.left)

    def subtree_iter(A):
        if A.left:
            yield from A.left.subtree_iter()
        yield A
        if A.right:
            yield from A.right.subtree_iter()

    def subtree_first(A):
        if A.left:
            return A.left.subtree_first()
        else:
            return A

    def subtree_last(A):
        if A.right:
            return A.right.subtree_last()
        else:
            return A

    def successor(A):
        if A.right:
            return A.right.subtree_first()
        while A.parent and (A is A.parent.right):
            A = A.parent
        return A.parent

    def predecessor(A):
        if A.left:
            return A.left.subtree_last()
        while A.parent and (A is A.parent.left):
            A = A.parent
        return A.parent

    def subtree_rotate_right(D):
        if D.left:
            B, E = D.left, D.right
            A, C = B.left, B.right
            D, B = B, D
            D.item, B.item = B.item, D.item
            B.left, B.right = A, D
            D.left, D.right = C, E
            if A:
                A.parent = B
            if E:
                E.parent = D

    def subtree_rotate_left(B):
        if B.right:
            A, D = B.left, B.right
            C, E = D.left, D.right
            B, D = D, B
            B.item, D.item = D.item, B.item
            D.left, D.right = B, E
            B.left, B.right = A, C
            if A:
                A.parent = B
            if E:
                E.parent = D

    def rebalance(A):
        if A.skew == 2:
            if A.right.skew() < 0:
                A.right.subtree_rotate_right()
            A.subtree_rotate_left()
        elif A.skew() == -2:
            if A.left.skew() > 0:
                A.left.subtree_rotate_left()
            A.subtree_rotate_right()

    def maintain(A):
        A.rebalance()
        A.subtree_update()
        if A.parent:
            A.parent.maintain()

    def subtree_insert_before(A, B):
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left, B.parent = B, A
        A.maintain()

    def subtree_insert_after(A, B):
        if A.right:
            A = A.right.subtree_first()
            A.left, B.parent = B, A
        else:
            A.right, B.parent = B, A
        A.maintain()

    def subtree_delete(A):
        if A.left or A.right:
            if A.left:
                B = A.predecessor()
            else:
                B = A.successor()
            A.item, B.item = B.item, A.item
            return B.subtree_delete()
        if A.parent:
            if A is A.parent.left:
                A.parent.left = None
            else:
                A.parent.right = None
            A.maintain()
        return A

class Binary_Tree:
    def __init__(T, Node_Type=Binary_Node):
        T.root = None
        T.size = 0
        T.Node_Type = Node_Type

    def __len__(T): return T.size

    def __iter__(T):
        if T.root:
            for A in T.root.subtree_iter():
                yield A.item

class Size_Node(Binary_Node):
    def subtree_update(A):
        super().subtree_update()
        A.size = 1
        if A.left:
            A.size += A.left.size
        if A.right:
            A.size += A.right.size

    def subtree_at(A, i):
        if 0 <= i:
            if A.left:
                L_size = A.left.size
            else:
                L_size = 0
            if i < L_size:
                return A.left.subtree_at(i)
            elif i > L_size:
                return A.right.subtree_at(i - L_size - 1)
            else:
                return A

class Seq_Binary_Tree(Binary_Tree):
    def __init__(self):
        super().__init__(Size_Node)

    def build(self, X):
        def build_subtree(X, i, j):
            c = (i + j) // 2
            root = self.Node_Type(X[c])
            if i < c:
                root.left = build_subtree(X, i, c - 1)
                root.left.parent = root
            if c < j:
                root.right = build_subtree(X, c + 1, j)
                root.right.parent = root
            root.subtree_update()
            return root
        self.root = build_subtree(X, 0, len(X) - 1)
        self.size = self.root.size

    def get_at(self, i):
        if self.root:
            return self.root.subtree_at(i).item

    def set_at(self, i, x):
        if self.root:
            self.root.subtree_at(i).item = x

    def insert_at(self, i, x):
        new_node = self.Node_Type(x)
        if i == 0:
            if self.root:
                node = self.root.subtree_first()
                node.subtree_insert_before(new_node)
            else:
                self.root = new_node
        else:
            node = self.root.subtree_at(i - 1)
            node.subtree_insert_after(new_node)
        self.size += 1

    def delete_at(self, i):
        if self.root:
            node = self.root.subtree_at(i)
            ext = node.subtree_delete()
            if ext.parent is None:
                self.root = None
            self.size -= 1
            return ext.item

    def insert_first(self, x): self.insert_at(0, x)
    def delete_first(self, x): return self.delete_at(0)
    def insert_last(self, x): self.insert_at(len(self), x)
    def delete_last(self): return self.delete_at(len(self)-1)