#coding:utf8

#author:HaxtraZ

#description:红黑树，python实现

RED = 'red'

BLACK = 'black'

class RBT:

def __init__(self):

self.items = []

self.root = None

def LEFT_ROTATE(self, x):

# x是一个RBTnode

y = x.right

if y is None:

# 右节点为空，不旋转

return

else:

beta = y.left

x.right = beta

if beta is not None:

beta.parent = x

p = x.parent

y.parent = p

if p is None:

# x原来是root

self.root = y

elif x == p.left:

p.left = y

else:

p.right = y

y.left = x

x.parent = y

def RIGHT_ROTATE(self, y):

# y是一个节点

x = y.right

if x is None:

# 右节点为空，不旋转

return

else:

beta = x.right

y.left = beta

if beta is not None:

beta.parent = y

p = y.parent

x.parent = p

if p is None:

# y原来是root

self.root = x

elif y == p.left:

p.left = x

else:

p.right = x

x.right = y

y.parent = x

def INSERT(self, val):

z = RBTnode(val)

y = None

x = self.root

while x is not None:

y = x

if z.val < x.val:

x = x.left

else:

x = x.right

z.PAINT(RED)

z.parent = y

if y is None:

# 插入z之前为空的RBT

self.INSERT_FIXUP(z)

elif y.color == RED:

# z的父节点y为红色，需要fixup。

# 如果z的父节点y为黑色，则不用调整

if z.val < y.val:

y.left = z

else:

y.right = z

self.INSERT_FIXUP(z)

def INSERT_FIXUP(self, z):

# case 1:z为root节点

if self.root == None:

z.PAINT(BLACK)

self.root = z

return

# case 2:z的父节点为黑色

if self.parent.color == BLACK:

# 包括了z处于第二层的情况

return

# 下面的几种情况，都是z.parent.color == RED:

# 节点y为z的uncle

p = z.parent

if p == p.parent.left:

y = p.parent.right

else:

y = p.parent.left

g = p.parent # g为x的grandpa

# case 3-0:z没有叔叔。即：y为NIL节点

# 注意，此时z的父节点一定是RED

if y is None:

if z == p.left:

# 3-0-0:z为右儿子，则把p左旋

# 转化为3-0-1或3-0-2的情况

self.LEFT_ROTATE(p)

p, z = z, p

g.PAINT(RED)

p.PAINT(BLACK)

if g.left == p:

# 3-0-1:p为g的左儿子

self.RIGHT_ROTATE(g)

else:

# 3-0-2:p为g的右儿子

self.LEFT_ROTATE(g)

# case 3-1:z有黑叔

elif y.color == BLACK:

if p.right == z:

# 3-1-0:z为右儿子,则左旋p

# 转化为3-1-1或3-1-2

self.LEFT_ROTATE(p)

p, z = z, p

p.PAINT(BLACK)

g.PAINT(RED)

if p == g.left:

# 3-1-1:p为g的左儿子，则右旋g

self.RIGHT_ROTATE(g)

else:

# 3-1-2:p为g的右儿子，则左旋g

self.LEFT_ROTATE(g)

# case 3-2:z有红叔

# 则涂黑父和叔，涂红爷，g作为新的z，递归调用

else:

y.PAINT(BLACK)

p.PAINT(BLACK)

g.PAINT(RED)

self.INSERT_FIXUP(g)

def DELETE(self, val):

curNode = self.root

while curNode is not None:

if val < curNode.val:

curNode = curNode.left

elif val > curNode.val:

curNode = curNode.right

else:

# 找到了值为val的元素,正式开始删除

if curNode.left is None and curNode.right is None:

# case1:curNode为叶子节点：直接删除即可

if curNode == self.root:

self.root = None

else:

p = curNode.parent

if curNode == p.left:

p.left = None

else:

p.right = None

elif curNode.left is not None and curNode.right is not None:

sucNode = self.SUCCESOR(curNode)

curNode.val, sucNode.val = sucNode.val, curNode.val

self.DELETE(sucNode.val)

else:

p = curNode.parent

if curNode.left is None:

x = curNode.right

else:

x = curNode.left

if curNode == p.left:

p.left = x

else:

p.right = x

x.parent = p

if curNode.color == BLACK:

self.DELETE_FIXUP(x)

curNode = None

return False

def FIND(self, val):

class RBTnode:

'''红黑树的节点类型'''

def __init__(self, val):

self.val = val

self.left = None

self.right = None

self.parent = None

del PAINT(self, color):

self.color = colro