用python 实现红黑树算法 附上代码

答：python 实现红黑树算法的代码如下：# Python Program to Create a Binary Tree
# Representation of Red-Black Tree
# A node structure
class Node:
# Constructor which creates a new node
def __init__(self, key):
self.left = None
self.right = None
self.val = key
self.color = 1 # 1 for red, 0 for black # Class to represent Red-Black Tree
class RedBlackTree:
# Constructor which creates a nil node
def __init__(self):
self.nil = Node(0)
self.nil.color = 0
self.nil.left = None
self.nil.right = None
self.root = self.nil # Utility function that performs a
# standard right rotate
def rightRotate(self, x):
y = x.left
x.left = y.right
if y.right != self.nil:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y # Utility function that performs a
# standard left rotate
def leftRotate(self, x):
y = x.right
x.right = y.left
if y.left != self.nil:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y # Utility function that performs a
# insert fixup after inserting a node
def insertFixup(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.rightRotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.leftRotate(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self.leftRotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.rightRotate(k.parent.parent)
self.root.color = 0 # Utility function that inserts a
# node in the tree
def insert(self, k):
# Ordinary Binary Search Insertion
y = self.nil
x = self.root
while x != self.nil:
y = x
if k.val < x.val:
x = x.left
else:
x = x.right
k.parent = y
if y == self.nil:
self.root = k
elif k.val < y.val:
y.left = k
else:
y.right = k
k.left = self.nil
k.right = self.nil
k.color = 1 # new node must be red
self.insertFixup(k)