1. 红黑树的概念
红黑树从平衡二叉搜索树延伸出来的一种较为复杂的数据结构，它会对树的各个节点进行着色标记（红色和黑色），相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，（插入最多需要旋转2次，删除最多需要旋转3次），整体来说性能要优于AVL树。在插入和删除操作的时候依据节点的颜色向平衡的方向调整，可以在O(logN)时间内完成查找、插入和删除。
红黑树需要满足的条件：
1. 根节点为黑色
2. 子节点可以为红色或者黑色
3. 每个叶节点(NIL)为黑色
4. 红色节点的两个子节点必须是黑色
5. 从叶子节点到根的路径，不可以同时出现两个连续的红色节点
6. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
红黑树
2. 旋转调整
因为红黑树也是一棵二叉搜索树，在插入或删除节点的时候，也需要进行旋转来调整节点的位置，红黑树旋转包好：左旋和右旋
1. 左旋
2. 右旋
3. 红黑树插入节点
1. 红黑树插入节点默认为红色，如果插入的点是黑色，那么就无需调整颜色，整棵树都是黑色，也满足红黑树的要求，没有意义
2. 变色的规则：
1. 如果插入节点的父节点是红色，而且他的叔叔节点（父节点的兄弟节点）也是红色
1. 把父节点（7）设为黑色
2.把叔叔节点（13）设为黑色
3.把祖父节点（12）设为红色
4.把指针定义到祖父节点（12）分析是否符合红黑树性质要求
2. 如果当前节点（12）为右节点，且它的父节点（5）是红色，叔叔节点（30）是黑色，不满足变颜色的需求，需要进行左旋
1. 当前节点（12）向上移动作为根节点，他的父节点（5）向左下移动，作为它的左孩子
2. 它的左孩子变成它的原来的父节点（5）的右孩子
3. 它的右孩子不变
3. 当前节点（5）为左节点，且父节点（12）是红色，叔叔节点（30）为黑色，进行右旋
1. 把父节点（12）变为黑色
2. 把祖父节点（19）变为红色
3. 把祖父节点（19）进行右旋
4. 父节点（12）的右孩子变成祖父节点（19）的左孩子
，
4. 红黑树的插入和删除实现
import random
# 节点的类型，颜色为黑色
class NullNode:
def __init__(self):
self.color = "Black"
self.parent = None
self.left = None
self.right = None
# 红黑树节点类
class RbTree:
def __init__(self, item, color):
self.item = item
self.color = color
self.parent = NullNode() # 父节点
self.left = NullNode() # 左孩子
self.right = NullNode() # 右孩子
# 格式化输出: \033[30m~\033[37m 设置字体颜色，\033[0m 关闭所有属性
def format(self):
if self.color == "Red":
return f"\033[31m{self.item}\033[0m"
else:
return f"\033[34m{self.item}\033[0m"
# 左旋函数，x为颜色冲撞的上层节点，图中节点5, rootNode为根节点
def left_rotate(self, rootNode, x):
p = x.parent # 指针节点的父节点
r = x.right # 指针节点的右孩子集合
# 判断是否存在右孩子r,不存在则无法进行左旋
if isinstance(r, NullNode):
raise Exception("can not left_rotate while right child is Null ")
# 右节点r设为父节点,即和x的父节点连接
r.parent = p
if x == p.left: # 情况1，x是它父节点的左孩子，则r为p的左孩子
p.left = r
else: # 情况2：x是它父节点的右孩子，则r为p的右孩子
p.right = r
# 右节点r的左节点变为x的右节点，即定义parent和right指向
r.left.parent = x
x.right = r.left
# x设为它原来右孩子r的左节点，这里都要注意他们的双向关系
r.left = x
x.parent = r
# 如果根节点发送变化，则t为新的根节点
if not r.parent or isinstance(r.parent, NullNode):
rootNode = r
return rootNode
# 右旋函数，x为当前颜色冲撞的上层节点的父节点，即图的节点19, rootNode为根节点
def right_rotate(self, rootNode, x):
p = x.parent
l = x.left # 左节点，即颜色冲突的上层节点，图节点12
# 左孩不存在，无法进行旋转
if isinstance(l, NullNode):
raise Exception("can not right_rotate while left child is Null ")
# 将x的左节点和x右旋，x的左节点为根节点，x为x的左节点的孩子
l.parent = p
if x == p.left: # 情况1，x是它父节点的左孩子，则l为p的左孩子
p.left = l
else:
p.right = l # 情况2：x是它父节点的右孩子，则l为p的右孩子
# 左节点l的右孩子为x的左孩子，将他们连接起来
l.right.parent = x
x.left = l.right
# 将x为他原来左孩子l的右孩子，建立连接
l.right = x
x.parent = l
if not l.parent or isinstance(l.parent, NullNode):
rootNode = l
return rootNode
# 插入节点，rootNode为根节点，item为插入元素
def insert(self, rootNode, item):
# 插入节点，初始色为红色
insertNode = RbTree(item, "Red")
y = NullNode() # y为节点的特征：黑色，且左右节点，父节点都为None
x = rootNode # x为根节点
# 当x存在，并且x不是NullNode的实例对象时，一层一层对比往下插入，知道到达最底层
while x and not isinstance(x, NullNode):
y = x
if insertNode.item < x.item: # 小于根节点则往左下走
x = x.left
else:
x = x.right # 大于根节点则往右上走
# 连接插入节点和指针节点，注意双重指向
insertNode.parent = y
# 判断节点插入的是指针节点的左边还是右边，空树的时候，直接插入
if not y or isinstance(y, NullNode):
rootNode = insertNode
# 小于的时候，插入左边
elif insertNode.item < y.item:
y.left = insertNode
# 小于的时候，插入右边
else:
y.right = insertNode
# 返回根节点，insert_fixup的结果就是返回根节点
return self.insert_fixup(rootNode, insertNode)
# 调整颜色并进行旋转调整位置
def insert_fixup(self, rootNode, insertNode):
# 当插入节点的父节点为Red时，说明两个节点连续为Red，不符合
while insertNode.parent.color == "Red":
# 当插入节点的父节点是左子树时，并且它的兄弟节点为Red时，开始进行变色
if insertNode.parent == insertNode.parent.parent.left:
uncleNodeRight = insertNode.parent.parent.right
if uncleNodeRight.color == "Red":
# 变色规则：父节点和叔叔节点变为Black，祖父节点变为Red
insertNode.parent.color = "Black"
uncleNodeRight.color = "Black"
insertNode.parent.parent.color = "Red"
insertNode = insertNode.parent.parent # 将指针更新值祖父节点处
# 当叔叔节点时Black时
else:
# 当节点插入的是右边时，右子树左旋
if insertNode == insertNode.parent.right:
insertNode = insertNode.parent # 更新一下指着，即插入元素的父节点
rootNode = self.left_rotate(rootNode, insertNode) # 父节点左旋
insertNode.parent.color = "Black" # 父节点变Black
insertNode.parent.parent.color = "Red" # 祖父节点变Red
rootNode = self.right_rotate(rootNode, insertNode.parent.parent) # 以祖父节点为指针进行右旋
# 当插入节点的父节点是右子树时，并且它的兄弟节点为Red时，开始进行变色,和左边一样
else:
uncleNodeLeft = insertNode.parent.parent.left
if uncleNodeLeft.color == "Red": # 叔叔节点
insertNode.parent.color = "Black" # 父节点
uncleNodeLeft.color = "Black" # 叔叔节点
insertNode.parent.parent.color = "Red" # 祖父节点
insertNode = insertNode.parent.parent
# 当节点插入的是左边时，左子树右旋
else:
if insertNode == insertNode.parent.left:
insertNode = insertNode.parent
rootNode = self.right_rotate(rootNode, insertNode) # 右旋
# 父节点变黑，原来的祖父节点变红，并进行旋转
insertNode.parent.color = "Black"
insertNode.parent.parent.color = "Red"
rootNode = self.left_rotate(rootNode, insertNode.parent.parent)
# 将根节点变为Black，并返回
rootNode.color = "Black"
return rootNode
# 删除节点,rootNode为根节点，item为删除的元素
def delete(self, rootNode, item):
deleteNode = NullNode() # 指针，指向删除的节点
y = NullNode()
x = rootNode # 先把根节点存起来
# 当根节点存在，就开始进行寻找元素的位置
while x and not isinstance(x, NullNode):
# 三种情况：大于指针节点往右找，小于往左找，并更新x的位置，等于说明找到了，将元素位置赋值给指针
if item < x.item:
x = x.left
elif item > x.item:
x = x.right
else:
deleteNode = x
break
if isinstance(deleteNode, NullNode):
return rootNode
if isinstance(deleteNode.left, NullNode) or isinstance(deleteNode.right, NullNode):
y = deleteNode
else:
y = self.tree_successor(deleteNode)
if not isinstance(y.left, NullNode):
x = y.left
else:
x = y.right
x.parent = y.parent
if isinstance(y.parent, NullNode):
rootNode = x
elif y == y.parent.left:
y.parent.left = x
else:
y.parent.right = x
if y != deleteNode:
deleteNode.item = y.item
if y.color == "Black":
rootNode = self.delete_fixup(t, x)
print(rootNode.item)
return rootNode
def delete_fixup(self, t, x):
while x != t and x.color == "Black":
if x == x.parent.left:
w = x.parent.right
if w.color == "Red":
w.color = "Black"
x.parent.color = "Red"
t = self.left_rotate(t, x.parent)
w = x.parent.right
if w.left.color == "Black" and w.right.color == "Black":
w.color = "Red"
x = x.parent
elif w.right.color == "Black":
w.left.color = "Black"
w.color = "Red"
t = self.right_rotate(t, w)
w = x.parent.right
else:
w.color = x.parent.color
x.parent.color = "Black"
w.right.color = "Black"
t = self.left_rotate(t, x.parent)
x = t
else:
w = x.parent.left
if w.color == "Red":
w.color = "Black"
x.parent.color = "Red"
t = self.right_rotate(t, x.parent)
w = x.parent.left
if w.right.color == "Black" and w.left.color == "Black":
w.color = "Red"
x = x.parent
elif w.left.color == "Black":
w.right.color = "Black"
w.color = "Red"
t = self.left_rotate(t, w)
w = x.parent.left
else:
w.color = x.parent.color
x.parent.color = "Black"
w.left.color = "Black"
t = self.right_rotate(t, x.parent)
x = t
x.color = "Black"
return t
def tree_successor(self, x):
y = x.right
insertNode = NullNode()
while y and not isinstance(y, NullNode):
insertNode = y
y = y.left
return insertNode
def set_parent(self, p, l, r):
p.left = l
p.right = r
l.parent = p
r.parent = p
def format_tree(self, t):
if not t or isinstance(t, NullNode):
return 0, []
left_indent, left_tree = self.format_tree(t.left)
right_indent, right_tree = self.format_tree(t.right)
tree = []
tree.append("." * left_indent + t.format() + "." * right_indent)
n = 0
while n < len(left_tree) or n < len(right_tree):
line = ""
if n < len(left_tree):
line += left_tree[n]
else:
line += " " * left_indent
line += " " * len(str(t.item))
if n < len(right_tree):
line += right_tree[n]
else:
line += " " * right_indent
tree.append(line)
n += 1
indent = left_indent + len(str(t.item)) + right_indent
return indent, tree
def print_tree(self, t):
_, tree = self.format_tree(t)
for line in tree:
print(line)
t = NullNode()
li = [i for i in range(10)]
random.shuffle(li)
for i in li:
tree = RbTree(i, "Red")
t = tree.insert(t, i)
tree.print_tree(t)
tree.delete(t,4)
tree.print_tree(t)
标签：right,parent,color,insertNode,红黑树,节点,left From： https://www.cnblogs.com/chf333/p/17048224.html