【数据结构与算法系列】中级篇：赏析《树结构及其算法》与《常用高层数据结构》（Python版）_中阶数据结构

作者：笔触狂放9 | 2024-05-15 19:59:24

踩

中阶数据结构

《树形结构及其算法》

1.二叉树

深度优先搜索（DFS）：前、中、后序遍历

广度优先搜索（BFS）：层次遍历

迭代与递归写法

from collections import deque



class TreeNode:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right


#迭代：o(n),o(n) n:节点个数
def preOrder(root:TreeNode):
    if root is None:
        return []

    res,stack=[],[]
    stack.append(root)
    while len(stack):
        curr=stack.pop()
        res.append(curr.data)

        if curr.right:
            stack.append(curr.right)
        if curr.left:
            stack.append(curr.left)
    return res

#递归：o(n),o(n)(最好o（nlogn）)
def preOrderR(root:TreeNode):
    res=[]

    def preOrder(node):
        if node is None:
            return
        res.append(node.data)
        preOrder(node.left)
        preOrder(node.right)
    preOrder(root)
    return res





#迭代：o(n),o(n) n:节点个数
def inOrder(root:TreeNode):
    if root is None:
        return []

    res,stack=[],[]
    curr=root
    while curr or len(stack):
        while curr:
            stack.append(curr)
            curr=curr.left
        node=stack.pop()
        res.append(node.data)
        curr=node.right
    return res

#递归：o(n),o(n)(最好o（nlogn）)
def inOrderR(root:TreeNode):

    res = []

    def inOrder(node):
        if node is None:
            return

        inOrder(node.left)
        res.append(node.data)
        inOrder(node.right)

    inOrder(root)
    return res






#迭代：o(n),o(n) n:节点个数
def postOrder(root:TreeNode):
    if root is None:
        return []

    res,stack=[],[]
    #根->右->左
    stack.append(root)
    while len(stack):
        curr=stack.pop()
        res.append(curr.data)

        if curr.left:
            stack.append(curr.left)
        if curr.right:
            stack.append(curr.right)
    #左->右->根
    res.reverse()
    return res

#递归：o(n),o(n)(最好o（nlogn）)
def postOrderR(root:TreeNode):

    res=[]
    def postOrder(node):
        if node is None:
            return []
        postOrder(node.left)
        postOrder(node.right)
        res.append(node.data)

    postOrder(root)
    return res




#方法1(一维数组)：o(n)，o(n)
def levelOrder_1(root:TreeNode):
    if root is None:
        return []
    #队列queue
    res,queue=[],deque()
    queue.append(root)
    while len(queue):
        #key:每轮循环遍历处理一个节点
        curr=queue.popleft()
        res.append(curr.data)
        #将遍历节点的左右子节点入队
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)

    return res

#方法2（二维数组）：o(n)，o(n)
def levelOrder_2(root: TreeNode):
    if root is None:
        return []
    # 队列queue
    res,queue=[],deque()
    queue.append(root)
    while len(queue):
        size,level_nodes=len(queue),[]
        #key:每轮循环遍历处理一层节点
        for i in range(size):
            curr=queue.popleft()
            level_nodes.append(curr.data)
            # 将遍历节点的左右子节点入队
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        res.append(level_nodes)
    return res


if __name__=='__main__':
    root=TreeNode(23)
    node1=TreeNode(34)
    node2=TreeNode(21)
    node3=TreeNode(99)
    node4=TreeNode(77)
    node5=TreeNode(90)
    node6=TreeNode(45)
    node7=TreeNode(60)

    root.left=node1
    root.right=node2
    node1.left=node3
    node3.left=node4
    node3.right=node5
    node2.left = node6
    node2.right = node7

    print(preOrder(root))
    print(preOrderR(root))
    print(inOrder(root))
    print(inOrderR(root))
    print(postOrder(root))
    print(postOrderR(root))
    print(levelOrder_1(root))
    print(levelOrder_2(root))
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

2.普通二叉查找树

迭代写法

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BST:
    def __init__(self, __comp):
        self.root = None
        self.size = 0
        self.__comp = __comp

    def getSize(self):
        return self.size

    def isEmpty(self):
        return self.size == 0

 # 插入：o(logn)
    def add(self, e):
        if self.root is None:
            self.root = TreeNode(e)
        else:
            curr = self.root
            while curr:
                # 比较
                if self.__comp(e, curr.data) == 0:
                    return
                elif self.__comp(e, curr.data) < 0 and not curr.left:
                    curr.left = TreeNode(e)
                    self.size += 1
                    return
                elif self.__comp(e, curr.data) > 0 and not curr.right:
                    curr.right = TreeNode(e)
                    self.size += 1
                    return
                if self.__comp(e, curr.data) < 0:
                    curr = curr.left
                else:
                    curr = curr.right

# 修改o(logn)：set(src,target)会破坏二叉搜索树的顺序

