Skip to content

Commit c561269

Browse files
heqin-zhuheqin-zhu
committed
b tree ✌️
1 parent a8fcf41 commit c561269

16 files changed

Lines changed: 2358 additions & 1313 deletions

File tree

‎README.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,6 @@ I use python 3.6+ and c++ to implements them.
77
Since I used f-Strings in python, you may use python 3.6+ to run the following python scripts.
88

99
>>I am still learning new things and this repo is always updating.
10-
Some scripts may have bugs or not be finished yet.
1110
1211
# Notice
1312
Currently, Github can't render latex math formulas.

‎algorithm/dynamic-programming/Vec2d.hs‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
module Vec2d
2+
(Vec2d,
3+
getVal,
4+
setVal
5+
) where
6+
import Data.List (intercalate)
7+
8+
data Vec2d a = Vec (Int,Int) [a] | Vec2 [[a]]
9+
10+
instance (Show a)=>Show (Vec2d a) where
11+
show (Vec2 ll) = show2d ll
12+
show (Vec (x,y) lst) = show2d $ slice y lst
13+
14+
getVal i j (Vec (x,y) lst) = lst !! (i*y+j)
15+
getVal i j (Vec2 ll) = ll !! i !! j
16+
17+
setVal val i j (Vec (x,y) lst) =
18+
let pos = i*y+j
19+
before = take pos lst
20+
after = drop (pos+1) lst
21+
in Vec (x,y) $before ++ [val] ++ after
22+
23+
setVAl val i j (Vec2 ll) =
24+
let before = take i ll
25+
origin = ll !! i
26+
new = take j origin ++ [val] ++ drop (j+1) origin
27+
after = drop (i+1) ll
28+
in Vec2 $before ++ [new] ++ after
29+
30+
show2d::(Show a)=>[[a]]->String
31+
show2d ll =
32+
let str =concat . map (\lst-> show lst ++",\n") $ll -- intercalate ",\n" . map show $ ll
33+
in "Vector 2d: [\n"++str++ "]\n"
34+
35+
slice n lst
36+
| length lst <= n = [lst]
37+
| otherwise = (take n lst) : (slice n $drop n lst)
38+

‎algorithm/dynamic-programming/__pycache__/LCS.cpython-37.pyc‎

759 Bytes
Binary file not shown.

‎algorithm/dynamic-programming/lcs.hs‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
import Vec2d (Vec2d,getVal,setVal)
2+
3+
4+
lcs a b =
5+
let m = lenghth a
6+
n = length b
7+
rst = []
8+
in 1 --to do

‎algorithm/dynamic-programming/lcs.py‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
def lcs(a,b):
2+
'''time: O(mn); space: O(mn)'''
3+
m,n= len(a),len(b)
4+
board = [[[] for i in range(n+1)] for i in range(m+1)]
5+
for i in range(m):
6+
for j in range(n):
7+
if a[i]==b[j]:
8+
board[i+1][j+1] =board[i][j]+[a[i]]
9+
elif len(board[i][j+1]) < len(board[i+1][j]):
10+
board[i+1][j+1] = board[i+1][j]
11+
else :
12+
board[i+1][j+1] = board[i][1+j]
13+
return board[m][n]
14+
15+
def lcs2(a,b):
16+
'''time: O(mn); space: O(m)'''
17+
m,n= len(a),len(b)
18+
board = [[] for i in range(n+1)]
19+
for i in range(m):
20+
last = []
21+
for j in range(n):
22+
if a[i]==b[j]:
23+
board[j+1] =board[j]+[a[i]]
24+
elif len(board[j+1]) < len(last):
25+
board[j+1] = last
26+
last = board[j+1]
27+
return board[n]
28+
29+
if __name__ =='__main__':
30+
a="dsaffqewqfqewregqwefqwe"
31+
b="adsfsfs3qt5yhyh24efwq"
32+
print(lcs(a,b))
33+
print(lcs2(a,b))

