# make a global red black tree
# add nodes in it
# RED => 0
# BLACK => 1
class RBNode:
"""docstring for RedBlack"""
def __init__(self,data=None,color=0,parent=None,leftChild=None,rightChild=None):
self.data=data
self.parent=parent
self.leftChild=leftChild
self.color=color
self.rightChild=rightChild
class RBTree:
"""insert rotate left , rotate right, fixup"""
def __init__(self):
self.root = RBNode()
def insert(self,x):
if self.root==None:
self.root = x
y = self.root
z= None
while y!=None:
z = y
if x.data > y.data :
y=y.rightChild
else:
y=y.leftChild
x.parent = z
if x.data > z.data:
z.rightChild = x
else:
z.leftChild = x #Rename this
def rotateLeft (self,x):
y = x.rightChild
x.rightChild = y.leftChild
if y.leftChild != None:
y.leftChild.parent = x
y.parent= x.parent
if x.parent == None:
self.root = y
elif x.parent.leftChild ==x:
x.parent.leftChild=y
else:
x.parent.rightChild = y
y.leftChild = x
x.parent=y
#compltete!!
def rotateRight(self,x):
y= x.leftChild
x.leftChild = y.rightChild
if x.leftChild !=None :
x.leftChild.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.leftChild:
x.parent.leftChild = y
else:
x.parent.rightChild = y
y.rightChild =x
x.parent = y
#compltete it
def insertFix(self,z):
#CASE 1 parent of z is left child
# 1. uncle of z is red
if z.parent == None:
z.color=1
return z
while z.parent.color == 0:
if z.parent.parent!=None and z.parent == z.parent.parent.leftChild: # parent of z if left child
y= z.parent.parent.rightChild # y uncle of z
if y.color == 0:# and statement
z.parent.color = 1
y.color = 1
z.parent.parent.color = 0
z = z.parent.parent
else:
# 2. z is right child of its parent or uncle is black
if z == z.parent.rightChild:
z= z.parent
self.rotateLeft(z)
#case
self.rotateRight(z.parent.parent)
z.parent.color =1
z.parent.parent.color = 0
else :#parent is right child
#uncle is red
if z.parent.parent.leftChild!=None and z.parent.parent.color==0:
z.parent.parent.color = 0
z.parent.parent.leftChild.color = 1
z.parent.color = 1
z = z.parent.parent
else:
if z == z.parent.leftChild:
self.rotateRight(z.parent)
self.rotateLeft(z.parent.parent)
z.parent.color = 1
z.parent.leftChild.color = 0
z= z.parent
def Visit(x):
if x!= None:
Visit(x.leftChild)
print(x)
Visit(x.rightChild)
########### MAIN PROGRAMM #################
tree = RBTree()
n = input()
p = raw_input().split()
for i in range(0,n):
node = RBNode(p[i])
tree.insert(node)
tree.insertFix(node)
#
########### MAIN PROGRAMM #################