import random
import time
import sys
sys.setrecursionlimit(10000)
class RBNode():
def __init__(self,data,left = None,right = None,parent = None,color = "R"):
self.data = data
self.left = left
self.right = right
self.parent = parent
self.color = color
def grandparent(self):
"""祖父结点"""
if self.parent is None:
return None
elif self.parent.parent is None:
return None
else:
return self.parent.parent
def uncle(self):
"""叔叔结点"""
if self.parent is None:
return None
elif self.parent.parent is None:
return None
else:
if(self.parent.parent.left == self.parent):
return self.parent.parent.right
else:
return self.parent.parent.left
def brother(self):
"""兄弟结点"""
if self.parent is None:
return None
else:
if(self.parent.left == self):
return self.parent.right
else:
return self.parent.left
class RBTree():
def __init__(self):
self.root = None
self.node = None
def search(self,key):
"""查找关键字,返回相应结点"""
node = self.root
if node is None:
return None
while node:
if(key < node.data):
node = node.left
elif(key > node.data):
node = node.right
else:
return node
return None
def insert(self,key):
"""全为红结点插入"""
if self.search(key) is not None: #如果本来在树里
return
else:
node = RBNode(key)
temp = self.root
if self.root is None:
temp = node
else:
while temp:
if(key < temp.data):
parent = temp
temp = temp.left
else:
parent = temp
temp = temp.right
node.parent = parent
if(key < parent.data):
parent.left = node
else:
parent.right = node #完成插入
self.insert_case(node)
return
def left_right(self,node):
"""左右 -> 左左"""
parent = node.parent
grandparent = node.grandprant()
node.left.parent = parent
parent.right = node.left
parent.parent = node
node.left = parent
grandparent.left = node
node.parent = grandparent
return node
def right_left(self,node):
"""右左 -> 右右"""
parent = node.parent
grandparent = node.grandprant()
node.right.parent = parent
parent.left = node.right
parent.parent = node
node.right = parent
grandparent.right = node
node.parent = grandparent
return node
def left_left(self,node):
"""左左调整"""
a = node.grandparent()
b = node.parent
a.color = "R"
b.color = "B"
if b.right:
b.right.parent = a
a.left = b.right
b.right = a
b.parent = a.parent
if b.parent:
if b.parent.data > b.data:
b.parent.left = b
else:
b.parent.right = b
b.left.parent = b
b.right.parent = b
while b.parent:
b = b.parent
return b
def right_right(self,node):
"""右右调整"""
a = node.grandparent()
b = node.parent
a.color = "R"
b.color = "B"
if b.left:
b.left.parent = a
a.right = b.left
b.left = a
b.parent = a.parent
if b.parent:
if b.parent.data > b.data:
b.parent.left = b
else:
b.parent.right = b
b.left.parent = b
b.right.parent = b
while b.parent:
b = b.parent
return b
def insert_case(self, node):
"""插入情况"""
if node.parent is None: #根节点，变黑
node.color = "B"
self.root = node
return
elif(node.parent.color == "B"): #父结点为黑，不需要改
while node.parent:
node = node.parent
self.root = node
return
elif(node.parent.color == "R" and node.uncle() != None):#父结点为红，叔父结点存在
if(node.uncle().color == "R"):
node.parent.color = "B"
node.uncle().color = "B"
node.parent.parent.color = "R"
return self.insert_case(node.parent.parent)#相当于插入祖父结点。递归
elif node.parent.right == node and node.parent.parent.left == node.parent :
node = self.left_right(node)
self.root = self.left_left(node)
return
elif node.parent.left == node and node.parent.parent.right == node.parent :
node = self.right_left(node)
self.root = self.right_right(node)
return
elif(node.uncle() is None):#与叔父为黑情况相同，父结点为红
if node.parent.right == node and node.parent.parent.left == node.parent :
node = self.left_right(node)
self.root = self.left_left(node)
return
elif node.parent.left == node and node.parent.parent.right == node.parent :
node = self.right_left(node)
self.root = self.right_right(node)
return
#父结点为红，左左情况，右右情况
if node.parent.left == node and node.parent.parent.left == node.parent :
self.root = self.left_left(node)
return
elif node.parent.right == node and node.parent.parent.right == node.parent :
self.root = self.right_right(node)
return
return
#删除
def left_rotate(self,node):
"""删除左旋操作，node为顶结点"""
parent = node.parent
right = node.right
if not right:
return
node.right = node.right.left
if node.right:
node.right.parent = node
right.left = node
node.parent = right
if not parent:
self.root = right
else:
if parent.left.data == node.data:
parent.left = right
else:
parent.right = right
right.parent = parent
def right_rotate(self,node):
"""删除的右旋操作"""
parent = node.parent
left = node.left
if not left:
return
node.left = node.left.right
if node.left:
node.leftt.parent = node
left.right = node
node.parent = left
if not parent:
self.root = left
else:
if parent.left.data == node.data:
parent.left = left
else:
parent.right = left
left.parent = parent
def change_color(self,node):
"""变色操作"""
if node.color == "R":
node.color = "B"
elif node.color == "B":
node.color = "R"
def delet_val(self,data):
"""删除"""
if self.root:
node = self.search(data)
if node:
self.delet(node)
def delet(self,node):
if node.left is None and node.right is