#查询
    def contains(self, target):
        node = self.find(target)
        if not node:
            return False
        return True

    #O(logn)
    def find(self, target):
        if not self.root:
            return None
        curr = self.root
        while curr:
            if self.__comp(target, curr.data) == 0:
                return curr
            elif self.__comp(target, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right
        return None

    # 中序遍历：方便观察结果，找bug
    def inOrder(self):
        res = []

        def inOrderR(node):
            if not node:
                return []
            inOrderR(node.left)
            res.append(node.data)
            inOrderR(node.right)

        inOrderR(self.root)
        return res

    #O(logn)
    def minValue(self):
        if not self.root:
            raise Exception("tree is null")
        min_node = self.root
        while min_node.left:
            #最深最左
            min_node = min_node.left
        return min_node.data

    #O(logn)
    def maxValue(self):
        if not self.root:
            raise Exception("tree is null")
        max_node = self.root
        while max_node.right:
            #最深最右
            max_node = max_node.right
        return max_node.data

#删除
    #O(logn)
    def removeMin(self):
        if not self.root:
            raise Exception("tree is null")
        # 找
        min_node, parent = self.root, None
        while min_node.left:
            parent = min_node
            min_node = min_node.left
        #删
        if not parent:
            #位于根节点处
            self.root = self.root.right
        else:
            #key
            parent.left = min_node.right

        min_node.right = None
        self.size -= 1
        return min_node.data

    # 时间复杂度：O(logn)
    def removeMax(self):
        if not self.root:
            raise Exception("tree is null")
        # 找
        max_node, parent = self.root, None
        while max_node.right:
            parent = max_node
            max_node = max_node.right
        #删
        if not parent:
            #位于根节点处
            self.root = self.root.left
        else:
            parent.right = max_node.left

        max_node.left = None
        self.size -= 1
        return max_node.data

    #优化: O(logn)
    def remove_2(self, e):
        if not self.root:
            return
        #找
        curr, parent = self.root, None
        while curr and self.__comp(e, curr.data) != 0:
            parent = curr
            if self.__comp(e, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right
        # 如果没有找到需要删除的元素，则直接返回
        if not curr:
            return

        #情况简化
        if curr.left and curr.right:
            #找右子树最小值
            min_node, min_parent = curr.right, curr
            while min_node.left:
                min_parent = min_node
                min_node = min_node.left
            #覆盖该删除节点值
            curr.data = min_node.data
            #curr变为叶子节点：情况则简化成三种
            curr, parent = min_node, min_parent

        #确定开删节点是仅有一个子树节点还是叶子节点
        if curr.left:
            child = curr.left
            #if parent:
                #curr.left = None
        elif curr.right:
            child = curr.right
            #if parent:
                #curr.right = None
        else:
            child = None

        #开删
        if not parent:
            self.root = child
        elif curr == parent.left:
            parent.left = child
        elif curr == parent.right:
            parent.right = child

        self.size -= 1

    #o(logn)
    def remove_1(self, e):
        if not self.root:
            return

        curr, parent = self.root, None
        # 找
        while curr and self.__comp(e, curr.data) != 0:
            parent = curr
            if self.__comp(e, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right

        # 如果没有找到需要删除的元素，则直接返回
        if not curr:
            return

        # 删
        if not curr.left and not curr.right:
            if not parent:
                self.root = None
            elif curr == parent.left:
                parent.left = None
            elif curr == parent.right:
                parent.right = None
        elif curr.left and not curr.right:
            if not parent:
                self.root = curr.left
            elif curr == parent.left:
                parent.left = curr.left
                curr.left = None
            elif curr == parent.right:
                parent.right = curr.left
                curr.left = None
        elif not curr.left and curr.right:
            if not parent:
                self.root = curr.right
            elif curr == parent.left:
                parent.left = curr.right
                curr.right = None
            elif curr == parent.right:
                parent.right = curr.right
                curr.right = None
        elif curr.left and curr.right:
            #找右子树最小值
            min_node, min_parent = curr.right, curr
            while min_node.left:
                min_parent = min_node
                min_node = min_node.left

            ##覆盖该删除节点值
            curr.data = min_node.data

            #覆盖该删除节点值
            # 先拿到要删除 min 节点的右子树
            right = min_node.right
            # bug 修复：这里删除 min 节点，需要区分 min 是父亲节点的右子节点还是左子节点
            # 要删除 min 节点是父亲节点的右子节点
            if min_parent.right == min_node:
                """
                比如我们要删除以下树的节点70
                        33
                     /      \
                   22        66
                           /    \
                         35      70
                                   \
                                    99
                那么这个时候：minParent = 66，min = 70，即 min 是父亲节点的右子节点
                """
                # 将 min 的右子树挂到父亲节点的右子树中
                min_parent.right = right
            else:
                # 要删除 min 节点是父亲节点的左子节点
                """
                比如我们要删除以下树的节点68
                        33
                     /      \
                   22        66
                           /    \
                         35      70
                               /   \
                             68     99
                               \
                                69
                那么这个时候：minParent = 70，min = 68，即 min 是父亲节点的左子节点
                """
                # 将 min 的右子树挂到父亲节点的左子树中
                min_parent.left = right
            # 删掉 min 的右子树，这样可以使得 min 节点从树中断开
            min_node.right = None

        self.size -= 1


if __name__ == '__main__':
    # bst = BST(lambda a, b: a - b)
    bst = BST(lambda a, b: a - b)
    bst.add(33)
    bst.add(22)
    bst.add(66)
    bst.add(12)
    bst.add(35)
    bst.add(70)
    bst.add(34)
    bst.add(50)
    bst.add(68)
    bst.add(99)

    print(bst.inOrder())
    print(bst.contains(34))

    print(bst.minValue())
    print(bst.maxValue())

    print(bst.removeMin())
    print(bst.inOrder())

    print(bst.removeMax())
    print(bst.inOrder())

    bst.remove_1(66)
    bst.remove_2(67)
    print(bst.inOrder())
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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316

递归写法

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BSTR:
    def __init__(self,__comp):
        self.root=None
        self.size=0
        self.__comp=__comp

    def getsize(self):
        return self.size
    def isEmpty(self):
        return self.size==0



#插入：o(logn)
    def add(self,e):
        self.root=self.addR(self.root,e)
    #将e插入到以node为根节点的子树中
    #返回插入节点后二叉查找树的根节点
    def addR(self,node,e):
        #终止条件
        if not node:
            self.size+=1
            return TreeNode(e)
        #
        if self.__comp(e,node.data)<0:
            node.left=self.addR(node.left,e)
        elif self.__comp(e,node.data)>0:
            node.right=self.addR(node.right,e)
        # e的父亲节点
        return node


#修改：o(logn)：set(src,target)会破坏二叉搜索树的顺序



#查询
    def contains(self,target):
        node=self.find(target)
        if not node:
            return False
        return True
    #o(logn)
    def find(self,target):
        return self.findR(self.root,target)
    def findR(self,node,target):
        #
        if not node:
            return
        #
        if self.__comp(target,node.data)==0:
            return node
        elif self.__comp(target,node.data)<0:
            return self.findR(node.left,target)
        elif self.__comp(target,node.data)>0:
            return self.findR(node.right,target)


    def inOrder(self):
        res=[]

        def inOrderR(node):
            if not node:
                return []
            inOrderR(node.left)
            res.append(node.data)
            inOrderR(node.right)
        inOrderR(self.root)
        return res

    #o(logn)
    def minValue(self):
        if not self.root:
            raise Exception('tree is null')
        return self.minValueR(self.root).data
    def minValueR(self,node):
        #
        if not node.left:
            return node
        #
        return self.minValueR(node.left)

    #o(logn)
    def maxValue(self):
        if not self.root:
            raise Exception('tree is null')
        return self.maxValueR(self.root).data
    def maxValueR(self, node):
        #
        if not node.right:
            return node
        #
        return self.maxValueR(node.right)


#删除
    #O(logn)
    def removeMin(self):
        if not self.root:
            raise Exception('tree is null')

        res=self.minValue()
        self.root=self.removeMinR(self.root)
        return res
    #删除以node为根节点的子树的最小节点
    #返回删除完最小节点的子树的根节点
    def removeMinR(self,node):
        #
        if not node.left:
            right_node=node.right
            node.right=None
            self.size-=1
            return right_node
        #
        node.left=self.removeMinR(node.left)
        return node


    def removeMax(self):
        if not self.root:
            raise Exception('tree is null')

        res=self.maxValue()
        self.root=self.removeMaxR(self.root)
        return res
    #删除以node为根节点的子树的最大节点
    #返回删除完最大节点的子树的根节点
    def removeMaxR(self,node):
        #
        if not node.right:
            left_node=node.left
            node.left=None
            self.size-=1
            return left_node
        #
        node.right=self.removeMaxR(node.right)
        return node




    def remove(self,e):
        self.root=self.removeR(self.root,e)
    def removeR(self,node,e):
        if not node:
            return None
        #找
        if self.__comp(e,node.data)<0:
            node.left=self.removeR(node.left,e)
            return node
        elif self.__comp(e,node.data)>0:
            node.right=self.removeR(node.right,e)
            return node
        #删
        else:
            #情况1
            if not node.left:
                right_node = node.right
                node.right = None
                self.size -= 1
                return right_node
            #情况2
            if not node.right:
                left_node = node.left
                node.left = None
                self.size -= 1
                return left_node
            #情况3(node的left和right都不为空)：用‘后继节点’替代
            successor=self.minValueR(node.right)
            #key:right->left
            successor.right=self.removeMinR(node.right)
            successor.left=node.left

            node.left=None
            node.right=None
            return successor

if __name__ == '__main__':
    # bst = BST(lambda a, b: a - b)
    bst = BSTR(lambda a, b: a - b)
    bst.add(33)
    bst.add(22)
    bst.add(66)
    bst.add(12)
    bst.add(35)
    bst.add(70)
    bst.add(34)
    bst.add(50)
    bst.add(68)
    bst.add(99)

    print(bst.inOrder())
    print(bst.contains(34))

    print(bst.minValue())
    print(bst.maxValue())

    print(bst.removeMin())
    print(bst.inOrder())

    print(bst.removeMax())
    print(bst.inOrder())

    bst.remove(66)
    print(bst.inOrder())
    bst.remove(68)
    print(bst.inOrder())
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

3.AVL树


class TreeNode:
    def __init__(self,data,left=None,right=None,height=1):
        self.data=data
        self.left=left
        self.right=right
        self.height=height

class AVLTree:
    def __init__(self,__comp):
        self.root=None
        self.size=0
        self.__comp=__comp

    def getSize(self):
        return self.size
    def isEmpty(self):
        return self.size==0


    def getHeight(self,node):
        if not node:
            return 0
        return node.height
    #平衡因子：左右子节点高度差
    def getBalanceFactor(self,node):
        if not node:
            return 0
        return self.getHeight(node.left)-self.getHeight(node.right)


#二叉树判断:增序排列
    def isBST(self):
        res=self.inOrder()
        #
        if len(res)<=1:
            return True
        #
        for i in range(1,len(res)):
            if self.__comp(res[i],res[i-1])<0:
                return False
        return True
#平衡树判断：
    def isBalanced(self):
        return self.isBalancedR(self.root)
    def isBalancedR(self,node):
        #终止条件
        if not node:
            return True
        #递归下去
        balance_factor=self.getBalanceFactor(node)
        if abs(balance_factor)>1:
            return False
        return self.isBalancedR(node.left) and self.isBalancedR(node.right)


#转变平衡的操作：右旋与左旋
    """
     对节点 y 进行向右旋转操作，返回旋转后新的根节点 x
            y                                    x
           / \                                 /   \
          x   T4        向右旋转 (y)          z       y
         / \          --------------->      / \     / \
        z   T3                            T1   T2 T3   T4
       / \
     T1   T2
    """
    def rightRotate(self,y):
        #中介点
        x=y.left
        t3=x.right
        #旋
        x.right=y
        y.left=t3
        #更新节点高度：先y后x-因为y为子节点
        y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
        x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
        #返回调整后的根节点
        return x


    """
     对节点y进行向左旋转操作，返回旋转后新的根节点x
        y                             x
      /  \                          /   \
     T4   x      向左旋转 (y)       y     z
         / \   - - - - - - - ->   / \   / \
       T3  z                     T4 T3 T1 T2
          / \
         T1 T2
    """
    def leftRotate(self,y):
        #中介点
        x=y.right
        t3=x.left
        #旋
        x.left=y
        y.right=t3
        #更新节点高度：先y后x-因为y为子节点
        y.height=max(self.getHeight(y.left),self.getHeight(y.right))+1
        x.height=max(self.getHeight(x.left),self.getHeight(x.right))+1
        #返回调整后的根节点
        return x


#插入:o(logn)
    def add(self,e):
        self.root=self.addR(self.root,e)
    #将节点e插入到以node为根节点的子树中
    #返回此根节点
    def addR(self,node,e):
        #终止条件
        if not node:
            self.size-=1
            return TreeNode(e)
        ####################递归###############################

        if self.__comp(e,node.data)<0:
            node.left=self.addR(node.left,e)
        if self.__comp(e,node.data)>0:
            node.right=self.addR(node.right,e)

        #更新高度
        node.height=max(self.getHeight(node.left),self.getHeight(node.right))+1
        #利用平衡因子判断是否平衡，并根据具体情况（四种），利用旋转规整
        balance_factor=self.getBalanceFactor(node)
        #情况1：LL-左子节点增左子节点e
        if balance_factor>1 and self.getBalanceFactor(node.left)>=0:
            return self.rightRotate(node)
        #情况2：RR-右子节点增右子节点e
        if balance_factor<-1 and self.getBalanceFactor(node.right)<=0:
            return self.leftRotate(node)
        #情况3：LR-左子节点增右子节点e
        if balance_factor>1 and self.getBalanceFactor(node.left)<0:
            #先转LL
            node.left=self.leftRotate(node.left)
            return self.rightRotate(node)
        #情况4：RL-右子节点增左子节点e
        if balance_factor<-1 and self.getBalanceFactor(node.right)>0:
            #先转RR
            node.right=self.rightRotate(node.right)
            return self.leftRotate(node)
        return node




#删除：o(logn)
    def minValueR(self, node):
        if not node.left:
            return node
        return self.minValueR(node.left)
    # 删除以  node 为根节点的子树的最小节点
    # 并返回删除完最小节点的子树的根节点
    def removeMinR(self, node):
        if not node.left:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node
        left_node = self.removeMinR(node.left)
        node.left = left_node
        return node

    def remove(self,e):
        self.root=self.removeR(self.root,e)
    def removeR(self,node,e):
        #终
        if not node:
            return None
        #####################递归###############################
        #找
        if self.__comp(e,node.data)<0:
            node.left=self.removeR(node.left,e)
            #方便后续更新节点高度与整平衡
            retNode=node
        elif self.__comp(e,node.data)>0:
            node.right=self.removeR(node.right,e)
            retNode=node
        #删
        else:
            if not node.left:
                right_node=node.right
                node.right=None
                self.size-=1
                retNode=right_node
            elif not node.right:
                left_node=node.left
                node.left=None
                self.size-=1
                retNode=left_node
            else:
                #node的左右子节点都不为空
                #利用后继节点
                successor=self.minValueR(node.right)
                successor.right=self.removeMinR(node.right)
                successor.left=node.left

                node.left=None
                node.right=None
                retNode=successor

            #
            if not retNode:
                return None

        # 更新高度
        retNode.height = max(self.getHeight(retNode.left), self.getHeight(retNode.right)) + 1
        # 利用平衡因子判断是否平衡，并根据具体情况（四种），利用旋转规整
        balance_factor = self.getBalanceFactor(retNode)
        # 情况1：LL-左子节点增左子节点e
        if balance_factor > 1 and self.getBalanceFactor(retNode.left) >= 0:
            return self.rightRotate(retNode)
        # 情况2：RR-右子节点增右子节点e
        if balance_factor < -1 and self.getBalanceFactor(retNode.right) <= 0:
            return self.leftRotate(retNode)
        # 情况3：LR-左子节点增右子节点e
        if balance_factor > 1 and self.getBalanceFactor(retNode.left) < 0:
            # 先转LL
            retNode.left = self.leftRotate(retNode.left)
            return self.rightRotate(retNode)
        # 情况4：RL-右子节点增左子节点e
        if balance_factor < -1 and self.getBalanceFactor(retNode.right) > 0:
            # 先转RR
            retNode.right = self.rightRotate(retNode.right)
            return self.leftRotate(retNode)

        return retNode

    # 中序遍历
    def inOrder(self):
        res = []

        def inOrderR(node):
            if not node:
                return []
            inOrderR(node.left)
            res.append(node.data)
            inOrderR(node.right)

        inOrderR(self.root)
        return res
    
 
if __name__ == '__main__':
    avl = AVLTree(lambda x, y: x - y)

    avl.add(9)
    avl.add(10)
    avl.add(11)
    avl.add(13)

    print(avl.isBST())
    print(avl.isBalanced())

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
247
248
249
250
251
252
253
254
255

4.对比2-3树与红黑树


BLACK=False
RED=True

class TreeNode:
    def __init__(self,data,left=None,right=None,color=RED):
        self.data=data
        self.left=left
        self.right=right
        #颜色
        self.color=color

class RBST:
    def __init__(self,__comp):
        self.root=None
        self.size=0
        self.__comp=__comp

    def getSize(self):
        return self.size
    def isEmpty(self):
        return self.size==0

    #判断节点颜色
    def isRED(self,node):
        #空节点为黑
        if not node:
            return BLACK
        return node.color

    """
        node                    x
        /  \       左旋转      /   \
       T1   x     ------->  node  T3
           / \              /  \
          T2 T3            T1  T2
    """
    def leftRotate(self,node):
        #中介点
        x=node.right
        t2=x.left
        #左旋
        node.right=t2
        x.left=node
        #转色
        x.color=node.color
        node.color=RED

        return x
    """
        node                    x
        /  \       右旋转      /   \
       x   T2     ------->   y   node
      / \                        /  \
     y  T1                      T1  T2
    """
    def rightRotate(self,node):
        #中介点
        x=node.left
        t1=x.right
        #右旋
        node.left=t1
        x.right=node

        x.color=node.color
        node.color=RED
        return x



    #颜色翻转
    def flipColors(self,node):
        node.color=RED
        node.left.color=BLACK
        node.right.color=BLACK

#插入：o(logn)
    def add(self,e):
        self.root=self.addR(self.root,e)
        #保持根节点为黑
        self.root.color=BLACK
    def addR(self,node,e):
        #终止条件
        if not node:
            self.size+=1
            return TreeNode(e)
        #递归
        if self.__comp(e,node.data)<0:
            node.left=self.addR(node.left,e)
        elif self.__comp(e,node.data)>0:
            node.right=self.addR(node.right,e)
        else:
            return node

        #维护以node为根节点的子树黑平衡
        if self.isRED(node.right) and not self.isRED(node.left):
            node=self.leftRotate(node)
        if self.isRED(node.left) and not self.isRED(node.left.left):
            node=self.rightRotate(node)
        if self.isRED(node.left) and self.isRED(node.right):
            node=self.flipColors(node)

        return node


    # 中序遍历
    def inOrder(self):
        res = []

        def inOrderR(node):
            if not node:
                return []
            inOrderR(node.left)
            res.append(node.data)
            inOrderR(node.right)

        inOrderR(self.root)
        return res

if __name__ == '__main__':
    avl = RBST(lambda x, y: x - y)

    avl.add(9)
    avl.add(10)
    avl.add(11)
    avl.add(13)

    print(avl.inOrder())
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

《常用高层数据结构》

1.二叉堆

1.1基于单链表实现DataStream

#方法一：
class Node:
    def __init__(self,val,next=None):
        self.val=val
        self.next=next

class DataStream:
    def __init__(self):
        self.dummy_node=Node(-1)

    #o(1)
    def add(self,val):
        new_node=Node(val)
        new_node.next=self.dummy_node.next
        self.dummy_node.next=new_node

    def removeMax(self):
        if not self.dummy_node.next:
            raise Exception('removeMax失败，因为数据流中无元素')
        #遍历链表，找最大值所在节点
        curr=self.dummy_node.next
        max_value_node=curr
        while curr:
            if curr.val>max_value_node.val:
                max_value_node=curr
            curr=curr.next
        #找最大值节点的前一个节点
        curr,max_value_node_prev=self.dummy_node.next,self.dummy_node
        while curr:
            if curr==max_value_node:
                break
            max_value_node_prev=curr
            curr=curr.next
        #删除
        max_value_node_prev.next=max_value_node.next
        max_value_node.next=None

        return max_value_node.val

if __name__=='__main__':
    ds=DataStream()
    ds.add(3)
    print(ds.removeMax())#3
    ds.add(6)
    ds.add(5)
    print(ds.removeMax())#6
    ds.add(2)
    ds.add(1)
    print(ds.removeMax())#5
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

#方法二：
class Node:
    def __init__(self,val,next=None):
        self.val=val
        self.next=next

class DataStream:
    def __init__(self):
        self.dummy_node=Node(-1)

    #o(1):按头节点值最大存储规则
    def add(self, val):
        #找：第一个比val小的节点
        prev,curr=self.dummy_node,self.dummy_node.next
        while curr:
            if curr.val<val:
                break
            prev=curr
            curr=curr.next
        #将元素添加至该节点前面
        new_node=Node(val,curr)
        prev.next=new_node

    #o(1)
    def removeMax(self):
        if not self.dummy_node.next:
            raise Exception('removeMax失败，因为数据流中无元素')
        #保存需要返回的最大值（头节点值）
        res=self.dummy_node.next.val
        #删除（头节点）
        head=self.dummy_node.next
        self.dummy_node.next=head.next
        head.next=None

        return res


if __name__=='__main__':
    ds=DataStream()
    ds.add(3)
    print(ds.removeMax())#3
    ds.add(6)
    ds.add(5)
    print(ds.removeMax())#6
    ds.add(2)
    ds.add(1)
    print(ds.removeMax())#5
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

1.2基于二叉堆实现DataStream

class MaxHeap:
    def __init__(self,__comp,data=None):
        self.__comp=__comp
        if not data:
            self.data=[]
        else:
            self.data=data[:]
            for i in range(self.lastNonLeafIndex(),-1,-1):
                self.siftDown(i)

    def size(self):
        return len(self.data)
    def isEmpty(self):
        return len(self.data)==0

    #左孩子节点索引
    def leftChild(self,index):
        return index*2+1
    #右孩子节点索引
    def rightChild(self,index):
        return index*2+2
    #父节点索引
    def parent(self,index):
        if index==0:
            raise Exception('index-0 does not have parent')
        return (index-1)//2

    #最后一个父节点：最后一个叶子结点的父节点
    def lastNonLeafIndex(self):
        #最后一个叶子节点索引
        last_leaf_index=len(self.data)-1
        #转化
        return self.parent(last_leaf_index)

    #上浮保持完全二叉树
    def siftUp(self,index):
        e=self.data[index]

        while index>0:
            parent_node_val=self.data[self.parent(index)]
        #循环比较:小值通过赋值下浮
            if self.__comp(e,parent_node_val)<=0:
                break
            self.data[index]=parent_node_val
            index=self.parent(index)
        #最后’index’处进行赋值
        self.data[index]=e

    #下浮保持完全二叉树
    def siftDown(self,index):
        e=self.data[index]
        while self.leftChild(index)<len(self.data):
            #寻左右子节点中最大值节点
            max_node_index=self.leftChild(index)
            if self.rightChild(index)<len(self.data):
                right_node_val=self.data[self.rightChild(index)]
                left_node_val=self.data[self.leftChild(index)]
                if self.__comp(right_node_val,left_node_val)>0:
                    max_node_index=self.rightChild(index)
        # 循环比较：大值通过赋值上浮
            if self.__comp(e,self.data[max_node_index])>=0:
                break
            self.data[index]=self.data[max_node_index]
            index=max_node_index
        # 最后’index’处进行赋值
        self.data[index]=e


    #o(logn)
    def add(self,e):
        self.data.append(e)
        self.siftUp(len(self.data)-1)



    def findMax(self):
        if self.isEmpty():
            raise Exception('Heap is Empty')
        return self.data[0]
    #o(logn)
    def removeMax(self):
        max_val=self.findMax()
        #最后节点替换为头节点，并删除
        last=self.data[len(self.data)-1]
        self.data[0]=last
        self.data.pop()
        #通过下沉恢复成大顶堆
        if len(self.data)>=1:
            self.siftDown(0)

        return max_val

class DataStream:
    def __init__(self, __comp):
        self.maxHeap = MaxHeap(__comp)

    # 时间复杂度：O(logn)
    def add(self, val):
        self.maxHeap.add(val)

    # O(logn)
    def removeMax(self):
        return self.maxHeap.removeMax()


def sort(data):
    # 1. 建堆，堆化 O(n)
    max_heap = MaxHeap(lambda a, b: a - b, data)

    # 2. 排序
    i, tmp = len(data) - 1, [0] * len(data)

    # O(nlogn)
    while not max_heap.isEmpty():
        tmp[i] = max_heap.removeMax()
        i -= 1

    # 3. 拷贝
    for i in range(len(data)):
        data[i] = tmp[i]

if __name__ == '__main__':
    ds = DataStream(lambda a, b: a - b)
    ds.add(3)
    print(ds.removeMax())  # 打印 3
    ds.add(6)
    ds.add(5)
    print(ds.removeMax())  # 打印 6
    ds.add(2)
    ds.add(1)
    print(ds.removeMax())  # 打印 5
    
    #HeapSort
    data = [15, 17, 19, 13, 22, 16, 28, 30, 42, 66]
    sort(data)
    print(data)
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

1.3基于二叉堆实现优先队列

在这里插入图片描述

class MaxHeap:
    def __init__(self,__comp,data=None):
        self.__comp=__comp
        if not data:
            self.data=[]
        else:
            self.data=data[:]
            for i in range(self.lastNonLeafIndex(),-1,-1):
                self.siftDown(i)

    def size(self):
        return len(self.data)
    def isEmpty(self):
        return len(self.data)==0

    #左孩子节点索引
    def leftChild(self,index):
        return index*2+1
    #右孩子节点索引
    def rightChild(self,index):
        return index*2+2
    #父节点索引
    def parent(self,index):
        if index==0:
            raise Exception('index-0 does not have parent')
        return (index-1)//2

    #最后一个父节点：最后一个叶子结点的父节点
    def lastNonLeafIndex(self):
        #最后一个叶子节点索引
        last_leaf_index=len(self.data)-1
        #转化
        return self.parent(last_leaf_index)

    #上浮保持完全二叉树
    def siftUp(self,index):
        e=self.data[index]

        while index>0:
            parent_node_val=self.data[self.parent(index)]
        #循环比较:小值通过赋值下浮
            if self.__comp(e,parent_node_val)<=0:
                break
            self.data[index]=parent_node_val
            index=self.parent(index)
        #最后’index’处进行赋值
        self.data[index]=e

    #下浮保持完全二叉树
    def siftDown(self,index):
        e=self.data[index]
        while self.leftChild(index)<len(self.data):
            #寻左右子节点中最大值节点
            max_node_index=self.leftChild(index)
            if self.rightChild(index)<len(self.data):
                right_node_val=self.data[self.rightChild(index)]
                left_node_val=self.data[self.leftChild(index)]
                if self.__comp(right_node_val,left_node_val)>0:
                    max_node_index=self.rightChild(index)
        # 循环比较：大值通过赋值上浮
            if self.__comp(e,self.data[max_node_index])>=0:
                break
            self.data[index]=self.data[max_node_index]
            index=max_node_index
        # 最后’index’处进行赋值
        self.data[index]=e


    #o(logn)
    def add(self,e):
        self.data.append(e)
        self.siftUp(len(self.data)-1)



    def findMax(self):
        if self.isEmpty():
            raise Exception('Heap is Empty')
        return self.data[0]
    #o(logn)
    def removeMax(self):
        max_val=self.findMax()
        #最后节点替换为头节点，并删除
        last=self.data[len(self.data)-1]
        self.data[0]=last
        self.data.pop()
        #通过下沉恢复成大顶堆
        if len(self.data)>=1:
            self.siftDown(0)

        return max_val



class PriorityQueue:
    def __init__(self,__comp):
        self.maxHeap=MaxHeap(__comp)

    def getsize(self):
        return self.maxHeap.size()
    def isEmpty(self):
        return self.maxHeap.isEmpty()

    def enqueue(self,e):
        self.maxHeap.add(e)
    def dequeue(self):
        return self.maxHeap.removeMax()

    def getFront(self):
        return self.maxHeap.findMax()

if __name__ == '__main__':
    ds = PriorityQueue(lambda a, b: a - b)
    ds.enqueue(3)
    print(ds.dequeue())  # 打印 3
    ds.enqueue(6)
    ds.enqueue(5)
    print(ds.dequeue())  # 打印 6
    ds.enqueue(2)
    ds.enqueue(1)
    print(ds.dequeue())  # 打印 5
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

2.Set

2.1数组set

class ArraySet:
    def __init__(self):
        self.data=[]

    def size(self):
        return len(self.data)
    def isEmpty(self):
        return len(self.data)==0

    #o(1)
    def add(self,e):
        if self.data.count(e)==0:
            self.data.append(e)
    def remove(self,e):
        if self.data.count(e)>0:
            self.data.remove(e)

    def contain(self,e):
        return self.data.count(e)>0

    def toString(self):
        return "ArraySet[ data = {} ]".format(self.data)


if __name__=='__main__':
    set1=ArraySet()
    set1.add(2)
    set1.add(4)
    set1.add(1)
    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contain(4))

    set1.remove(1)
    print(set1.toString())
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

2.2链表set

class Node:
    def __init__(self, e, next=None):
        self.e = e
        self.next = next

    def toString(self):
        return str(self.e)


class LinkedList:
    def __init__(self):
        self.dummyHead = Node(-1)
        self.size = 0

    def getSize(self):
        return self.size

    def isEmpty(self):
        return self.size == 0

    """
        查询操作
    """
    # 查询指定索引的节点的值
    # 时间复杂度： O(n)
    def get(self, index):
        if index < 0 or index >= self.getSize():
            raise Exception("get failed, require index >= 0 && index < size")

        curr = self.dummyHead.next
        for i in range(0, index):
            curr = curr.next

        return curr.e

    # 时间复杂度： O(1)
    def getFirst(self):
        return self.get(0)

    def getLast(self):
        return self.get(self.size - 1)

    """
        修改操作
    """
    # 修改指定索引的节点元素
    # 时间复杂度： O(n)
    def set(self, index, e):
        if index < 0 or index >= self.getSize():
            raise Exception("set failed, require index >= 0 && index < size")

        curr = self.dummyHead.next
        for i in range(0, index):
            curr = curr.next

        curr.e = e

    """
        新增操作
    """
    # 在指定索引的位置插入新的节点
    # 时间复杂度： O(n)
    def add(self, index, e):
        if index < 0 or index > self.getSize():
            raise Exception("add failed, require index >= 0 && index < size")

        prev = self.dummyHead
        for i in range(0, index):
            prev = prev.next

        prev.next = Node(e, prev.next)
        self.size += 1

    # 在链表表头新增节点
    # 时间复杂度： O(1)
    def addFirst(self, e):
        self.add(0, e)

    # 在链表表尾新增节点
    # 时间复杂度： O(n)
    def addLast(self, e):
        self.add(self.size, e)

    """
        删除操作
    """
    # 删除指定索引的节点，并返回删除的节点的值
    # 时间复杂度： O(n)
    def remove(self, index):
        if index < 0 or index >= self.getSize():
            raise Exception("remove failed, require index >= 0 && index < size")

        prev = self.dummyHead
        for i in range(0, index):
            prev = prev.next

        del_node = prev.next
        prev.next = del_node.next
        del_node.next = None

        self.size -= 1
        return del_node.e

    # 时间复杂度： O(1)
    def removeFirst(self):
        return self.remove(0)

    # 时间复杂度： O(n)
    def removeLast(self):
        return self.remove(self.size - 1)

    # 删除第一个值等于 e 的节点
    # 时间复杂度： O(n)
    def removeElement(self, e):
        if self.dummyHead.next is None:
            raise Exception("removeElement failed, LinkedList is Empty")
        prev, curr = self.dummyHead, self.dummyHead.next
        while curr:
            if curr.e == e:
                break
            prev = curr
            curr = curr.next
        # bug 修复，需要先判断 curr
        # 如果 curr 为 None 的话，说明链表中不存在值等于 e 的节点
        if curr:
            prev.next = curr.next
            curr.next = None

    # 判断链表中是否存在指定元素
    # 时间复杂度： O(n)
    def contains(self, e):
        curr = self.dummyHead.next
        while curr:
            if curr.e == e:
                return True
            curr = curr.next
        return False

    def toString(self):
        res = ""
        curr = self.dummyHead.next
        while curr:
            res += curr.toString() + "=>"
            curr = curr.next
        res += "null"
        return res


class LinkedListSet:
    def __init__(self):
        self.data=LinkedList()

    def size(self):
        return self.data.getSize()
    def isEmpty(self):
        return self.data.isEmpty()

    def add(self,e):
        if not self.data.contains(e):
            self.data.addFirst(e)
    def remove(self,e):
        if self.data.contains(e):
            self.data.removeElement(e)

    def contains(self,e):
        return self.data.contains(e)


    def toString(self):
        return 'LinkedListSet[ data={} ]'.format(self.data.toString())


if __name__ == '__main__':
    set1 = LinkedListSet()
    set1.add(2)
    set1.add(4)
    set1.add(1)

    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contains(4))

    set1.remove(1)
    print(set1.toString())
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

2.3二叉搜索树set

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BST:
    def __init__(self, __comp):
        self.root = None
        self.size = 0
        self.__comp = __comp

    def getSize(self):
        return self.size

    def isEmpty(self):
        return self.size == 0

 # 插入：o(logn)
    def add(self, e):
        if self.root is None:
            self.root = TreeNode(e)
        else:
            curr = self.root
            while curr:
                # 比较
                if self.__comp(e, curr.data) == 0:
                    return
                elif self.__comp(e, curr.data) < 0 and not curr.left:
                    curr.left = TreeNode(e)
                    self.size += 1
                    return
                elif self.__comp(e, curr.data) > 0 and not curr.right:
                    curr.right = TreeNode(e)
                    self.size += 1
                    return
                if self.__comp(e, curr.data) < 0:
                    curr = curr.left
                else:
                    curr = curr.right

# 修改o(logn)：set(src,target)会破坏二叉搜索树的顺序

#查询
    def contains(self, target):
        node = self.find(target)
        if not node:
            return False
        return True

    #O(logn)
    def find(self, target):
        if not self.root:
            return None
        curr = self.root
        while curr:
            if self.__comp(target, curr.data) == 0:
                return curr
            elif self.__comp(target, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right
        return None

    # 中序遍历：方便观察结果，找bug
    def inOrder(self):
        res = []

        def inOrderR(node):
            if not node:
                return []
            inOrderR(node.left)
            res.append(node.data)
            inOrderR(node.right)

        inOrderR(self.root)
        return res

    #O(logn)
    def minValue(self):
        if not self.root:
            raise Exception("tree is null")
        min_node = self.root
        while min_node.left:
            #最深最左
            min_node = min_node.left
        return min_node.data

    #O(logn)
    def maxValue(self):
        if not self.root:
            raise Exception("tree is null")
        max_node = self.root
        while max_node.right:
            #最深最右
            max_node = max_node.right
        return max_node.data

#删除
    #O(logn)
    def removeMin(self):
        if not self.root:
            raise Exception("tree is null")
        # 找
        min_node, parent = self.root, None
        while min_node.left:
            parent = min_node
            min_node = min_node.left
        #删
        if not parent:
            #位于根节点处
            self.root = self.root.right
        else:
            #key
            parent.left = min_node.right

        min_node.right = None
        self.size -= 1
        return min_node.data

    # 时间复杂度：O(logn)
    def removeMax(self):
        if not self.root:
            raise Exception("tree is null")
        # 找
        max_node, parent = self.root, None
        while max_node.right:
            parent = max_node
            max_node = max_node.right
        #删
        if not parent:
            #位于根节点处
            self.root = self.root.left
        else:
            parent.right = max_node.left

        max_node.left = None
        self.size -= 1
        return max_node.data

    #优化: O(logn)
    def remove_2(self, e):
        if not self.root:
            return
        #找
        curr, parent = self.root, None
        while curr and self.__comp(e, curr.data) != 0:
            parent = curr
            if self.__comp(e, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right
        # 如果没有找到需要删除的元素，则直接返回
        if not curr:
            return

        #情况简化
        if curr.left and curr.right:
            #找右子树最小值
            min_node, min_parent = curr.right, curr
            while min_node.left:
                min_parent = min_node
                min_node = min_node.left
            #覆盖该删除节点值
            curr.data = min_node.data
            #curr变为叶子节点：情况则简化成三种
            curr, parent = min_node, min_parent

        #确定开删节点是仅有一个子树节点还是叶子节点
        if curr.left:
            child = curr.left
            # if parent:
            #     curr.left = None
        elif curr.right:
            child = curr.right
            # if parent:
            #     curr.right = None
        else:
            child = None

        #开删
        if not parent:
            self.root = child
        elif curr == parent.left:
            parent.left = child
        elif curr == parent.right:
            parent.right = child

        self.size -= 1

    #o(logn)
    def remove_1(self, e):
        if not self.root:
            return

        curr, parent = self.root, None
        # 找
        while curr and self.__comp(e, curr.data) != 0:
            parent = curr
            if self.__comp(e, curr.data) < 0:
                curr = curr.left
            else:
                curr = curr.right

        # 如果没有找到需要删除的元素，则直接返回
        if not curr:
            return

        # 删
        if not curr.left and not curr.right:
            if not parent:
                self.root = None
            elif curr == parent.left:
                parent.left = None
            elif curr == parent.right:
                parent.right = None
        elif curr.left and not curr.right:
            if not parent:
                self.root = curr.left
            elif curr == parent.left:
                parent.left = curr.left
                curr.left = None
            elif curr == parent.right:
                parent.right = curr.left
                curr.left = None
        elif not curr.left and curr.right:
            if not parent:
                self.root = curr.right
            elif curr == parent.left:
                parent.left = curr.right
                curr.right = None
            elif curr == parent.right:
                parent.right = curr.right
                curr.right = None
        elif curr.left and curr.right:
            #找右子树最小值
            min_node, min_parent = curr.right, curr
            while min_node.left:
                min_parent = min_node
                min_node = min_node.left

            ##覆盖该删除节点值
            curr.data = min_node.data

            #覆盖该删除节点值
            # 先拿到要删除 min 节点的右子树
            right = min_node.right
            # bug 修复：这里删除 min 节点，需要区分 min 是父亲节点的右子节点还是左子节点
            # 要删除 min 节点是父亲节点的右子节点
            if min_parent.right == min_node:
                """
                比如我们要删除以下树的节点70
                        33
                     /      \
                   22        66
                           /    \
                         35      70
                                   \
                                    99
                那么这个时候：minParent = 66，min = 70，即 min 是父亲节点的右子节点
                """
                # 将 min 的右子树挂到父亲节点的右子树中
                min_parent.right = right
            else:
                # 要删除 min 节点是父亲节点的左子节点
                """
                比如我们要删除以下树的节点68
                        33
                     /      \
                   22        66
                           /    \
                         35      70
                               /   \
                             68     99
                               \
                                69
                那么这个时候：minParent = 70，min = 68，即 min 是父亲节点的左子节点
                """
                # 将 min 的右子树挂到父亲节点的左子树中
                min_parent.left = right
            # 删掉 min 的右子树，这样可以使得 min 节点从树中断开
            min_node.right = None

        self.size -= 1

class BSTSet:
    def __init__(self, __comp):
        self.bst = BST(__comp)

    def size(self):
        return self.bst.getSize()

    def isEmpty(self):
        return self.bst.isEmpty()

    def add(self, e):
        self.bst.add(e)

    def remove(self, e):
        self.bst.remove_1(e)

    def contains(self, e):
        return self.bst.contains(e)

    def toString(self):
        return "BSTSet[ data = {} ]".format(self.bst.inOrder())


if __name__ == '__main__':
    set1 = BSTSet(lambda a, b: a - b)
    set1.add(2)
    set1.add(4)
    set1.add(1)

    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contains(4))

    set1.remove(1)
    print(set1.toString())
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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324

2.4HashSet

#基本实现

class HashSet:
    def __init__(self,__hash):
        self.data=[None]*10
        self.__size=0
        self.__hash=__hash

    #e对应hash值
    def hash(self,e,length):
        return abs(self.__hash(e))%length

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size==0

    def add(self,e):
        index=self.hash(e,len(self.data))
        if not self.data[index]:
            self.data[index]=e
            self.__size+=1
            #扩容
            if self.__size==len(self.data):
                self.resize(2*len(self.data))
    def resize(self,newCapacity):
        new_data=[None]*newCapacity
        for i in range(len(self.data)):
            if self.data[i]:
                new_index=self.hash(self.data[i],newCapacity)
                new_data[new_index]=self.data[i]
            self.data=new_data


    def remove(self,e):
        index=self.hash(e,len(self.data))
        if self.data[index]:
            self.data[index]=None
            self.__size-=1


    def contains(self,e):
        index=self.hash(e,len(self.data))
        return self.data[index]!=None

    def toString(self):
        return 'HashSet [data = {} ]'.format(self.data)

if __name__ == '__main__':
    set1 = HashSet(lambda a: a)
    set1.add(2)
    set1.add(4)
    set1.add(1)

    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contains(4))

    set1.remove(1)
    print(set1.toString())
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

#解决Hash冲突：基于开放寻址

class Item:
    def __init__(self,data):
        self.data=data
        self.is_deleted=False

    def toString(self):
        return str(self.data)



class HashSet:
    def __init__(self,__hash,__equal):
        self.items=[None]*10
        self.__size=0
        self.__hash=__hash
        self.__equal=__equal

        #记录删除元素个数
        self.delete_count=0
        #扩展因子
        self.loadFactor=0.75

    def hash(self,e,length):
        return abs(self.__hash(e))%length

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size==0



    def add(self,e):
        index=self.hash(e,len(self.items))
#若已存在且为e，直接返回
        if self.items[index] and self.__equal(e, self.items[index]):
            return

# 辅助变量
        add_index,is_first=index,True
        #找：等于null或已删除的第一个元素
        while self.items[index] and not self.items[index].is_deleted:
            if (not self.items[index] or self.items[index].is_deleted) and is_first:
                add_index,is_first=index,False
            index+=1
            index=index%len(self.items)

#找到：add_index为null或已删除元素
        #若为已删除元素，通过add后，count-=1
        if self.items[add_index] and self.items[add_index].is_deleted:
            self.delete_count-=1
        #
        self.items[add_index] = Item(e)
        self.__size += 1

#扩容
        if self.__size>=len(self.items)*self.loadFactor:
            self.resize(2*len(self.items))

    def resize(self,newCapacity):
        new_data=[None]*newCapacity
        for i in range(len(self.items)):
            if self.items[i] and not self.items[i].is_deleted:
                new_index=self.hash(self.items[i],newCapacity)
                new_data[new_index]=self.items[i]
            self.items=new_data
            #清理标记删除元素
            self.delete_count=0


    def remove(self,e):
        index=self.hash(e,len(self.items))
#找：等于e或null的元素
        while self.items[index] and not self.__equal(e,self.items[index].data):
            index+=1
            index=index%len(self.items)
        if self.items[index]:
            self.items[index].is_deleted=True
            self.__size-=1
            self.delete_count+=1
#删除标记太多，缩容
        if self.delete_count+self.__size>=len(self.items)*self.loadFactor:
            self.resize(len(self.items))




    def contains(self,e):
        index=self.hash(e,len(self.items))
        #找
        while self.items[index] and not self.__equal(e,self.items[index].data):
            index+=1
            index=index%len(self.items)
        #找到
        return self.items[index] and not self.items[index].is_deleted

    def toString(self):
        res=''
        for data in self.items:
            if data and not data.is_deleted:
                res+=data.toString()+','
        return res

if __name__=='__main__':
    set1 = HashSet(lambda a: a, lambda a, b: a == b)
    set1.add(2)
    set1.add(4)
    set1.add(1)

    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contains(4))

    set1.remove(1)
    print(set1.toString())

        #找到
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

