红黑树增删查python实现

酥酥酥酥苏 2020-11-14 16:22:35
Python 实现 博客园 增删


'''
一、红黑树性质
结点必须是红色或者黑色。
根节点必须是黑色。
叶节点(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)
t.in_order(t.root)
# print(t.root.elem)
版权声明
本文为[酥酥酥酥苏]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/szq95716/p/13973532.html

  1. 利用Python爬虫获取招聘网站职位信息
  2. Using Python crawler to obtain job information of recruitment website
  3. Several highly rated Python libraries arrow, jsonpath, psutil and tenacity are recommended
  4. Python装饰器
  5. Python实现LDAP认证
  6. Python decorator
  7. Implementing LDAP authentication with Python
  8. Vscode configures Python development environment!
  9. In Python, how dare you say you can't log module? ️
  10. 我收藏的有关Python的电子书和资料
  11. python 中 lambda的一些tips
  12. python中字典的一些tips
  13. python 用生成器生成斐波那契数列
  14. python脚本转pyc踩了个坑。。。
  15. My collection of e-books and materials about Python
  16. Some tips of lambda in Python
  17. Some tips of dictionary in Python
  18. Using Python generator to generate Fibonacci sequence
  19. The conversion of Python script to PyC stepped on a pit...
  20. Python游戏开发,pygame模块,Python实现扫雷小游戏
  21. Python game development, pyGame module, python implementation of minesweeping games
  22. Python实用工具,email模块,Python实现邮件远程控制自己电脑
  23. Python utility, email module, python realizes mail remote control of its own computer
  24. 毫无头绪的自学Python,你可能连门槛都摸不到!【最佳学习路线】
  25. Python读取二进制文件代码方法解析
  26. Python字典的实现原理
  27. Without a clue, you may not even touch the threshold【 Best learning route]
  28. Parsing method of Python reading binary file code
  29. Implementation principle of Python dictionary
  30. You must know the function of pandas to parse JSON data - JSON_ normalize()
  31. Python实用案例,私人定制,Python自动化生成爱豆专属2021日历
  32. Python practical case, private customization, python automatic generation of Adu exclusive 2021 calendar
  33. 《Python实例》震惊了,用Python这么简单实现了聊天系统的脏话,广告检测
  34. "Python instance" was shocked and realized the dirty words and advertisement detection of the chat system in Python
  35. Convolutional neural network processing sequence for Python deep learning
  36. Python data structure and algorithm (1) -- enum type enum
  37. 超全大厂算法岗百问百答(推荐系统/机器学习/深度学习/C++/Spark/python)
  38. 【Python进阶】你真的明白NumPy中的ndarray吗?
  39. All questions and answers for algorithm posts of super large factories (recommended system / machine learning / deep learning / C + + / spark / Python)
  40. [advanced Python] do you really understand ndarray in numpy?
  41. 【Python进阶】Python进阶专栏栏主自述:不忘初心,砥砺前行
  42. [advanced Python] Python advanced column main readme: never forget the original intention and forge ahead
  43. python垃圾回收和缓存管理
  44. java调用Python程序
  45. java调用Python程序
  46. Python常用函数有哪些?Python基础入门课程
  47. Python garbage collection and cache management
  48. Java calling Python program
  49. Java calling Python program
  50. What functions are commonly used in Python? Introduction to Python Basics
  51. Python basic knowledge
  52. Anaconda5.2 安装 Python 库(MySQLdb)的方法
  53. Python实现对脑电数据情绪分析
  54. Anaconda 5.2 method of installing Python Library (mysqldb)
  55. Python implements emotion analysis of EEG data
  56. Master some advanced usage of Python in 30 seconds, which makes others envy it
  57. python爬取百度图片并对图片做一系列处理
  58. Python crawls Baidu pictures and does a series of processing on them
  59. python链接mysql数据库
  60. Python link MySQL database