class Node: def __init__(this,key): this.key=key this.color=None this.left=None this.right=None this.parent=None class RedBlackTree: def __init__(this): this.root=None def Left_Rotate(this,x): y=x.right x.right=y.left y.left.parent=x y.parent=x.parent if x.parent==None: this.root=y elif x==x.parent.left: x.parent.left=y else: x.parent.right=y y.left=x x.parent=y def Right_Rotate(this,y): x=y.left y.left=x.right x.right.parent=y x.parent=y.parent if y.parent==None: this.root=x elif y==y.parent.left: y.parent.left=x else: y.parent.right=x x.right=y y.parent=x def Preorder(this,x): if x!=None: print x.key print x.color this.Preorder(x.left) this.Preorder(x.right) def Insert(this,key): z=Node(key) y=None x=this.root while x!=None: y=x if z.key