#解决Hash冲突：基于链表：

class Node:
    def __init__(self,val,next=None):
        self.val=val
        self.next=next

    def toString(self):
        return str(self.val)


class HashSet:
    def __init__(self,__hash,__equal):
        self.data=[None]*10
        self.__size=0
        self.__hash=__hash
        self.__equal=__equal
        self.loadFactor=0.75

    def hash(self,e,length):
        return abs(self.__hash(e))%length

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size==0



    def add(self,e):
        index=self.hash(e,len(self.data))
        #
        if not self.data[index]:
            self.data[index]=Node(e)
            self.__size+=1
        #
        prev,curr=None,self.data[index]
        while curr:
            if self.__equal(e,curr.val):
                return
            prev=curr
            curr=curr.next
        prev.next=Node(e)
        self.__size+=1
        #扩容
        if self.__size==len(self.data)*self.loadFactor:
            self.resize(2*len(self.data))
    def resize(self,newCapacity):
        new_data=[None]*newCapacity
        for i in range(len(self.data)):
            curr=self.data[i]
            while curr:
                e=curr.val
                new_index = self.hash(e, newCapacity)
                # 通过数组属性，定位
                head = new_data[new_index]

                # 通过链表属性，扩链
                if not head:
                    new_data[new_index] = Node(e)
                else:
                    new_data[new_index] = Node(e)
                    new_data[new_index].next = head
                curr = curr.next
        self.data=new_data


    def remove(self,e):
        index=self.hash(e,len(self.data))
        #
        if not self.data[index]:
            return
        #
        prev,curr=None,self.data[index]
        while curr:
            if self.__equal(e,curr.val):
                if not prev:
                    #e为头节点
                    self.data[index]=curr.next
                else:
                    prev.next=curr.next
                    curr.next=None
                self.__size-=1
                break
            prev=curr
            curr=curr.next

    def contains(self,e):
        index=self.hash(e,len(self.data))
        if not self.data[index]:
            return False

        curr=self.data[index]
        while curr:
            if self.__equal(e,curr.val):
                return True
            curr=curr.next
        return False

    def toString(self):
        res=''
        for node in self.data:
            while node:
                res+=node.toString()+'=>'
                node=node.next
        return res


