红黑树（Red-Black Tree

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，它的插入、删除和查找操作的平均时间复杂度都是 O(log n)。红黑树的高度始终保持在 O(log n) 级别，因此它是一种高效的数据结构。
红黑树的基本原理是，它的每个节点都有一个平衡因子，表示该节点的左子树和右子树的高度差。插入和删除操作会改变节点的平衡因子，因此需要通过旋转操作来重新平衡树。
使用红黑树时，需要提供以下几个方法：

1. 插入节点：将一个节点插入到红黑树中，并返回插入后的树。
2. 删除节点：将一个节点从红黑树中删除，并返回删除后的树。
3. 查找节点：在红黑树中查找某个节点。
4. 旋转操作：将一个节点旋转以重新平衡红黑树。
5. 获取平衡因子：获取一个节点的平衡因子。
6. 更新平衡因子：更新一个节点的平衡因子。
   在插入和删除节点时，需要先比较当前节点的平衡因子，如果平衡因子大于 1 或小于 -1，则需要进行旋转操作来重新平衡树。
   下面是一个简单的红黑树的实现：

class Node:
def init(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
self.balance_factor = 0
class RedBlackTree:
def init(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self.root = self._insert(self.root, key)
return self
def _insert(self, node, key):
if key < node.key:
node.left = self._insert(node.left, key)
elif key > node.key:
node.right = self._insert(node.right, key)
else:
return node
node.height = 1 + max(self._height(node.left), self._height(node.right))
balance_factor = self._get_balance_factor(node)
if balance_factor > 1:
if self._get_balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
node = self._rotate_right(node)
elif balance_factor < -1:
if self._get_balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
node = self._rotate_left(node)
return node
def delete(self, key):
if self.root:
self.root = self._delete(self.root, key)
return self
def _delete(self, node, key):
if not node:
return node
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
temp = self._find_min_value_node(node.right)
node.key = temp.key
node.right = self._delete(node.right, temp.key)
if not node:
return node
node.height = 1 + max(self._height(node.left), self._height(node.right))
balance_factor = self._get_balance_factor(node)
if balance_factor > 1:
if self._get_balance_factor(node.left) < 0:
node.left = self._rotate_left(node.left)
node = self._rotate_right(node)
elif balance_factor < -1:
if self._get_balance_factor(node.right) > 0:
node.right = self._rotate_right(node.right)
node = self._rotate_left(node)
return node
def _rot