$25
CS5800-Homework 8 Solved
1 Implement a hash for text
import re
MAXHASH = 2500
class Node: def i n i t ( self , k , val ) :
s e l f . next = None s e l f . key = k s e l f . value = val
class LinkedList : def i n i t ( s e l f ) : s e l f . head = None s e l f . size = 0
def add front ( self , key , value ) : newNode = Node(key , value ) newNode. next = s e l f . head
s e l f . head = newNode s e l f . size += 1
def remove( self , key) :
if s e l f . head is None: return False if s e l f . head . 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 s e l f . head = s e l f . head . next
26 s e l f . size = s e l f . size −1
27 return True
28 cur = s e l f . head . next
29 prev = s e l f . head
30 while cur is not None: 31if cur . key == key :
32prev . next = cur . next
33s e l f . size = s e l f . size −1
34return True
35prev = cur
36cur = cur . next
37return False
38
39def search ( self , key) :
40if s e l f . head is not None:
41cur = s e l f . head 42while cur is not None: 43if cur . key == key :
44return cur
45cur = cur . next
46return None
47
48def iter ( s e l f ) :
49if not s e l f . head :
50return
51cur = s e l f . head
52print( cur . key , ” : ” , cur . value ) 53while cur . next :
54cur = cur . next
55print( cur . key , ” : ” , cur . value )
56
57def hashFunction (key) :
58 hash num = 0 59 for i in key :
60 hash num += ord( i )
61 return hash num
62
63 class HashMap:
64 def i n i t ( self , capacity , function ) :
65 s e l f . buckets = [ ] 66 for i in range( capacity ) :
67 s e l f . buckets . append( LinkedList () )
68 #capacity = the total number of buckets to be crrated in the hash table
69s e l f . maxhash = capacity
70#function = the hash function to use for
hashing
71 s e l f . hash function = function
72s e l f . size = 0
73
74#empties the hash table 75def clear ( s e l f ) :
76s e l f . buckets = [ ]
77for i in range( s e l f . capacity ) :
78s e l f . buckets . append( LinkedList () )
79s e l f . size = 0
80
81#update the given key , value in the hash table 82def insert ( self , key , value ) :
83 hash num = s e l f . hash function (key)
84 index = hash num % s e l f . maxhash
85bucket = s e l f . buckets [ index ]
86node = bucket . search (key) #check the bucket by
key
87if node is not None: #already exist , then
update
88node . value = value
89return
90else : #not exist , then add value
91 s e l f . buckets [ index ] . add front (key , value )
92s e l f . size += 1
93
94 #remove and free with given key 95 def delete ( self , key) :
96 hash num = s e l f . hash function (key)
97
index = hash num % s e l f . maxhash
98
bucket = s e l f . buckets [ index ]
99
node = bucket . search (key) #check the key
bucket
by
100
if node is not None: #already exist , delete
then
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
bucket . remove(key)
s e l f . size −= 1
#search a key exists def find ( self , key) :
hash num = s e l f . hash function (key)
index = hash num % s e l f . maxhash bucket = s e l f . buckets [ index ] node = bucket . search (key) #check the key if node is not None:
return True
else :
return False
#return the value def get ( self , key) :
hash num = s e l f . hash function (key)
index = hash num % s e l f . maxhash bucket = s e l f . buckets [ index ] node = bucket . search (key) #check the
bucket
bucket
by
by
key
121 if node is not None: 122 return node . value 123 else :
124 return False
125
126 #get how many empty buckets in the table 127 def empty buckets ( s e l f ) :
128 num = 0
129 for buckets in s e l f . buckets : 130 if buckets . head is None: 131 num += 1
132 return num
133
134 def print hash ( s e l f ) :
135 for i in s e l f . buckets :
136 if i . size != 0:
137i . iter ()
138
139def t e s t f i l e ( file ) :
140hash map = HashMap(MAXHASH, hashFunction )
141rgx = re . compile(”(\w[\w ’]∗\w|\w)”) 142l i s t a l l k e y s = set ()
143with open( file ) as f :
144for line in f : 145words = rgx . findall ( line ) 146for word in words :
147word = word . lower () #covert to
lowercase
148l i s t a l l k e y s . add(word)
149 word count = hash map . get (word) 150if word count is None: 151hash map . insert (word , 1)
152else :
153 hash map . insert (word , word count+1)
154f . close ()
155
156with open( ’ keys . txt ’ , ’w’ ) as f : 157for word in l i s t a l l k e y s :
158value = hash map . get (word)
159f . write (word)
160f . write (” : ”)
161f . write ( str ( value ) )
162f . write ( ’\n ’ )
163f . close ()
164
165 def test () :
166 hash map = HashMap(MAXHASH, hashFunction )
167 rgx = re . compile(”(\w[\w ’]∗\w|\w)”)
168 line = ’ Alice was beginning to get very tired of sitting by her sister on the bank , and of having nothing to do . Once or twice she had peeped
into the book her sister was reading , but it had no pictures or conversations in it , ”and what is the use of a book ,” thought Alice , ”without
pictures or conversations ?” ’
words = words = rgx . findall ( line )
#insert key for word in words :
word = word . lower () #covert to lowercase
#l i s t a l l k e y s . add(word) word count = hash map . get (word)
if word count is None:
hash map . insert (word , 1)
else :
hash map . insert (word , word count+1) hash map . print hash ()
#delete key hashmap . delete ( ’ conversations ’ ) print(”After delete : ”) hashmap . print hash ()
#find key result = hash map . find ( ’on ’ ) print( result )
if
name == ’ main ’ :
t e s t f i l e ( ’ alice in wonderland . txt ’ )
#test ()
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
2 Implement a red-black tree
class RBTree node :
def i n i t ( self , x) : s e l f . key = x s e l f . l e f t = None s e l f . right = None s e l f . parent = None s e l f . color = ’ black ’
class RBTree: def i n i t ( s e l f ) : s e l f . nil = RBTree node(0) s e l f . root = s e l f . nil
#class Function :
def inorder tree walk ( self , x) :
if x != None: s e l f . inorder tree walk (x . l e f t ) if x . key != 0:
print( ’key : ’ , x . key , ’ parent : ’ , x .
parent . key , ’ color : ’ , x . color )
s e l f . inorder tree walk (x . right )
def left rotate ( self , T, x) :
y = x . right #set y
x . right = y . l e f t #turn y ’ s l e f t subtree into x ’ s right subtree
if y . l e f t != T. nil :
y . l e f t . parent = x
y . parent = x . parent #link x ’ s parent to y
if x . parent == T. nil :
T. root = y elif x == x . parent . l e f t :
x . parent . l e f t = y else :
x . parent . right = y
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
y . l e f t = x #put x on y ’ s l e f t
35
36
x . parent = y
37 def
right rotate ( self , T, x) :
38
y = x . l e f t
39
x . l e f t = y . right
40
41
42
43
44
45
46
47
48
49
50
51
52def
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
if y . right != T. nil :
y . right . parent = x
y . parent = x . parent
if x . parent == T. nil :
T. root = y elif x == x . parent . right :
x . parent . right = y else :
x . parent . l e f t = y
y . right = x
x . parent = y
RBInsert ( self , T, z) :
z . l e f t = z . right = z . parent = T. nil
y = T. nilx = T. root while x != T. nil : y = x if z . key < x . key :
x = x . l e f t else :
x = x . right
z . parent = yif y == T. nil :
T. root = z elif z . key < y . key :
y . l e f t = z
68
else :
69
y . right = z
70
z . l e f t = T. nil
71
z . right = T. nil
72 z . color = ’ red ’
73 s e l f . RBInsert fixup (T, z)
74
75 def RBInsert fixup ( self , T, z) :
76 while z . parent . color == ’ red ’ :
77 if z . parent == z . parent . parent . l e f t :
78y = z . parent . parent . right 79if y . color == ’ red ’ :
80z . parent . color = ’ black ’
#case 1
81y . color = ’ black ’
#case 1
82z . parent . parent . color = ’ red ’
#case 1
83z = z . parent . parent
#case 1
84else :
85if z == z . parent . right :
86z = z . parent
#case
2
87 s e l f . left rotate (T, z)
#case 2
88z . parent . color = ’ black ’
#case 3
89z . parent . parent . color = ’ red ’
#case 3
90 s e l f . right rotate (T, z . parent .
parent ) #case 3
91else : #same as then clause with ’ right ’ and
’ l e f t ’ exchange
92y = z . parent . parent . l e f t 93if y . color == ’ red ’ :
94z . parent . color = ’ black ’
95 y . color = ’ black ’
96 z . parent . parent . color = ’ red ’
97 z = z . parent . parent
98 else :
99 if z == z . parent . l e f t :
100 z = z . parent
101 s e l f . right rotate (T, z)
102 z . parent . color = ’ black ’
103 z . parent . parent . color = ’ red ’
104 s e l f . left rotate (T, z . parent . parent
120
if
w. color == ’ red ’ :
121
w. color = ’ black ’
#case 1
122
x . parent . color = ’ red ’
#case 1
123
s e l f . left rotate (T, x . parent )
#case 1
124
w = x . parent . right
#case 1
125
if
w. l e f t . color == ’ black ’ and w. right .
color == ’ black ’ :
126
w. color == ’ red ’
#case 2
127
x = x . parent
)
105T. root . color = ’ black ’
106
107def transplant ( self , T, u, v) :
108if u. parent == T. nil :
109T. root = v
110elif u == u. parent . l e f t : 111u. parent . l e f t = v 112else :
113u. parent . right = v
114v . parent = u. parent
115
116 def RBDelete fixup ( self , T, x) :
117while x != T. root and x . color == ’ black ’ : 118if x == x . parent . l e f t :
119w = x . parent . right
#case 2
128 else :
129 if w. right . color == ’ black ’ :
130 w. l e f t . color == ’ black ’
#case 3
131 w. color = ’ red ’
#case 3
132 s e l f . right rotate (T, x)
140 if
w. color == ’ red ’ :
141
w. color = ’ black ’
142
x . parent . color = ’ red ’
143
s e l f . right rotate (T, x . parent )
144
w = x . parent . l e f t
145 if
w. right . color == ’ black ’ and w. l e f t .
color == ’ black ’ :
146
w. color = ’ red ’
147
x = x . parent
#case 3
133w. color = x . parent . color
#case 4
134x . parent . color = ’ black ’
#case 4
135w. right . color = ’ black ’
#case 4
136 s e l f . left rotate (T, x . parent )
#case 4
137x = T. root
#case 4
138else : #same as then clause with ’ right ’
and ’ l e f t ’ exchanged
139w = x . parent . l e f t
148else :
149if w. l e f t . color == ’ black ’ :
150w. right . color = ’ black ’
151w. color = ’ red ’
152 s e l f . left rotate (T, w)
153 w = x . parent . l e f t
154 w. color = x . parent . color 155 x . parent . color = ’ black ’
156 w. l e f t . color = ’ black ’
157
s e l f . right rotate (T, x . parent )
158
x = T. root
159
160
x . color = ’ black ’
161
def
RBDelete( self , T, z) :
162
y = z
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
def
y original color = y . color if z . l e f t == T. nil :
x = z . rights e l f . transplant (T, z , z . right )
elif z . right == T. nil :
x = z . l e f ts e l f . transplant (T, z , z . l e f t )
else :
y = s e l f . tree minimum(z . right )
y original color = y . color
x = y . right
if y . parent == z :
x . parent = yelse :
s e l f . transplant (T, y , y . right ) y . right = z . right
y . right . parent = y
s e l f . transplant (T, z , y) y . l e f t = z . l e f t
y . l e f t . parent = y
y . color = z . color
if y original color == ’ black ’ :
s e l f . RBDelete fixup (T, x)
tree minimum( self , x) :
while x . l e f t != s e l f . nil :
x = x . l e f t
return x
192
def
tree maximum( self , x) :
193
while x . right != s e l f . nil :
194
x = x . right
195
196
return x
197
def
tree successor ( self , x) :
198
if x . right != s e l f . nil :
199
return s e l f . tree minimum(x . right )
200
y = x . parent
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
def
def
def
while y != s e l f . nil and x == y . right : x = y
y = y . parent
return y
tree predecessor ( self , x) :
if x . l e f t != s e l f . nil :
return s e l f . tree maximum(x . l e f t )
y = x . parent while y != s e l f . nil and x == y . l e f t :
x = y
y = y . parent
return y
iterative tree search ( self , x , k) :
while x != s e l f . nil :
if k == x . key : return x
elif k < x . key :
x = x . l e f t else :
x = x . right return None
tree depth ( self , T) −> int :
if T is None:
return 0
return max( s e l f . tree depth (T. l e f t ) ,
s e l f .
tree depth (T. right ) )+1
229
230 def test () :
231 nodes = [11 ,2 ,14 ,1 ,7 ,15 ,5 ,8 ,4]
T = RBTree()
#x = Function () for node in nodes :
T. RBInsert (T, RBTree node(node) )
T. inorder tree walk (T. root ) h = T. tree depth (T. root )
print(”The height of RB tree is : ” , h−1)
#search node ’ s key i f it in the RB tree value = 7
y = T. iterative tree search (T. root , value )
if y != None:
print(y . key , ” is
else :
print( value , ” is tree ”)
#find node ’ s predecessor if y != None:
temp = T. tree predecessor (y)
print(”The predecessor of” , y . key , ” is ” , temp .
key)
temp = T. tree successor (y)
print(”The successor of” , y . key , ” is ” , temp . key
)
#insert new key to RB tree
T. RBInsert (T, RBTree node(10) ) print(”After insert node : ”) T. inorder tree walk (T. root )
#delete node delete = 14
T. RBDelete(T, T. iterative tree search (T. root , delete ) )
print(”After delete node : ”)
T. inorder tree walk (T. root )
if
name == ’ main ’ :
test ()
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
3 Implement the skiplist data structure
import random
#random number has biggest limitation maxLevel = 16
#random level , select random number between 1 to maxRand
randLevel = random . randint (1 , maxLevel)
class SkipNode : def i n i t ( self , val ) : s e l f . value = val s e l f . right = None s e l f .down = None
class SkipList : def i n i t ( s e l f ) :
#i n i t i a l i z e header and sentinel to infinity header = [ SkipNode(−float ( ’ inf ’ ) ) for i in range(maxLevel) ]
sentinel = [ SkipNode( float ( ’ inf ’ ) ) for i in range(maxLevel) ]
#connect them together for i in range(maxLevel − 1) : header [ i ] . right = sentinel [ i ] header [ i ] . down = header [ i +1]
sentinel [ i ] . down = sentinel [ i +1]
#the last layer of header don ’ t have ”down” option
header [ −1]. right = sentinel [−1]
#skiplist i n i t i a l pointer is header ’ s f i r s t element
s e l f . head = header [0]
#search begin with i n i t i a l pointer def search ( self , target : int ) −> bool :
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
31node = s e l f . head 32while node :
33if node . right . value > target :
34node = node .down
35elif node . right . value < target :
36node = node . right
37else :
38return True
39return False
40
41def add( self , num: int ) −> None:
42#use prev array to store skpilist pointer before jump down
43prev = [ ]
44node = s e l f . head 45while node :
46if node . right . value >= num:
47prev . append(node)
48node = node .down 49else :
50node = node . right
51
52#arr is the array of pointer to be inserted , randomly in length
53arr = [ SkipNode(num) for i in range( randLevel ) ] 54temp = SkipNode(None)
55for i , j in zip( prev [ maxLevel − len( arr ) :] , arr )
:
56j . right = i . right
57i . right = j
58temp .down = j
59temp = j
60
61def earse ( self , num: int ) −> bool :
62ans = False
63node = s e l f . head 64while node :
65if node . right . value > num:
node = node .down
elif node . right . value < num:
node = node . right else :
ans = True node . right = node . right . right node = node .down return ans
def test () : sl = SkipList () sl . add(20) sl . add(40) sl . add(10) sl . add(20) sl . add(5) sl . add(80) sl . earse (20) sl . add(100) sl . add(20) sl . add(30) sl . earse (5) sl . add(50)
print( sl . search (80) ) sl . earse (10)
print( sl . search (10) )
if name == ’ main ’ :
test ()
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