‎algorithm/dynamic-programming/matrix-multiply.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
def adjustOrd(sizes):
2+
''' adjust the chain-multiply of matrix, sizes=[row1,row2,..,rown,coln]'''
3+
n = len(sizes)
4+
if n<3: return

‎algorithm/dynamic-programming/splitStripe.hs‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
import qualified Data.Map as M
2+
3+
{-
4+
count function:
5+
There is stripe which length is n,
6+
priceMap contains a map for different length of stripe and its price
7+
then find the maximum price to split the stripe in different shorter stripes
8+
( including the original length if possible)
9+
-}
10+
11+
priceMap = M.fromList [(1,1),(2,5),(3,8),(4,9),(5,10),(6,17),(7,17),(8,20),(9,24),(10,30)]
12+
13+
count n priceMap = _count 1 $M.fromList [(0,0)]
14+
where
15+
end = n+1
16+
_count cur rst
17+
| cur == end = rst
18+
| otherwise = _count (1+cur) (M.insert cur price rst)
19+
where
20+
newRst = M.insert cur (getValue cur priceMap) rst
21+
price = maximum. map getPrice $[0..div cur 2]
22+
getPrice a = (getValue a newRst ) + (getValue (cur-a) newRst)
23+
getValue key mp
24+
| M.member key mp = mp M.! key
25+
| otherwise = 0

‎algorithm/dynamic-programming/splitStripe.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
'''
2+
There is stripe which length is n,
3+
priceMap contains a map for different length of stripe and its price
4+
then find the maximum price to split the stripe in different shorter stripes
5+
( including the original length if possible)
6+
'''
7+
8+
def count(n,prices):
9+
def best(cur):
10+
# note that copying the list or create a new list in the following new_stripes codes
11+
if cur in values: return values[cur],stripes[cur]
12+
maxPrice = 0
13+
new_stripes=[]
14+
for i,j in prices.items():
15+
if i<=cur:
16+
p, tmp = best(cur-i)
17+
if maxPrice<p+j:
18+
new_stripes = tmp+[i] # if the list is not copyed, create a new list, don't use append
19+
maxPrice =p+j
20+
values[cur] = maxPrice
21+
stripes[cur] = new_stripes
22+
return maxPrice,new_stripes
23+
values = {0:0}
24+
stripes = {0:[]}
25+
return best(n)
26+
27+
28+
29+
if __name__=='__main__':
30+
li = [(1,1),(2,5),(3,8),(4,9),(5,10),(6,17),(7,17),(8,20),(9,24),(10,30)]
31+
prices = {i:j for i,j in li}
32+
n = 40
33+
34+
d = {i:count(i,prices) for i in range(n+1)}
35+
for i in range(n+1):
36+
print(i,d[i])

‎algorithm/dynamic-programming/testVec2d.hs‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
import Vec2d
2+
main = do
3+
let d=[1..10]
4+
ll = [[(i,j)| i<-[1..5]] | j<-['a'..'g']]
5+
print (Vec (2,5) d)
6+
print (Vec (5,2) d)
7+
print (Vec2 ll)

‎dataStructure/bTree.py‎

