'''
一、红黑树性质
结点必须是红色或者黑色。
根节点必须是黑色。
叶节点(NIL)必须是黑色(NIL节点无数据，是空节点)。
红色结点不能连续。
从任一节点出发到其每个叶子节点的路径，黑色节点的数量必须相等。
'''
from dataStructures.tree.biTree.bst import BST
class RBNode:
def init(self, data):
self.elem = data
self.parent = None
self.lchild = None
self.rchild = None
self.color = 'r'
class RBTree(BST):
def init(self, li):
BST.init(self, li)
def changeColor(self, p, c):
pre_p = p.parent
pre_p.lchild.color = 'b'
pre_p.rchild.color = 'b'
pre_p.color = 'r'
if pre_p == self.root:
p.parent.color = 'b'
return pre_p
def rotate_left_left(self, p, c):
#祖父结点右旋
pre_p = p.parent
rchild_p = p.rchild
p.rchild = pre_p
pre_p.parent = p
pre_p.lchild = rchild_p
if rchild_p:
rchild_p.parent = pre_p
#变色
pre_p.color = 'r'
p.color = 'b'
return p
def rotate_right_right(self, p, c):
#祖父结点左旋
pre_p = p.parent
lchild_p = p.lchild
p.lchild = pre_p
pre_p.parent = p
pre_p.rchild = lchild_p
if lchild_p:
lchild_p.parent = pre_p
#变色
pre_p.color = 'r'
p.color = 'b'
return p
def rotate_left_right(self, p, c):
#父节点左旋
pre_p = p.parent
lchild_c = c.lchild
c.lchild = p
p.parent = c
p.rchild = lchild_c
if lchild_c:
lchild_c.parent = p
c.parent = pre_p
pre_p.lchild = c
#祖父节点右旋
rchild_c = c.rchild
c.rchild = pre_p
pre_p.lchild = rchild_c
pre_p.parent = c
if rchild_c:
rchild_c.parent = pre_p
#变色
c.color = 'b'
pre_p.color = 'r'
return c
def rotate_right_left(self, p, c):
# 父节点右旋
pre_p = p.parent
rchild_c = c.rchild
c.rchild = p
p.parent = c
p.lchild = rchild_c
if rchild_c:
rchild_c.parent = p
c.parent = pre_p
pre_p.rchild = c
#祖父节点左旋
lchild_c = c.lchild
c.lchild = pre_p
pre_p.rchild = lchild_c
pre_p.parent = c
if lchild_c:
lchild_c.parent = pre_p
#变色
c.color = 'b'
pre_p.color = 'r'
return c
def insert_no_rec(self, val):
# 1. 和BST一样，插入
p = self.root
if not p: # 空树
self.root = RBNode(val)
self.root.color = 'b'
return
while True:
if val < p.elem:
if p.lchild:
p = p.lchild # node存储就是插入的结点
else: # 左孩子不存在
p.lchild = RBNode(val)
p.lchild.parent = p
node = p.lchild # node 存储的就是插入的节点
break
elif val > p.elem:
if p.rchild:
p = p.rchild
else:
p.rchild = RBNode(val)
p.rchild.parent = p
node = p.rchild
break
else: # val == p.data
return
while node.parent and node.parent != self.root:
if node.color == 'b' or node.parent.color == 'b' :
break
else:
pre_p = node.parent.parent
pre_pre_p = pre_p.parent # 祖祖节点
p = node.parent
if node.color == 'r' and p.color == 'r':
# 祖父节点左子树
if pre_p.lchild == p:
# 如果叔父节点都为红直接变色再判断
if pre_p.rchild and pre_p.rchild.color == 'r':
node = self.changeColor(node.parent, node)
continue
#父亲节点左子树
if p.lchild == node:
#判断祖父节点右子树的情况
node = self.rotate_left_left(node.parent, node)
else:
node = self.rotate_left_right(node.parent, node)
# 祖父节点右子树
elif pre_p.rchild == p:
# 如果叔父节点都为红直接变色再判断
if pre_p.lchild and pre_p.lchild.color == 'r':
node = self.changeColor(node.parent, node)
continue
if p.lchild == node:
node = self.rotate_right_left(node.parent, node)
else:
node = self.rotate_right_right(node.parent, node)
# 连接旋转后都子树
node.parent = pre_pre_p
if pre_pre_p:
if pre_p == pre_pre_p.lchild:
pre_pre_p.lchild = node
else:
pre_pre_p.rchild = node
node.parent = pre_pre_p
break
else:
self.root = node
break
def del_red_no_leaf(self, c):
if c.parent.lchild == c:
c.parent.lchild = None
else:
c.parent.rchild = None
def del_black_cur_1(self, c, p, b):
# 兄弟结点是黑色的，而且有一个同方向的子结点（可断定右节点是红色）
# 兄弟节点只有一个子节点
# c为左子树，有兄弟节点并且兄弟节点有右孩子
if c == p.lchild and b.rchild:
b.color = p.color #1、父节点颜色赋给兄弟结点
b.rchild.color = 'b' #2、将父亲节点和兄弟结点右孩子设为黑色）
p.color = 'b'
p.lchild = None #3、将被删除节点删除
b.lchild = p #4、父节点左旋
p.parent = b
p.lchild, p.rchild = None, None
return b #返回旋转后的子树的根节点
# c为左子树，有兄弟节点并且兄弟节点有左孩子
elif c == p.lchild and b.lchild:
#兄弟结点是黑色的，且有一个左节点（可以断定左节点是红色）
b.lchild.color = 'b' #1、将该左孩子设置为黑色
b.color = 'r' #2、将兄弟结点设置为红色
p.rchild = b.lchild
b.lchild.parent = p
p.rchild.rchild = b
b.parent = p.rchild
b.lchild, b.rchild = None, None
b = p.rchild
#回到情况1
b.color = p.color # 1、父节点颜色赋给兄弟结点
b.rchild.color = 'b' # 2、将父亲节点和兄弟结点右孩子设为黑色）
p.color = 'b'
p.lchild = None # 3、将被删除节点删除
b.lchild = p # 4、父节点左旋
p.parent = b
p.lchild, p.rchild = None, None
return b # 返回旋转后的子树的根节点
# c为右子树，有兄弟节点并且兄弟节点有左孩子
elif c == p.rchild and b.lchild:
b.color = p.color #1、父节点颜色赋给兄弟结点
p.color = 'b' #2、将父亲节点和兄弟结点左孩子设为黑色
b.lchild.color = 'b'
c = None #3、删除节点c
p.rchild = None
b.rchild = p #4、对父亲节点右旋转
p.parent = b
p.lchild, p.rchild = None, None
return b
# c为右子树，有兄弟节点并且兄弟结点有右孩子
else:
# 兄弟结点是黑色的，且有一个右节点（可以断定右节点是红色）
b.rchild.color = 'b' # 1、将该右孩子设置为黑色
b.color = 'r' # 2、将兄弟结点设置为红色
b_rchild = b.rchild # 3、对兄弟结点左旋转
b_rchild.lchild = b
b.parent = b_rchild
p.lchild = b_rchild
b_rchild.parent = p
b = p.lchild
b.color = p.color # 1、父节点颜色赋给兄弟结点
p.color = 'b' # 2、将父亲节点和兄弟结点左孩子设为黑色
b.lchild.color = 'b'
p.rchild = None # 删除节点c
b.rchild = p # 4、对父亲节点右旋转
p.parent = b
p.lchild, p.rchild = None, None
return b
def del_black_cur_2(self, c, p, b):
# 兄弟节点是黑色的，且有两个节点（可以断定左右节点都是红色的）
if c == p.lchild and b.color == 'b':
b.color = p.color #1、将父节点的颜色赋给兄弟节点
b.rchild.color = 'b' #2、将兄弟结点的右孩子设为黑色
p.color = 'b' #3、将父亲节点设为黑色
p.lchild = None #4、删除节点c
b_lchild = b.lchild #5、对父亲节点左旋
p.rchild = b_lchild
b_lchild.parent = p
b.lchild = p
p.parent = b
return b
# 兄弟节点是红色的，那么根据红黑树性质有它有两个黑色子节点
elif c == p.lchild and b.color == 'r':
b.color = 'b' # 1、将兄弟节点设为黑色
b.lchild.color = 'r' # 2、将兄弟结点的左孩子设为红色
p.lchild = None # 3、删除节点c
b_lchild = b.lchild # 4、对父亲节点左旋
p.rchild = b_lchild
b_lchild.parent = p
b.lchild = p
p.parent = b
return b
elif c == p.rchild and b.color == 'b':
b.color = p.color # 1、将父节点的颜色赋给兄弟节点
b.lchild.color = 'b' # 2、将兄弟结点的左孩子设为黑色
p.color = 'b' # 3、将父亲节点设为黑色
p.rchild = None # 4、删除节点c
b_rchild = b.rchild # 5、对父亲节点右旋
p.lchild = b_rchild
b_rchild.parent = p
b.rchild = p
p.parent = b
return b
else:
b.color = 'b' # 1、将兄弟节点设为黑色
b.rchild.color = 'r' # 2、将兄弟结点的右孩子设为红色
p.rchild = None # 3、删除节点c
b_rchild = b.rchild # 4、对父亲节点右旋
p.rchild = b_rchild
b_rchild.parent = p
b.rchild = p
p.parent = b
return b
def del_black_cur_0(self,c, p, b):
'''
替换节点R是黑色，无子节点，而且是其黑色父节点的左子节点，而且替换节点的兄弟节点是黑色的，且都无子节点：此时对这三个节点无论怎样变换都无法在删除R节点后让树平衡，所以此时需要向上探索保持平衡，也就是将P节点视作R节点向上平衡（所谓将P节点视作R节点也就是将不在乎P节点的左右子节点，就当做这是要被替换删除的一个树末节点，然后向上重新平衡），但并不是要删除P节点，而是通过一层层向上调整（向上调整也就是将P节点是为要被删除的节点，判断其为3,4,5,6中的哪一种情况，如果是3，4，5情况就可以直接调整平衡，但如果是情况6则继续向上一层调整）来重新让树达到平衡，达到平衡后在删除R节点
:param c:
:param p:
:param b:
:return:
'''
#兄弟节点是黑色的，而且没有子节点
#将兄弟结点设为红色，将父节点设为当前节点递归，直到根节点或遇到红色节点
if c == p.lchild: # 先删除节点
p.lchild = None
p.rchild.color = 'r' # 右孩子设为红节点
else:
p.rchild = None
p.lchild.color = 'r' # 左孩子设为红节点
c = p #找到父节点为红或者树顶的子节点
while c.parent.color != 'r' and c.parent != self.root:
c = c.parent
p = c.parent #左旋右旋操作
if p.rchild == c:
p_lchild_rchild = p.lchild.rchild
p_lchild = p.lchild
p_lchild.rchild = p
p.parent = p_lchild
p.lchild = p_lchild_rchild
p_lchild_rchild.parent = p
t = p_lchild
else:
p_rchild_lchild = p.rchild.lchild
p_rchild = p.rchild
p_rchild.lchild = p
p.parent = p_rchild
p.rchild = p_rchild_lchild
p_rchild_lchild.parent = p
t = p_rchild
return t
def delete_no_rec(self, val):
# 1、查找
c = self.query_no_rec(val)
while c:
# 2、
# A、删除的是叶子节点且该叶子节点是红色的 ---> 无需修复，因为它不会破坏红黑树的5个特性
# B、删除的是叶子节点且该叶子节点是黑色的 ---> 很明显会破坏特性5，需要修复
if not c.lchild and not c.rchild:
if c.color == 'r':
#红节点直接删除
self.del_red_no_leaf(c)
return
else:
#若最后删除的为黑色叶子结点，则必定有兄弟结点
p = c.parent #父亲结点
g = p.parent #祖父节点
before_p = p #保留p后做判断
b = p.rchild if p.lchild == c else p.lchild
# 有兄弟结点并且兄弟节点有俩个孩子
if b.color == 'b' and b.lchild and b.rchild:
p = self.del_black_cur_2(c, p, b)
break
# 有兄弟结点并且兄弟节点有一个孩子
elif b.color == 'b' and (b.lchild or b.rchild):
p = self.del_black_cur_1(c, p, b)
break
# 有兄弟结点并且兄弟节点无孩子
else:
p = self.del_black_cur_0(c, p ,b)
return
# C、删除的节点（为了便于叙述我们将其称为P）下面有一个子节点 S，对于这种情况我们通过 将P和S的值交换的方式，巧妙的将删除P变为删除S，S是叶子节点，这样C这种情况就会转 换为A, B这两种情况：
# C1： P为黑色，S为红色 ---> 对应 （1） 这种情况
# C2： P为黑色或红色，S为黑色 --- > 对应 （2） 这种情况
# 不会出现超过两层的情况，因为红黑树会自动旋转调整树的高度
elif (not c.lchild and c.rchild) or (c.lchild and not c.rchild):
while c.lchild or c.rchild:
# 与左孩子交换值
if c.lchild:
c.elem = c.lchild.elem
c = c.lchild
# 与右孩子交换值
else:
c.elem = c.rchild.elem
c = c.rchild
# D、删除的节点有两个子节点，对于这种情况，我们通过将P和它的后继节点N的值交换的方 式，将删除节点P转换为删除后继节点N，而后继节点只可能是以下两种情况：
# D1: N是叶子节点 --- > 对应情况 A 或 B
# D2: N有一个子节点 ---- > 对应情况 C
# 所以通过上面的分析我们发现，红黑树节点删除后的修复操作都可以转换为A或
# B这两种情况，而A不需要修复，所以我们只需要研究B这种情况如何修复就行了。
elif c.lchild and c.rchild:
# 找到后继结点
tmp_c = c
tmp_c = tmp_c.rchild
while tmp_c.lchild:
tmp_c = tmp_c.lchild
#交换值
c.elem = tmp_c.elem
c = tmp_c
# 连接旋转后都子树
if g:
if before_p == g.lchild:
g.lchild = p
else:
g.rchild = p
p.parent = g
else:
self.root = p
# 中序遍历
def in_order(self, root):
if root:
self.in_order(root.lchild)
print(root.elem, root.color,end='\n')
self.in_order(root.rchild)
import random
li = [random.randint(0, 10000) for i in range(20)]
print(li)
t = RBTree([10,22,55,49,33,69,44,3,1,0,5,2,15,17,90])
t.delete_no_rec(90)
print(t.root.elem,t.root.color)
print(t.root.lchild.elem,t.root.lchild.color)
print(t.root.rchild.elem,t.root.rchild.color)
print(t.root.rchild.rchild.elem,t.root.rchild.rchild.color)
print(t.root.lchild.rchild.elem,t.root.lchild.rchild.color)
print(t.root.lchild.elem,t.root.lchild.color)
t.in_order(t.root)