Implementation of adding, deleting and querying red and black trees in Python

Crispy, crispy, crispy 2020-11-14 16:22:35
implementation adding deleting querying red


'''
One 、 The nature of the mangrove
Nodes must be red or black .
The root node must be black .
Leaf nodes (NIL) It has to be black (NIL Node has no data , It's an empty node ).
Red nodes can't be continuous .
The path from any node to each leaf node , The number of black nodes must be equal .
'''
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):
# Grandfather node right-handed
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
# Color change
pre_p.color = 'r'
p.color = 'b'
return p
def rotate_right_right(self, p, c):
# Grandfather node left rotation
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
# Color change
pre_p.color = 'r'
p.color = 'b'
return p
def rotate_left_right(self, p, c):
# The parent node is left-handed
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
# Grandfather node right
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
# Color change
c.color = 'b'
pre_p.color = 'r'
return c
def rotate_right_left(self, p, c):
# The parent node is right-handed
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
# Grandfather node left rotation
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
# Color change
c.color = 'b'
pre_p.color = 'r'
return c
def insert_no_rec(self, val):
# 1. and BST equally , Insert
p = self.root
if not p: # Empty tree
self.root = RBNode(val)
self.root.color = 'b'
return
while True:
if val < p.elem:
if p.lchild:
p = p.lchild # node Storage is the inserted node
else: # The left child doesn't exist
p.lchild = RBNode(val)
p.lchild.parent = p
node = p.lchild # node What is stored is the inserted 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 # Ancestor node
p = node.parent
if node.color == 'r' and p.color == 'r':
# Grandfather node left sub tree
if pre_p.lchild == p:
# If the uncle nodes are all red, then judge if they change color directly
if pre_p.rchild and pre_p.rchild.color == 'r':
node = self.changeColor(node.parent, node)
continue
# Father node left child tree
if p.lchild == node:
# Judge the situation of the right subtree of grandfather node
node = self.rotate_left_left(node.parent, node)
else:
node = self.rotate_left_right(node.parent, node)
# Grandfather node right subtree
elif pre_p.rchild == p:
# If the uncle nodes are all red, then judge if they change color directly
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)
# After the connection is rotated, both subtrees
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):
# Brother nodes are black , And there is a child node in the same direction ( It can be concluded that the right node is red )
# The sibling node has only one child node
# c For the left subtree , There's a sibling node and the sibling node has a right child
if c == p.lchild and b.rchild:
b.color = p.color #1、 The parent node color is assigned to the sibling node
b.rchild.color = 'b' #2、 Set the right child of father node and brother node to black )
p.color = 'b'
p.lchild = None #3、 Will be deleted node delete
b.lchild = p #4、 The parent node is left-handed
p.parent = b
p.lchild, p.rchild = None, None
return b # Returns the root node of the subtree after rotation
# c For the left subtree , There's a sibling node and the sibling node has a left child
elif c == p.lchild and b.lchild:
# Brother nodes are black , And there's a left node ( It can be concluded that the left node is red )
b.lchild.color = 'b' #1、 Set the left child to black
b.color = 'r' #2、 Set the sibling node to red
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
# Back to the situation 1
b.color = p.color # 1、 The parent node color is assigned to the sibling node
b.rchild.color = 'b' # 2、 Set the right child of father node and brother node to black )
p.color = 'b'
p.lchild = None # 3、 Will be deleted node delete
b.lchild = p # 4、 The parent node is left-handed
p.parent = b
p.lchild, p.rchild = None, None
return b # Returns the root node of the subtree after rotation
# c For the right subtree , There's a sibling node and the sibling node has a left child
elif c == p.rchild and b.lchild:
b.color = p.color #1、 The parent node color is assigned to the sibling node
p.color = 'b' #2、 Set the left child of father node and brother node to black
b.lchild.color = 'b'
c = None #3、 Delete node c
p.rchild = None
b.rchild = p #4、 Rotate the parent node right
p.parent = b
p.lchild, p.rchild = None, None
return b
# c For the right subtree , There are sibling nodes and sibling nodes have right children
else:
# Brother nodes are black , And there's a right node ( It can be concluded that the right node is red )
b.rchild.color = 'b' # 1、 Set the right child to black
b.color = 'r' # 2、 Set the sibling node to red
b_rchild = b.rchild # 3、 Left rotation of the sibling node
b_rchild.lchild = b
b.parent = b_rchild
p.lchild = b_rchild
b_rchild.parent = p
b = p.lchild
b.color = p.color # 1、 The parent node color is assigned to the sibling node
p.color = 'b' # 2、 Set the left child of father node and brother node to black
b.lchild.color = 'b'
p.rchild = None # Delete node c
b.rchild = p # 4、 Rotate the parent node right
p.parent = b
p.lchild, p.rchild = None, None
return b
def del_black_cur_2(self, c, p, b):
# Brother nodes are black , And there are two nodes ( It can be concluded that the left and right nodes are red )
if c == p.lchild and b.color == 'b':
b.color = p.color #1、 Assign color to the parent node
b.rchild.color = 'b' #2、 Set the right child of the sibling node to black
p.color = 'b' #3、 Set the parent node to black
p.lchild = None #4、 Delete node c
b_lchild = b.lchild #5、 Turn left on the father node
p.rchild = b_lchild
b_lchild.parent = p
b.lchild = p
p.parent = b
return b
# Brother nodes are red , So according to the nature of the red black tree, it has two black child nodes
elif c == p.lchild and b.color == 'r':
b.color = 'b' # 1、 Set the sibling node to black
b.lchild.color = 'r' # 2、 Set the left child of the sibling node to red
p.lchild = None # 3、 Delete node c
b_lchild = b.lchild # 4、 Turn left on the father node
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、 Assign color to the parent node
b.lchild.color = 'b' # 2、 Set the left child of the sibling node to black
p.color = 'b' # 3、 Set the parent node to black
p.rchild = None # 4、 Delete node c
b_rchild = b.rchild # 5、 Turn right on the father node
p.lchild = b_rchild
b_rchild.parent = p
b.rchild = p
p.parent = b
return b
else:
b.color = 'b' # 1、 Set the sibling node to black
b.rchild.color = 'r' # 2、 Set the right child of the sibling node to red
p.rchild = None # 3、 Delete node c
b_rchild = b.rchild # 4、 Turn right on the father node
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):
'''
Replacement node R It's black , No child nodes , And it's the left child of its black parent , And the siblings of the replacement node are black , And there are no child nodes : At this time, no matter how to transform these three nodes, they can not be deleted R Let the tree balance after the node , So it's time to explore up and keep balance , Also is to P Nodes are treated as R Node up balance ( The so-called will P Nodes are treated as R Nodes, that is, will not care about P The left and right children of a node , Think of it as a tree end node to be replaced and deleted , And then rebalance up ), But it's not about deleting P node , It's through layers of upward adjustment ( Upward adjustment means that you will P The node is for the node to be deleted , Judge it as 3,4,5,6 In which case , If it is 3,4,5 The situation can adjust the balance directly , But if it's the case 6 Then continue to adjust up to the next level ) To rebalance the tree , When the balance is reached, delete R node
:param c:
:param p:
:param b:
:return:
'''
# Brother nodes are black , And there are no child nodes
# Set the sibling node to red , Set the parent node as the current node recursively , Until the root node or meets the red node
if c == p.lchild: # Delete the node first
p.lchild = None
p.rchild.color = 'r' # Set the right child as the red node
else:
p.rchild = None
p.lchild.color = 'r' # Set the left child as the red node
c = p # Find the child node whose parent is red or at the top of the tree
while c.parent.color != 'r' and c.parent != self.root:
c = c.parent
p = c.parent # Turn left and right
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、 lookup
c = self.query_no_rec(val)
while c:
# 2、
# A、 The leaf node is deleted and the leaf node is red ---> There is no need to repair , Because it won't destroy the red and black trees 5 A feature
# B、 The leaf node is deleted and the leaf node is black ---> It's obvious that it's going to destroy features 5, Need repair
if not c.lchild and not c.rchild:
if c.color == 'r':
# The red node is deleted directly
self.del_red_no_leaf(c)
return
else:
# If the last deleted is a black leaf node , Then there must be brothers
p = c.parent # Father node
g = p.parent # Grandfather node
before_p = p # Retain p Then make a judgment
b = p.rchild if p.lchild == c else p.lchild
# There's a sibling node and the sibling node has two children
if b.color == 'b' and b.lchild and b.rchild:
p = self.del_black_cur_2(c, p, b)
break
# There is a sibling node and the sibling node has a child
elif b.color == 'b' and (b.lchild or b.rchild):
p = self.del_black_cur_1(c, p, b)
break
# There are sibling nodes and sibling nodes have no children
else:
p = self.del_black_cur_0(c, p ,b)
return
# C、 Deleted nodes ( For the sake of narration, we call it P) There is a child node below S, In this case, we use take P and S How to exchange the values of , Clever will delete P Change to delete S,S It's a leaf node , such C This will turn Replace with A, B In both cases :
# C1: P For the black ,S In red ---> Corresponding (1) This situation
# C2: P For black or red ,S For the black --- > Corresponding (2) This situation
# There won't be more than two layers , Because the red black tree will automatically rotate to adjust the height of the tree
elif (not c.lchild and c.rchild) or (c.lchild and not c.rchild):
while c.lchild or c.rchild:
# Exchange value with left child
if c.lchild:
c.elem = c.lchild.elem
c = c.lchild
# Exchange values with the right child
else:
c.elem = c.rchild.elem
c = c.rchild
# D、 The deleted node has two child nodes , In this case , We pass the will P And its successor nodes N The value of the exchange type , The node will be deleted P Convert to delete successor nodes N, The subsequent node can only be in the following two cases :
# D1: N It's a leaf node --- > Corresponding situation A or B
# D2: N There is a child node ---- > Corresponding situation C
# So through the above analysis, we find that , The repair operation after deleting the red black tree node can be converted to A or
# B In both cases , and A There's no need to fix , So we just need to study B How to repair this situation is OK .
elif c.lchild and c.rchild:
# Find the successor node
tmp_c = c
tmp_c = tmp_c.rchild
while tmp_c.lchild:
tmp_c = tmp_c.lchild
# Exchange value
c.elem = tmp_c.elem
c = tmp_c
# After the connection is rotated, both subtrees
if g:
if before_p == g.lchild:
g.lchild = p
else:
g.rchild = p
p.parent = g
else:
self.root = p
# In the sequence traversal
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)
版权声明
本文为[Crispy, crispy, crispy]所创,转载请带上原文链接,感谢

  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