Lines changed: 212 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,212 @@
1+
class node:
2+
def __init__(self,keys=None,isLeaf = True,children=None):
3+
if keys is None:keys=[]
4+
if children is None: children =[]
5+
self.keys = keys
6+
self.isLeaf = isLeaf
7+
self.children = []
8+
def __getitem__(self,i):
9+
return self.keys[i]
10+
def __delitem__(self,i):
11+
del self.keys[i]
12+
def __setitem__(self,i,k):
13+
self.keys[i] = k
14+
def __len__(self):
15+
return len(self.keys)
16+
def __repr__(self):
17+
return str(self.keys)
18+
def __str__(self):
19+
children = ','.join([str(nd.keys) for nd in self.children])
20+
return f'keys: {self.keys}\nchildren: {children}\nisLeaf: {self.isLeaf}'
21+
def getChd(self,i):
22+
return self.children[i]
23+
def delChd(self,i):
24+
del self.children[i]
25+
def setChd(self,i,chd):
26+
self.children[i] = chd
27+
def getChildren(self,begin=0,end=None):
28+
if end is None:return self.children[begin:]
29+
return self.children[begin:end]
30+
def findKey(self,key):
31+
for i,k in enumerate(self.keys):
32+
if k>=key:
33+
return i
34+
return len(self)
35+
def update(self,keys=None,isLeaf=None,children=None):
36+
if keys is not None:self.keys = keys
37+
if children is not None:self.children = children
38+
if isLeaf is not None: self.isLeaf = isLeaf
39+
def insert(self,i,key=None,nd=None):
40+
if key is not None:self.keys.insert(i,key)
41+
if not self.isLeaf and nd is not None: self.children.insert(i,nd)
42+
def isLeafNode(self):return self.isLeaf
43+
def split(self,prt,t):
44+
# form new two nodes
45+
k = self[t-1]
46+
nd1 = node()
47+
nd2 = node()
48+
nd1.keys,nd2.keys = self[:t-1], self[t:] # note that t is 1 bigger than key index
49+
nd1.isLeaf = nd2.isLeaf = self.isLeaf
50+
if not self.isLeaf:
51+
# note that children index is one bigger than key index, and all children included
52+
nd1.children, nd2.children = self.children[0:t], self.children[t:]
53+
# connect them to parent
54+
idx = prt.findKey(k)
55+
if prt.children !=[]: prt.children.remove(self) # remove the original node
56+
prt.insert(idx,k,nd2)
57+
prt.insert(idx,nd = nd1)
58+
return prt
59+
60+
61+
class bTree:
62+
def __init__(self,degree=2):
63+
self.root = node()
64+
self.degree=degree
65+
self.nodeNum = 1
66+
self.keyNum = 0
67+
def search(self,key,withpath=False):
68+
nd = self.root
69+
fathers = []
70+
while True:
71+
i = nd.findKey(key)
72+
if i==len(nd): fathers.append((nd,i-1,i))
73+
else: fathers.append((nd,i,i))
74+
if i<len(nd) and nd[i]==key:
75+
if withpath:return nd,i,fathers
76+
else:return nd,i
77+
if nd.isLeafNode():
78+
if withpath:return None,None,None
79+
else:return None,None
80+
nd = nd.getChd(i)
81+
def insert(self,key):
82+
if len(self.root)== self.degree*2-1:
83+
self.root = self.root.split(node(isLeaf=False),self.degree)
84+
self.nodeNum +=2
85+
nd = self.root
86+
while True:
87+
idx = nd.findKey(key)
88+
if idx<len(nd) and nd[idx] == key:return
89+
if nd.isLeafNode():
90+
nd.insert(idx,key)
91+
self.keyNum+=1
92+
return
93+
else:
94+
chd = nd.getChd(idx)
95+
if len(chd)== self.degree*2-1: #ensure its keys won't excess when its chd split and u
96+
nd = chd.split(nd,self.degree)
97+
self.nodeNum +=1
98+
else:
99+
nd = chd
100+
def delete(self,key):#to do
101+
'''search the key, delete it , and form down to up to rebalance it '''
102+
nd,idx ,fathers= self.search(key,withpath=True)
103+
if nd is None : return
104+
del nd[idx]
105+
self.keyNum-=1
106+
if not nd.isLeafNode():
107+
chd = nd.getChd(idx) # find the predecessor key
108+
while not chd.isLeafNode():
109+
fathers.append((chd,len(chd)-1,len(chd)))
110+
chd = chd.getChd(-1)
111+
fathers.append((chd,len(chd)-1,len(chd)))
112+
nd.insert(idx,chd[-1])
113+
del chd[-1]
114+
if len(fathers)>1:self.rebalance(fathers)
115+
def rebalance(self,fathers):
116+
nd,keyIdx,chdIdx = fathers.pop()
117+
while len(nd)<self.degree-1: # rebalance tree from down to up
118+
prt,keyIdx,chdIdx = fathers[-1]
119+
lbro = [] if chdIdx==0 else prt.getChd(chdIdx-1)
120+
rbro = [] if chdIdx==len(prt) else prt.getChd(chdIdx+1)
121+
if len(lbro)<self.degree and len(rbro)<self.degree: # merge two deficient nodes
122+
beforeNode,afterNode = None,None
123+
if lbro ==[]:
124+
keyIdx = chdIdx
125+
beforeNode,afterNode = nd,rbro
126+
else:
127+
beforeNode,afterNode = lbro,nd
128+
keyIdx = chdIdx-1 # important, when choosing
129+
keys = beforeNode[:]+[prt[keyIdx]]+afterNode[:]
130+
children = beforeNode.getChildren() + afterNode.getChildren()
131+
isLeaf = beforeNode.isLeafNode()
132+
prt.delChd(keyIdx+1)
133+
del prt[keyIdx]
134+
nd.update(keys,isLeaf,children)
135+
prt.children[keyIdx]=nd
136+
self.nodeNum -=1
137+
elif len(lbro)>=self.degree: # rotate when only one sibling is deficient
138+
keyIdx = chdIdx-1
139+
nd.insert(0,prt[keyIdx]) # rotate keys
140+
prt[keyIdx] = lbro[-1]
141+
del lbro[-1]
142+
if not nd.isLeafNode(): # if not leaf, move children
143+
nd.insert(0,nd=lbro.getChd(-1))
144+
lbro.delChd(-1)
145+
else:
146+
keyIdx = chdIdx
147+
nd.insert(len(nd),prt[keyIdx]) # rotate keys
148+
prt[keyIdx] = rbro[0]
149+
del rbro[0]
150+
if not nd.isLeafNode(): # if not leaf, move children
151+
#note that insert(-1,ele) will make the ele be the last second one
152+
nd.insert(len(nd),nd=rbro.getChd(0))
153+
rbro.delChd(0)
154+
if len(fathers)==1:
155+
if len(self.root)==0:
156+
self.root = nd
157+
self.nodeNum -=1
158+
break
159+
nd,i,j = fathers.pop()
160+
def __str__(self):
161+
head= '\n'+'-'*30+'B Tree'+'-'*30
162+
tail= '-'*30+'the end'+'-'*30+'\n'
163+
lst = [[head],[f'node num: {self.nodeNum}, key num: {self.keyNum}']]
164+
cur = []
165+
ndNum =0
166+
ndTotal= 1
167+
que = [self.root]
168+
while que!=[]:
169+
nd = que.pop(0)
170+
cur.append(repr(nd))
171+
ndNum+=1
172+
que+=nd.getChildren()
173+
if ndNum==ndTotal:
174+
lst.append(cur)
175+
cur = []
176+
ndNum = 0
177+
ndTotal =len(que)
178+
lst.append([tail])
179+
lst = [','.join(li) for li in lst]
180+
return '\n'.join(lst)
181+
def __iter__(self,nd = None):
182+
if nd is None: nd = self.root
183+
que = [nd]
184+
while que !=[]:
185+
nd = que.pop(0)
186+
yield nd
187+
if nd.isLeafNode():continue
188+
for i in range(len(nd)+1):
189+
que.append(nd.getChd(i))
190+
191+
192+
if __name__ =='__main__':
193+
bt = bTree()
194+
from random import shuffle,sample
195+
n = 20
196+
lst = [i for i in range(n)]
197+
shuffle(lst)
198+
test= sample(lst,len(lst)//4)
199+
print(f'building b-tree with {lst}')
200+
for i in lst:
201+
bt.insert(i)
202+
#print(f'inserting {i})
203+
#print(bt)
204+
print(bt)
205+
print(f'serching {test}')
206+
for i in test:
207+
nd,idx = bt.search(i)
208+
print(f'node: {repr(nd)}[{idx}]== {i}')
209+
for i in test:
210+
print(f'deleting {i}')
211+
bt.delete(i)
212+
print(bt)

0 commit comments

Comments
 (0)