Skip to content

Commit 64c62a0

Browse files
heqin-zhuheqin-zhu
committed
Finished red black tree, but the script has some bugs and is to be polished
1 parent 3e84fa4 commit 64c62a0

6 files changed

Lines changed: 386 additions & 24 deletions

File tree

‎README.md‎

Lines changed: 12 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,19 @@
1-
# 算法笔记
2-
记录学习算法的一些笔记, 想法, 以及代码实现 :smiley:
1+
# Algorithm and data structures
2+
>Notes and codes for learning algorithm and data structures :smiley:
33
4-
目前正在看`<<算法导论>>`
4+
Some pictures and idead are from `<<Introduction to Algotithm>>
55

6+
I use python 3.6+ and c++ to implements them.
7+
Since I used f-Strings in python, you may use python 3.6+ to run the following python scripts.
68

7-
> 目前 github 上的文档不支持 latex 数学公式渲染
8-
所以如果要读下面的一些笔记(md文件), 可以移步到[我的博客](https://mbinary.coding.me)
9+
>>I am still learning new things and this repo is always updating.
10+
Some scripts may have bugs or not be finished yet.
911

10-
# 索引
12+
# Notice
13+
Currently, Github can't render latex math formulas.
14+
So,if you wannt to view the notes which contains latex math formulas and are in markdown format, you can visit [my blog](https://mbinary.coding.me)
15+
16+
# index
1117
* [.](.)
1218
* [notes](./notes)
1319
* [alg-general.md](./notes/alg-general.md)

‎dataStructure/redBlackTree.py‎

Lines changed: 313 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,313 @@
1+
'''
2+
#########################################################################
3+
# File : redBlackTree.py
4+
# Author: mbinary
5+
# Mail: [email protected]
6+
# Blog: https://mbinary.coding.me
7+
# Github: https://github.com/mbinary
8+
# Created Time: 2018-07-12 20:34
9+
# Description:
10+
#########################################################################
11+
'''
12+
from functools import total_ordering
13+
from random import randint, shuffle
14+
15+
@total_ordering
16+
class node:
17+
def __init__(self,val,left=None,right=None,isBlack=False):
18+
self.val =val
19+
self.left = left
20+
self.right = right
21+
self.isBlack = isBlack
22+
def __lt__(self,nd):
23+
return self.val < nd.val
24+
def __eq__(self,nd):
25+
return nd is not None and self.val==nd.val
26+
def setChild(self,nd,isLeft = True):
27+
if isLeft: self.left = nd
28+
else: self.right = nd
29+
def getChild(self,isLeft):
30+
if isLeft: return self.left
31+
else: return self.right
32+
def __bool__(self):
33+
return self.val is not None
34+
def __str__(self):
35+
color = 'B' if self.isBlack else 'R'
36+
return f'{color}-{self.val:}'
37+
def __repr__(self):
38+
return f'node({self.val},isBlack={self.isBlack})'
39+
class redBlackTree:
40+
def __init__(self):
41+
self.root = None
42+
def getParent(self,val):
43+
if isinstance(val,node):val = val.val
44+
if self.root.val == val:return None
45+
nd = self.root
46+
while nd:
47+
if nd.val>val and nd.left is not None:
48+
if nd.left.val == val: return nd
49+
else: nd = nd.left
50+
elif nd.val<val and nd.right is not None:
51+
if nd.right.val == val: return nd
52+
else: nd = nd.right
53+
def find(self,val):
54+
if isinstance(val,node):val = val.val
55+
nd = self.root
56+
while nd:
57+
if nd.val ==val:
58+
return nd
59+
elif nd.val>val:
60+
nd = nd.left
61+
else:
62+
nd = nd.right
63+
@staticmethod
64+
def checkBlack(nd):
65+
return nd is None or nd.isBlack
66+
@staticmethod
67+
def setBlack(nd,isBlack):
68+
if nd is not None:
69+
if isBlack is None or isBlack:
70+
nd.isBlack = True
71+
else:nd.isBlack = False
72+
def insert(self,val):
73+
if isinstance(val,node):val = val.val
74+
def _insert(root,nd):
75+
'''return parent'''
76+
while root:
77+
if root == nd:return None
78+
elif root>nd:
79+
if root.left :
80+
root=root.left
81+
else:
82+
root.left = nd
83+
return root
84+
else:
85+
if root.right:
86+
root = root.right
87+
else:
88+
root.right = nd
89+
return root
90+
# insert part
91+
nd = node(val)
92+
if self.root is None:
93+
self.root = nd
94+
self.setBlack(self.root,True)
95+
return
96+
parent = _insert(self.root,nd)
97+
if parent is None: return
98+
if not parent.isBlack: self.fixUpInsert(parent,nd)
99+
100+
def fixUpInsert(self,parent,nd):
101+
''' adjust color and level, there are two red nodes: the new one and its parent'''
102+
while not self.checkBlack(parent):
103+
grand = self.getParent(parent)
104+
isLeftPrt = grand.left == parent
105+
uncle = grand.getChild(not isLeftPrt)
106+
if not self.checkBlack(uncle):
107+
# case 1: new node's uncle is red
108+
self.setBlack(grand, False)
109+
self.setBlack(grand.left, True)
110+
self.setBlack(grand.right, True)
111+
nd = grand
112+
parent = self.getParent(nd)
113+
else:
114+
# case 2: new node's uncle is black(including nil leaf)
115+
isLeftNode = parent.left==nd
116+
if isLeftNode ^ isLeftPrt:
117+
# case 2.1 the new node is inserted in left-right or right-left form
118+
# grand grand
119+
# parent or parent
120+
# nd nd
121+
parent.setChild(nd.getChild(isLeftPrt),not isLeftPrt)
122+
nd.setChild(parent,isLeftPrt)
123+
grand.setChild(nd,isLeftPrt)
124+
nd,parent = parent,nd
125+
# case 2.2 the new node is inserted in left-left or right-right form
126+
# grand grand
127+
# parent or parent
128+
# nd nd
129+
grand.setChild(parent.getChild(not isLeftPrt),isLeftPrt)
130+
parent.setChild(grand,not isLeftPrt)
131+
self.setBlack(grand, False)
132+
self.setBlack(parent, True)
133+
self.setBlack(self.root,True)
134+
def sort(self,reverse = False):
135+
''' return a generator of sorted data'''
136+
def inOrder(root):
137+
if root is None:return
138+
if reverse:
139+
yield from inOrder(root.right)
140+
else:
141+
yield from inOrder(root.left)
142+
yield root
143+
if reverse:
144+
yield from inOrder(root.left)
145+
else:
146+
yield from inOrder(root.right)
147+
yield from inOrder(self.root)
148+
def getSuccessor(self,val):
149+
if isinstance(val,node):val = val.val
150+
def _inOrder(root):
151+
if root is None:return
152+
if root.val>= val:yield from _inOrder(root.left)
153+
yield root
154+
yield from _inOrder(root.right)
155+
gen = _inOrder(self.root)
156+
for i in gen:
157+
if i.val==val:
158+
try: return gen.__next__()
159+
except:return None
160+
161+
def delete(self,val):
162+
# delete node in a binary search tree
163+
if isinstance(val,node):val = val.val
164+
nd = self.find(val)
165+
if nd is None: return
166+
y = None
167+
if nd.left and nd.right:
168+
y= self.getSuccessor(val)
169+
else:
170+
y = nd
171+
py = self.getParent(y.val)
172+
x = y.left if y.left else y.right
173+
if py is None:
174+
self.root = x
175+
elif y==py.left:
176+
py.left = x
177+
else:
178+
py.right = x
179+
if y != nd:
180+
nd.val = y.val
181+
182+
# adjust colors and rotate
183+
if self.checkBlack(y): self.fixUpDel(py,x)
184+
185+
def fixUpDel(self,prt,chd):
186+
if self.root == chd or not self.checkBlack(chd):
187+
self.setBlack(chd, True)
188+
return
189+
isLeft = prt.left == chd
190+
brother = prt.getChild(not isLeft)
191+
if self.checkBlack(brother):
192+
# case 1: brother is black
193+
lb = self.checkBlack(brother.left)
194+
rb = self.checkBlack(brother.right)
195+
if lb and rb:
196+
# case 1.1: brother is black and two kids are black
197+
self.setBlack(brother,False)
198+
chd = prt
199+
elif lb or rb:
200+
# case 1.2: brother is black and two kids's colors differ
201+
if self.checkBlack(brother.getChild(not isLeft)):
202+
# uncle's son is nephew, and niece for uncle's daughter
203+
nephew = brother.getChild(isLeft),
204+
print(nephew)
205+
self.setBlack(nephew,True)
206+
self.setBlack(brother,False)
207+
208+
# brother right rotate
209+
prt.setChild(nephew,not isLeft)
210+
nephew.setChild(brother, not isLeft)
211+
brother = prt.right
212+
213+
# case 1.3: brother is black and two kids are red
214+
brother.isBlack = prt.isBlack
215+
self.setBlack(prt,True)
216+
self.setBlack(brother.right,True)
217+
218+
# prt left rotate
219+
prt.setChild(brother.getChild(isLeft),not isLeft)
220+
brother.setChild(prt,isLeft)
221+
chd = self.root
222+
223+
224+
else:
225+
# case 2: brother is red
226+
prt.setChild(brother.getChild(isLeft), not isLeft)
227+
brother.setChild(prt, isLeft)
228+
self.setBlack(prt,False)
229+
self.setBlack(brother,True)
230+
self.setBlack(chd,True)
231+
232+
def display(self):
233+
def getHeight(nd):
234+
if nd is None:return 0
235+
return max(getHeight(nd.left),getHeight(nd.right)) +1
236+
def levelVisit(root):
237+
from collections import deque
238+
lst = deque([root])
239+
level = []
240+
h = getHeight(root)
241+
lv = 0
242+
ct = 0
243+
while lv<=h:
244+
ct+=1
245+
nd = lst.popleft()
246+
if ct >= 2**lv:
247+
lv+=1
248+
level.append([])
249+
level[-1].append(str(nd))
250+
if nd is not None:
251+
lst.append(nd.left)
252+
lst.append(nd.right)
253+
else:
254+
lst.append(None)
255+
lst.append(None)
256+
return level
257+
lines = levelVisit(self.root)
258+
print('-'*5+ 'level visit' + '-'*5)
259+
return '\n'.join([' '.join(line) for line in lines])
260+
261+
def __str__(self):
262+
return self.display()
263+
264+
265+
def genNum(n =10):
266+
nums =[]
267+
for i in range(n):
268+
while 1:
269+
d = randint(0,100)
270+
if d not in nums:
271+
nums.append(d)
272+
break
273+
#nums = [3,4,2,0,1,6]
274+
return nums
275+
276+
def buildTree(n=10,nums=None,visitor=None):
277+
if nums is None: nums = genNum(n)
278+
rbtree = redBlackTree()
279+
print(f'build a red-black tree using {nums}')
280+
for i in nums:
281+
if visitor:
282+
visitor(rbtree)
283+
rbtree.insert(i)
284+
return rbtree
285+
def testInsert():
286+
def visitor(t):
287+
print(t)
288+
nums = [66, 14, 7, 2, 52, 96, 63, 51, 16, 53]
289+
rbtree = buildTree(nums = nums,visitor = visitor)
290+
print('-'*5+ 'in-order visit' + '-'*5)
291+
for i,j in enumerate(rbtree.sort()):
292+
print(f'{i+1}: {j}')
293+
294+
def testSuc():
295+
rbtree = buildTree()
296+
for i in rbtree.sort():
297+
print(f'{i}\'s suc is {rbtree.getSuccessor(i)}')
298+
299+
def testDelete():
300+
#nums = [56, 89, 31, 29, 24, 8, 62, 96, 20, 75] #tuple
301+
nums = [66, 14, 7, 2, 52, 96, 63, 51, 16, 53]
302+
rbtree = buildTree(nums = nums)
303+
print(rbtree)
304+
shuffle(nums)
305+
for i in nums:
306+
print(f'deleting {i}')
307+
rbtree.delete(i)
308+
print(rbtree)
309+
310+
if __name__=='__main__':
311+
testInsert()
312+
#testDelete()
313+
#testSuc()

0 commit comments

Comments
 (0)