if __name__ == '__main__':
    set1 = HashSet(lambda a: a, lambda a, b: a == b)
    set1.add(2)
    set1.add(4)
    set1.add(1)

    print(set1.toString())

    set1.add(2)
    print(set1.toString())

    print(set1.contains(4))

    set1.remove(1)
    print(set1.toString())
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

3.Map

#链表Map

class Node:
    def __init__(self,key=None,value=None,next=None):
        self.key=key
        self.value=value
        self.next=next

    def toString(self):
        return str(self.key)+'->'+str(self.value)


class LinkedListMap:
    def __init__(self,__equal):
        self.dummyHead=Node()
        self.__size=0
        self.__equal=__equal

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size==0


    def add(self,key,value):
        curr=self.getNode(key)
        #
        if not curr:
            self.dummyHead.next=Node(key,value,self.dummyHead.next)
            self.__size+=1
        else:
            curr.value=value
    def getNode(self,key):
        curr=self.dummyHead.next
        while curr:
            if self.__equal(key,curr.key):
                break
            curr=curr.next
        return curr





    def remove(self,key):
        #定位
        prev,curr=self.dummyHead,self.dummyHead.next
        while curr:
            if self.__equal(key,curr.key):
                break
            prev=curr
            curr=curr.next
        #删
        if curr:
            prev.next=curr.next
            curr.next=None
            self.__size-=1
            return curr.value
        return None



    def set(self,key,new_value):
        curr=self.getNode(key)
        if curr:
            curr.value=new_value
        else:
            raise Exception('没有对应的key：{}'.format(key))
    def get(self,key):
        node=self.getNode(key)
        return node.value if node else None
    def containsKey(self,key):
        node=self.getNode(key)
        return node!=None
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

