fork download
copy 
  1. # make a global red black tree 
  2. # add nodes in it
  3. # RED => 0
  4. # BLACK => 1
  5.  
  6. class RBNode:
  7. 	"""docstring for RedBlack"""
  8. 	def __init__(self,data=None,color=0,parent=None,leftChild=None,rightChild=None):
  9. 		self.data=data
  10. 		self.parent=parent
  11. 		self.leftChild=leftChild
  12. 		self.color=color
  13. 		self.rightChild=rightChild
  14.  
  15.  
  16.  
  17. class RBTree:
  18. 			"""insert rotate left , rotate right, fixup"""
  19.  
  20.  
  21. 			def __init__(self):
  22. 				self.root = RBNode()
  23.  
  24. 			def insert(self,x):
  25. 				if self.root==None:
  26. 					self.root = x
  27. 				y = self.root
  28. 				z= None
  29. 				while y!=None:
  30. 					z = y
  31. 					if x.data > y.data :
  32. 						y=y.rightChild
  33. 					else:
  34. 						y=y.leftChild
  35. 				x.parent = z
  36. 				if x.data > z.data:
  37. 					z.rightChild = x
  38.  
  39. 				else:
  40. 					z.leftChild = x #Rename this 		
  41.  
  42. 			def rotateLeft (self,x):
  43. 				y = x.rightChild
  44. 				x.rightChild = y.leftChild
  45. 				if y.leftChild != None:
  46. 					y.leftChild.parent = x
  47. 				y.parent= x.parent
  48. 				if x.parent == None:
  49. 					self.root = y
  50. 				elif x.parent.leftChild ==x:
  51. 					x.parent.leftChild=y
  52. 				else:
  53. 					x.parent.rightChild = y
  54. 				y.leftChild = x
  55. 				x.parent=y
  56.  
  57. 				#compltete!!
  58.  
  59. 			def rotateRight(self,x):
  60. 				y= x.leftChild
  61. 				x.leftChild = y.rightChild
  62. 				if x.leftChild !=None :
  63. 					x.leftChild.parent = x
  64.  
  65. 				y.parent =  x.parent
  66. 				if x.parent == None:
  67. 					self.root = y
  68. 				elif x == x.parent.leftChild:
  69. 					x.parent.leftChild = y
  70. 				else:
  71. 					x.parent.rightChild = y
  72.  
  73. 				y.rightChild =x
  74. 				x.parent = y
  75. 				#compltete it
  76.  
  77. 			def insertFix(self,z):
  78. 				#CASE 1 parent of z is left child
  79. 				# 1. uncle of z is red 
  80. 				if z.parent == None:
  81. 					z.color=1
  82. 					return z
  83.  
  84. 				while z.parent.color == 0:
  85. 					if z.parent.parent!=None and z.parent == z.parent.parent.leftChild:  # parent of z if left child
  86. 						y= z.parent.parent.rightChild     # y uncle of z
  87. 						if y.color == 0:# and statement
  88. 							z.parent.color = 1
  89. 							y.color = 1
  90. 							z.parent.parent.color = 0
  91. 							z = z.parent.parent
  92. 						else:
  93. 							# 2. z is right child of its parent or uncle is black
  94. 							if z == z.parent.rightChild:
  95. 								z= z.parent
  96. 								self.rotateLeft(z)
  97.  
  98.  
  99. 								#case
  100. 						 	self.rotateRight(z.parent.parent)
  101. 						 	z.parent.color =1
  102. 							z.parent.parent.color = 0
  103.  
  104. 					else :#parent is right child 
  105. 						#uncle is red 
  106. 						if z.parent.parent.leftChild!=None and z.parent.parent.color==0:
  107. 							z.parent.parent.color = 0
  108. 							z.parent.parent.leftChild.color = 1
  109. 							z.parent.color = 1
  110. 							z = z.parent.parent
  111. 						else:
  112. 							if z == z.parent.leftChild:
  113. 								self.rotateRight(z.parent)
  114. 							self.rotateLeft(z.parent.parent)
  115. 							z.parent.color = 1
  116. 							z.parent.leftChild.color = 0
  117. 							z=  z.parent
  118.  
  119.  
  120.  
  121. def Visit(x):
  122. 	if x!= None:
  123. 		Visit(x.leftChild)
  124. 		print(x)
  125. 		Visit(x.rightChild)
  126.  
  127.  
  128.  
  129.  
  130. ########### MAIN PROGRAMM #################
  131.  
  132. tree = RBTree()
  133. n = input()
  134. p = raw_input().split()
  135.  
  136. for i in range(0,n):
  137. 	node = RBNode(p[i])
  138. 	tree.insert(node)
  139. 	tree.insertFix(node)
  140.  
  141. #
  142.  
  143.  
  144.  
  145. ########### MAIN PROGRAMM #################
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
Runtime error #stdin #stdout #stderr 0s 23352KB
comments (?)
stdin
copy 
1
3
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 139, in <module>
  File "prog.py", line 106, in insertFix
AttributeError: 'NoneType' object has no attribute 'leftChild'
https://ideone.com/fi6FxR
language:
Python (cpython 2.7.16)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!