（python）实现Map的两种方法

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
class BSTMap:
class _Node:
def __init__(self,key=None,value=None):
self.key=key
self.value=value
self.left=None
self.right=None
def __str__(self):
return "key:{},Value:{}".format(str(self.key),str(self.value))
def __init__(self):
self._size=0
self._root=None
def get_size(self):
return self._size
def add(self,key,value):
self._root=self._add(self._root,key,value)
def _add(self,node,key,value):
if not node:
self._size+=1
node=self._Node(key,value)
elif node.key==key:
node.value=value
elif node.key>key:
node.left=self._add(node.left,key,value)
else node.key<key:
node.right=self._add(node.right,key,value)
return node
def _get_node(self,node,key):
if not node:
return None
elif node.key==key:
return node.value
elif node.key>key:
return self._get_node(node.left,key)
else:
return self._get_node(node.right,key)
def contains(self,key):
return self._get_node(self._root,key) is not None
def getter(self,key):
node=self._get_node(self._root,key)
return node.value if node is not None else None
def setter(self,key,value):
node=self._get_node(self._root,key)
if not node:
raise ValueError('key{},doesn't exist'.format(str(key)))
node.value=value
def remove(self,key):
node=self._get_node(self.root,key)
if not node:
self._root=self._remove(self._root,key)
return node.value
else:
return None
def _remove(self,node,key):
if not node:
return
if node.key>key:
node.left=self._remove(node.left,key)
elif node.key<key:
node.right=self._remove(node.right,key)
else:
if not node.left:
ret_node=node.right
node.right=None
self._size-=1
return ret_node
elif not node.right:
ret_node=node.left
node.left=None
self._size-=1
return ret_node
else:
ret_node=self._minimun(node.right,node.key)
ret_node.right=self._remove_min(node.right)
ret_node.left=node.left
node.left=node.right=None
return ret_node
def _minimum(self,node):
if not node.left:
return node
return self._minimum(node.left)
def _remove_min(self,node):
if not ndoe.left:
ret_node=node.right
node.right=None
self._size-=1
return ret_node
node.left=self._remove_min(node.left)
return node

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
class LinkedListMap:
def _Node:
def __init__(self,key=None,value,next=None):
self.key=key
self.value=value
self.next=next
def __str(self):
return "Key:{},Value:{}".format(str(self.key),str(self.value))
def __init__(self):
self._dummy_head=self._Node()
self._size=0
def get_node(self,key):
curr=self._dummy_head.next
while curr:
if curr.key==key:
return curr
curr=curr.next
def setter(self,key,value):
node=self.get_node(key)
if not node:
raise ValueError('Key Error')
node.value=value
def add(node,key,value):
node=self.get_node(key)
if not node:
self._dummy_head.next=(self._Node(key,value,self._dummy_head.next)
self._size+=1
else:
node.value=value
def remove(self,key):
pre=self._dummy_head
while prev.next:
if prev.next.key==key
break
prev=pre.next
if pre.next:
del_node=pre.next
pre.next=del_node.next
del_node.next=None
return del_node.value