#二叉搜索树Map

class TreeNode:
    def __init__(self,key,value,left=None,right=None):
        self.key=key
        self.value=value
        self.left=left
        self.right=right

class BSTMap:
    def __init__(self,__comp):
        self.root=None
        self.__size=0
        self.__comp=__comp

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size==0


    #o(logn)
    def add(self,key,value):
        self.root=self.addR(self.root,key,value)
    def addR(self,node,key,value):
        #终止条件
        if not node:
            self.__size+=1
            return TreeNode(key,value)

        #递归
        if self.__comp(key,node.key)<0:
            node.left=self.addR(node.left,key,value)
        elif self.__comp(key,node.key)>0:
            node.right=self.addR(node.right,key,value)
        return node


    #o(logn)
    def remove(self,key):
        node=self.getR(self.root,key)
        #
        if not node:
            return None
        #
        if self.__comp(key,node.key)<0:
            node.left=self.removeR(node.left,key)
            return node
        elif self.__comp(key,node.key)>0:
            node.right=self.removeR(node.right,key)
        else:
            #找到：删除节点为node
            #情况一
            if not node.left:
                #
                right_node=node.right
                #
                node.right=None
                self.__size-=1
                return right_node
            #情况2
            if not node.right:
                #
                left_node=node.left
                #
                node.left=None
                self.__size-=1
                return left_node
            #情况3
            successor=self.minValueR(node.right)
                #注意次序
            successor.right=self.removeMinR(node.right)
            successor.left=node.left

            node.left=None
            node.right=None
            return successor


    def minValueR(self, node):
        if not node.left:
            return node
        return self.minValueR(node.left)
    # 删除以  node 为根节点的子树的最小节点
    # 并返回删除完最小节点的子树的根节点
    def removeMinR(self, node):
        if not node.left:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node
        left_root = self.removeMinR(node.left)
        node.left = left_root
        return node





    def set(self,key,new_value):
        node=self.getR(self.root,key)
        #
        if not node:
            raise Exception('没有对应的key：{}'.format(key))
        #
        node.value=new_value

    def get(self,key):
        node=self.getR(self.root,key)
        return node.value if node else None
    def getR(self,node,key):
        if not node:
            return None

        if self.__comp(key,node.key)==0:
            return node
        elif self.__comp(key,node.key)<0:
            return self.getR(node.left,key)
        else:
            return self.getR(node.right,key)

    def contains(self,key):
        node=self.getR(self.root,key)
        return node!=None
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

