二叉查找树
- 所有 key 小于 V 的都被存储在 V 的左子树
- 所有 key 大于 V 的都存储在 V 的右子树
BST 的节点
|
1
2
3
|
class BSTNode(object):
def __init__(self, key, value, left=None, right=None):
self.key, self.value, self.left, self.right = key, value, left, right
|
二叉树查找
如何查找一个指定的节点呢，根据定义我们知道每个内部节点左子树的 key 都比它小，右子树的 key 都比它大，所以 对于带查找的节点 search_key，从根节点开始，如果 search_key 大于当前 key，就去右子树查找，否则去左子树查找
|
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
|
NODE_LIST = [
{'key': 60, 'left': 12, 'right': 90, 'is_root': True},
{'key': 12, 'left': 4, 'right': 41, 'is_root': False},
{'key': 4, 'left': 1, 'right': None, 'is_root': False},
{'key': 1, 'left': None, 'right': None, 'is_root': False},
{'key': 41, 'left': 29, 'right': None, 'is_root': False},
{'key': 29, 'left': 23, 'right': 37, 'is_root': False},
{'key': 23, 'left': None, 'right': None, 'is_root': False},
{'key': 37, 'left': None, 'right': None, 'is_root': False},
{'key': 90, 'left': 71, 'right': 100, 'is_root': False},
{'key': 71, 'left': None, 'right': 84, 'is_root': False},
{'key': 100, 'left': None, 'right': None, 'is_root': False},
{'key': 84, 'left': None, 'right': None, 'is_root': False},
]
class BSTNode(object):
def __init__(self, key, value, left=None, right=None):
self.key, self.value, self.left, self.right = key, value, left, right
class BST(object):
def __init__(self, root=None):
self.root = root
@classmethod
def build_from(cls, node_list):
cls.size = 0
key_to_node_dict = {}
for node_dict in node_list:
key = node_dict['key']
key_to_node_dict[key] = BSTNode(key, value=key) # 这里值和key一样的
for node_dict in node_list:
key = node_dict['key']
node = key_to_node_dict[key]
if node_dict['is_root']:
root = node
node.left = key_to_node_dict.get(node_dict['left'])
node.right = key_to_node_dict.get(node_dict['right'])
cls.size += 1
return cls(root)
def _bst_search(self, subtree, key):
"""
subtree.key小于key则去右子树找 因为 左子树<subtree.key<右子树
subtree.key大于key则去左子树找 因为 左子树<subtree.key<右子树
:param subtree:
:param key:
:return:
"""
if subtree is None:
return None
elif subtree.key < key:
self._bst_search(subtree.right, key)
elif subtree.key > key:
self._bst_search(subtree.left, key)
else:
return subtree
def get(self, key, default=None):
"""
查找树
:param key:
:param default:
:return:
"""
node = self._bst_search(self.root, key)
if node is None:
return default
else:
return node.value
def _bst_min_node(self, subtree):
"""
查找最小值的树
:param subtree:
:return:
"""
if subtree is None:
return None
elif subtree.left is None:
# 找到左子树的头
return subtree
else:
return self._bst_min_node(subtree.left)
def bst_min(self):
"""
获取最小树的value
:return:
"""
node = self._bst_min_node(self.root)
if node is None:
return None
else:
return node.value
def _bst_max_node(self, subtree):
"""
查找最大值的树
:param subtree:
:return:
"""
if subtree is None:
return None
elif subtree.right is None:
# 找到右子树的头
return subtree
else:
return self._bst_min_node(subtree.right)
def bst_max(self):
"""
获取最大树的value
:return:
"""
node = self._bst_max_node(self.root)
if node is None:
return None
else:
return node.value
def _bst_insert(self, subtree, key, value):
"""
二叉查找树插入
:param subtree:
:param key:
:param value:
:return:
"""
# 插入的节点一定是根节点，包括 root 为空的情况
if subtree is None:
subtree = BSTNode(key, value)
elif subtree.key > key:
subtree.left = self._bst_insert(subtree.left, key, value)
elif subtree.key < key:
subtree.right = self._bst_insert(subtree.right, key, value)
return subtree
def add(self, key, value):
# 先去查一下看节点是否已存在
node = self._bst_search(self.root, key)
if node is not None:
# 更新已经存在的 key
node.value = value
return False
else:
self.root = self._bst_insert(self.root, key, value)
self.size += 1
def _bst_remove(self, subtree, key):
"""
删除并返回根节点
:param subtree:
:param key:
:return:
"""
if subtree is None:
return None
elif subtree.key > key:
subtree.right = self._bst_remove(subtree.right, key)
return subtree
elif subtree.key < key:
subtree.left = self._bst_remove(subtree.left, key)
return subtree
else:
# 找到了需要删除的节点
# 要删除的节点是叶节点 返回 None 把其父亲指向它的指针置为 None
if subtree.left is None and subtree.right is None:
return None
# 要删除的节点有一个孩子
elif subtree.left is None or subtree.right is None:
# 返回它的孩子并让它的父亲指过去
if subtree.left is not None:
return subtree.left
else:
return subtree.right
else:
# 有两个孩子，寻找后继节点替换，并从待删节点的右子树中删除后继节点
# 后继节点是待删除节点的右孩子之后的最小节点
# 中(根)序得到的是一个排列好的列表 后继节点在待删除节点的后边
successor_node = self._bst_min_node(subtree.right)
# 用后继节点替换待删除节点即可保持二叉查找树的特性 左<根<右
subtree.key, subtree.value = successor_node.key, successor_node.value
# 从待删除节点的右子树中删除后继节点，并更新其删除后继节点后的右子树
subtree.right = self._bst_remove(subtree.right, successor_node.key)
return subtree
def remove(self, key):
assert key in self
self.size -= 1
return self._bst_remove(self.root, key)
|
以上就是Python 实现二叉查找树的示例代码的详细内容，更多关于Python 实现二叉查找树的资料请关注服务器之家其它相关文章！
原文链接：https://www.cnblogs.com/guotianbao/p/12789825.html