#HashMap

class Node:
    def __init__(self,key=None,value=None,next=None):
        self.key=key
        self.value=value
        self.next=next

    def toString(self):
        return str(self.key)+'->'+str(self.value)

class HashMap:
    def __init__(self,__hash,__equal,initCapacity=25,loadFactor=0.75):
        self.data=[None]*initCapacity
        self.__size=0
        self.__hash=__hash
        self.__equal=__equal
        self.loadFactor=loadFactor

    #key->索引
    def hash(self,key,length):
        return abs(self.__hash(key))%length

    def size(self):
        return self.__size
    def isEmpty(self):
        return self.__size

    def add(self,key,value):
        #目：'数组'属性位置
        index=self.hash(key,len(self.data))
        #目：链表属性位置
        curr=self.getNode(key,index)

        if not curr:
            self.data[index]=Node(key,value,self.data[index])
            self.__size+=1
            #扩容
            if self.__size>=len(self.data)*self.loadFactor:
                self.resize(2*len(self.data))
        else:
            curr.value=value
    def getNode(self,key,index):
        curr=self.data[index]
        while curr:
            if self.__equal(key,curr.key):
                break
            curr=curr.next
        return curr
    def resize(self,new_capacity):
        new_data=[None]*new_capacity
        for i in range(len(self.data)):
            curr=self.data[i]
            while curr:
                #'数组'属性定位
                key=curr.key
                new_index=self.hash(key,new_capacity)
                head=new_data[new_index]
                #链表属性扩容
                if not head:
                    new_data[new_index] = Node(key, curr.value)
                else:
                    new_data[new_index] = Node(key, curr.value)
                    new_data[new_index].next=head
                curr=curr.next
        self.data=new_data




    def remove(self,key):
        index=self.hash(key,len(self.data))
        #
        if not self.data[index]:
            return None
        #
        prev,curr=None,self.data[index]
        while curr:
            if self.__equal(key,curr.key):
                #删头
                if not prev:
                    self.data[index]=curr.next
                else:
                    prev.next=curr.next
                curr.next=None
                self.__size -= 1
                return curr.value
            prev=curr
            curr=curr.next
        return None






    def set(self,key,new_value):
        index=self.hash(key,len(self.data))
        node=self.getNode(key,index)
        if node:
            node.value=new_value
        else:
            raise Exception("没有对应的 key ：{}".format(key))
    def get(self,key):
        index = self.hash(key, len(self.data))
        node = self.getNode(key, index)
        return node.value if node else None
    def containkey(self,key):
        index = self.hash(key, len(self.data))
        node = self.getNode(key, index)
        return node!=None
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

4.跳表

import random

MAX_LEVEL=16

class Node:
    def __init__(self,data):
        self.data=data
        #key:在每一层维护索引节点
        self.nextNodes=[None]*MAX_LEVEL
        self.maxIndexLevel=0


class SkipList:
    def __init__(self,__comp):
        #记录当前跳表最大高度（包含原始链表层）
        self.levelCount=1
        self.dummyHead=Node(-1)
        self.__comp=__comp

    def contains(self,e):
        return self.get(e)
    def get(self,e):
        curr=self.dummyHead
        for i in range(self.levelCount-1,-1,-1):
            while curr.nextNodes[i] and self.__comp(curr.nextNodes[i].data,e)<0:
                curr=curr.nextNodes[i].data
        if curr.nextNodes[0] and self.__comp(curr.nextNodes[0].data,e)==0:
            return curr.nextNodes[0]
        return None


    #目：一层add后，维护上层索引(<=MAX_LEVEL)
    def randomLevel(self):
        level=1
        for i in range(1,MAX_LEVEL):
            if random.randint(0,MAX_LEVEL)%2==1:
                level+=1
        return level

    def add(self,e):
        level=self.randomLevel() if self.dummyHead.nextNodes[0] else 1
        #在各维护层中建立初始化虚拟头节点
        prevNodes=[None]*level
        for i in range(level):
            prevNodes[i]=self.dummyHead

        #找
        #定位于插入节点的前一个节点prev，并赋予prevNodes
        prev=self.dummyHead
        for i in range(self.levelCount-1,-1,-1):
            while prev.nextNodes[i] and self.__comp(prev.nextNodes[i].data,e)<0:
                prev=prev.nextNodes[i]
            if i<level:
                prevNodes[i]=prev
        #添
        #维护各层
        new_node=Node(e)
         #调整属性
        new_node.maxIndexLevel=level
        for i in range(level):
            new_node.nextNodes[i]=prev.nextNodes[i]
            prev.nextNodes[i]=new_node
        #更新链表高度
        if self.levelCount<level:
            self.levelCount=level



    def remove(self,e):
        prevNodes=[None]*self.levelCount
        #找
        prev=self.dummyHead
        for i in range(self.levelCount-1,-1,-1):
            while prev.nextNodes[i] and self.__comp(prev.nextNodes[i].data,e)<0:
                prev=prev.nextNodes[i]
            prevNodes[i]=prev
        #删
        if prev.nextNodes[0] and self.__comp(prev.nextNodes[0].data,e)==0:
            for i in range(self.levelCount-1,-1,-1):
                del_node=prevNodes[i].nextNodes[i]
                if del_node and self.__comp(del_node.data,e)==0:
                    prevNodes[i].nextNodes[i]=del_node.nextNodes[i]
                    del_node.nextNodes[i]=None
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/574739