当前位置： 首页 > news >正文

python实现--平衡二叉树和红黑树

news 2025/2/8 18:14:26

平衡二叉树（AVL树）

1. 定义

AVL树是一种自平衡二叉搜索树，其每个节点的左右子树高度差（平衡因子）绝对值不超过1。当插入或删除操作导致失衡时，通过旋转操作恢复平衡。

2. 核心操作与旋转类型

当平衡因子绝对值超过1时，需通过以下旋转调整：

失衡情况旋转操作应用场景
右子树过高左旋插入到右子树的右子树（RR）
左子树过高右旋插入到左子树的左子树（LL）
左子树的右子树过高左右旋插入到左子树的右子树（LR）
右子树的左子树过高右左旋插入到右子树的左子树（RL）
3. 旋转操作详解与图示
3.1 左旋（Left Rotation）

场景：节点A的右子树高度比左子树高2，且右子节点B的右子树更高（RR失衡）。

       A (平衡因子=-2)\B (平衡因子=-1)\C

步骤：

  1. 将B提升为新根节点。
  2. A成为B的左子节点。
  3. B原来的左子树T2成为A的右子树。
       B (新根)/ \A   C\T2
3.2 右旋（Right Rotation）

场景：节点A的左子树高度比右子树高2，且左子节点B的左子树更高（LL失衡）。

       A (平衡因子=2)/B (平衡因子=1)/C

步骤：

  1. 将B提升为新根节点。
  2. A成为B的右子节点。
  3. B原来的右子树T2成为A的左子树。
       B (新根)/ \C   A/T2
3.3 左右旋（Left-Right Rotation）

场景：节点A的左子树B的右子树更高（LR失衡）。

       A (平衡因子=2)/B (平衡因子=-1)\C

步骤：

  1. 先对B左旋，将C提升为B的位置。
  2. 再对A右旋，将C提升为根节点。
Step 1: 左旋BA/C/BStep 2: 右旋AC/ \B   A
3.4 右左旋（Right-Left Rotation）

场景：节点A的右子树B的左子树更高（RL失衡）。

       A (平衡因子=-2)\B (平衡因子=1)/C

步骤：

  1. 先对B右旋，将C提升为B的位置。
  2. 再对A左旋，将C提升为根节点。
Step 1: 右旋BA\C\BStep 2: 左旋AC/ \A   B
4. Python实现AVL树
class AVLNode:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneself.height = 1  # 节点高度class AVLTree:def insert(self, root, key):# 1. 标准BST插入if not root:return AVLNode(key)elif key < root.key:root.left = self.insert(root.left, key)else:root.right = self.insert(root.right, key)# 2. 更新节点高度root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))# 3. 计算平衡因子balance = self.get_balance(root)# 4. 根据失衡类型旋转# 左左失衡 → 右旋if balance > 1 and key < root.left.key:return self.right_rotate(root)# 右右失衡 → 左旋if balance < -1 and key > root.right.key:return self.left_rotate(root)# 左右失衡 → 先左旋后右旋if balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left)return self.right_rotate(root)# 右左失衡 → 先右旋后左旋if balance < -1 and key < root.right.key:root.right = self.right_rotate(root.right)return self.left_rotate(root)return rootdef delete(self, root, key):# 1. 标准BST删除if not root:return rootif key < root.key:root.left = self.delete(root.left, key)elif key > root.key:root.right = self.delete(root.right, key)else:if root.left is None:return root.rightelif root.right is None:return root.left# 找到右子树的最小节点替换temp = self.get_min_node(root.right)root.key = temp.keyroot.right = self.delete(root.right, temp.key)# 删除后若树为空直接返回if root is None:return root# 2. 更新高度root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))# 3. 检查平衡balance = self.get_balance(root)# 左左失衡 → 右旋if balance > 1 and self.get_balance(root.left) >= 0:return self.right_rotate(root)# 左右失衡 → 先左旋后右旋if balance > 1 and self.get_balance(root.left) < 0:root.left = self.left_rotate(root.left)return self.right_rotate(root)# 右右失衡 → 左旋if balance < -1 and self.get_balance(root.right) <= 0:return self.left_rotate(root)# 右左失衡 → 先右旋后左旋if balance < -1 and self.get_balance(root.right) > 0:root.right = self.right_rotate(root.right)return self.left_rotate(root)return rootdef left_rotate(self, z):y = z.rightT2 = y.left# 旋转y.left = zz.right = T2# 更新高度z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return y  # 新根节点def right_rotate(self, z):y = z.leftT3 = y.right# 旋转y.right = zz.left = T3# 更新高度z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return y  # 新根节点def get_height(self, root):if not root:return 0return root.heightdef get_balance(self, root):if not root:return 0return self.get_height(root.left) - self.get_height(root.right)def get_min_node(self, root):current = rootwhile current.left:current = current.leftreturn currentdef pre_order(self, root):if root:print(f"{root.key} ", end="")self.pre_order(root.left)self.pre_order(root.right)# 示例
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:root = avl.insert(root, key)print("前序遍历:", end=" ")
avl.pre_order(root)  # 30 20 10 25 40 50
5. 操作流程示例**

插入序列 [10, 20, 30, 40, 50, 25]：

  1. 插入 10 → 树平衡。
  2. 插入 20 → 平衡因子为 -1，无需旋转。
  3. 插入 30 → 节点 10 的平衡因子为 -2，触发左旋。
    10 (失衡)        20\             /  \20    →    10    30\30
  4. 插入 40 → 节点 20 的平衡因子为 -2，触发左旋。
      20              30/  \            /  \
10   30    →   20    40\40
  5. 插入 50 → 节点 30 的平衡因子为 -2，触发左旋。
  6. 插入 25 → 触发左右旋：
         30                 30               25/  \               /  \             /  \20   40    →       20   40   →     20    30/ \                / \             /     /  \
10  25             10  25          10    25    40
6. 总结
  • 左旋：修复右子树过高，时间复杂度 (O(1))。
  • 右旋：修复左子树过高，时间复杂度 (O(1))。
  • 左右旋与右左旋：处理子树内部的不平衡，需两次旋转。
  • 平衡维护：插入和删除操作后，需递归向上调整平衡因子。

红黑树详解

红黑树是一种自平衡的二叉搜索树，通过在节点上增加一个颜色属性（红色或黑色）来维护树的平衡。它广泛应用于关联容器（如 C++ 的 std::map 和 Java 的 TreeMap）中，因为它在插入、删除和查找操作中都能保持较好的性能。

1. 红黑树的性质

红黑树满足以下性质：

  1. 节点颜色：每个节点是红色或黑色。
  2. 根节点：根节点是黑色。
  3. 叶子节点：所有叶子节点（NIL 节点）是黑色。
  4. 红色节点规则：如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）。
  5. 黑色高度：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些性质确保了红黑树的关键特性：从根节点到叶子节点的最长路径不超过最短路径的两倍。

2. 红黑树的操作

红黑树的核心操作包括插入、删除和查找。插入和删除操作可能会破坏红黑树的性质，因此需要通过旋转和重新着色来恢复平衡。

2.1 插入操作

插入新节点时，默认将其颜色设置为红色，然后通过以下步骤调整树的结构：

  1. 标准二叉搜索树插入：将新节点插入到合适的位置。
  2. 调整颜色和结构：
    • 如果新节点的父节点是黑色，直接插入。
    • 如果新节点的父节点是红色，则根据叔节点的颜色进行调整：
      • 叔节点为红色：重新着色（父节点和叔节点变为黑色，祖父节点变为红色），然后递归检查祖父节点。
      • 叔节点为黑色：通过旋转和重新着色恢复平衡。

插入示例：

插入 10 → 树为空，直接插入为根节点（黑色）。
插入 20 → 插入为 10 的右子节点（红色）。
插入 30 → 插入为 20 的右子节点（红色），触发旋转和重新着色。
2.2 删除操作

删除节点时，可能会破坏红黑树的性质，因此需要通过以下步骤调整：

  1. 标准二叉搜索树删除：找到要删除的节点，并用其前驱或后继节点替换。
  2. 调整颜色和结构：
    • 如果删除的节点是红色，直接删除。
    • 如果删除的节点是黑色，则需要通过旋转和重新着色恢复平衡。

删除示例：

删除 20 → 用 10 替换 20，然后调整颜色和结构。
2.3 查找操作

红黑树的查找操作与普通二叉搜索树相同，时间复杂度为 (O(\log n))。

3. 红黑树的旋转

红黑树通过旋转操作来调整树的结构，分为左旋和右旋。

3.1 左旋

场景：当节点的右子树过高时，执行左旋。

操作步骤：

  1. 将节点 A 的右子节点 B 提升为新的父节点。
  2. 节点 A 成为 B 的左子节点。
  3. B 原来的左子节点变为 A 的右子节点。

图示：

      A (失衡节点)               B\                       / \B          →         A   C\C
3.2 右旋

场景：当节点的左子树过高时，执行右旋。

操作步骤：

  1. 将节点 A 的左子节点 B 提升为新的父节点。
  2. 节点 A 成为 B 的右子节点。
  3. B 原来的右子节点变为 A 的左子节点。

图示：

        A (失衡节点)           B/                     / \B          →         C   A/C

4. Python 实现红黑树

class Node:def __init__(self, value, color="red"):self.value = valueself.color = colorself.left = Noneself.right = Noneself.parent = Noneclass RedBlackTree:def __init__(self):self.NIL = Node(None, "black")  # 叶子节点self.root = self.NILdef insert(self, value):new_node = Node(value)new_node.left = self.NILnew_node.right = self.NILself._insert_recursive(self.root, new_node)self._fix_insert(new_node)def _insert_recursive(self, root, new_node):if root == self.NIL:self.root = new_nodenew_node.color = "black"returnif new_node.value < root.value:if root.left == self.NIL:root.left = new_nodenew_node.parent = rootelse:self._insert_recursive(root.left, new_node)else:if root.right == self.NIL:root.right = new_nodenew_node.parent = rootelse:self._insert_recursive(root.right, new_node)def _fix_insert(self, node):while node.parent.color == "red":if node.parent == node.parent.parent.left:uncle = node.parent.parent.rightif uncle.color == "red":node.parent.color = "black"uncle.color = "black"node.parent.parent.color = "red"node = node.parent.parentelse:if node == node.parent.right:node = node.parentself._left_rotate(node)node.parent.color = "black"node.parent.parent.color = "red"self._right_rotate(node.parent.parent)else:uncle = node.parent.parent.leftif uncle.color == "red":node.parent.color = "black"uncle.color = "black"node.parent.parent.color = "red"node = node.parent.parentelse:if node == node.parent.left:node = node.parentself._right_rotate(node)node.parent.color = "black"node.parent.parent.color = "red"self._left_rotate(node.parent.parent)self.root.color = "black"def _left_rotate(self, x):y = x.rightx.right = y.leftif y.left != self.NIL:y.left.parent = xy.parent = x.parentif x.parent == self.NIL:self.root = yelif x == x.parent.left:x.parent.left = yelse:x.parent.right = yy.left = xx.parent = ydef _right_rotate(self, x):y = x.leftx.left = y.rightif y.right != self.NIL:y.right.parent = xy.parent = x.parentif x.parent == self.NIL:self.root = yelif x == x.parent.right:x.parent.right = yelse:x.parent.left = yy.right = xx.parent = ydef inorder_traversal(self):result = []self._inorder(self.root, result)return resultdef _inorder(self, node, result):if node != self.NIL:self._inorder(node.left, result)result.append((node.value, node.color))self._inorder(node.right, result)# 测试代码
rbt = RedBlackTree()
values = [10, 20, 30, 15, 25, 5]
for v in values:rbt.insert(v)
print("中序遍历:", rbt.inorder_traversal())

5. 红黑树与 AVL 树的对比

特性红黑树AVL 树
平衡性近似平衡严格平衡
插入/删除性能较快（旋转次数较少）较慢（旋转次数较多）
查找性能稍慢（树较高）较快（树较矮）
应用场景关联容器（如 std::map）需要频繁查找的场景

6. 总结

  • 红黑树通过颜色标记和旋转操作维护平衡，适合需要频繁插入和删除的场景。
  • 插入和删除操作通过旋转和重新着色恢复平衡。
  • 查找操作的时间复杂度为 (O(\log n))。
  • 红黑树在工程中应用广泛，是许多编程语言标准库的核心数据结构之一。

http://www.mrgr.cn/news/89877.html

相关文章：

  • 探索从传统检索增强生成（RAG）到缓存增强生成（CAG）的转变
  • Linux特权组全解析：识别GID带来的权限提升风险
  • Axure设计教程：动态排名图（中继器实现）
  • 前端导出pdf，所见即所得
  • openmv运行时突然中断并且没断联只是跟复位了一样
  • 群晖Alist套件无法挂载到群晖webdav，报错【连接被服务器拒绝】
  • 大数据数仓实战项目（离线数仓+实时数仓）3
  • vscode卡住---回退版本解决
  • 快速上手Vim的使用
  • 02DevOps基础环境准备
  • Excel 融合 deepseek
  • 深入Linux系列之进程地址空间
  • 基于机器学习时序库pmdarima实现时序预测
  • NetCore Consul动态伸缩+Ocelot 网关 缓存 自定义缓存 + 限流、熔断、超时 等服务治理 + ids4鉴权
  • SQL Server 数据库迁移到 MySQL 的完整指南
  • 在 Navicat 17 中扩展 PostgreSQL 数据类型 | 复合类型
  • openAI官方prompt技巧（一）
  • ubuntu 本地部署deepseek r1 蒸馏模型
  • AlwaysOn 可用性组副本所在服务器以及该副本上数据库的各项状态信息
  • .net的一些知识点6
  • C++效率掌握之STL库：string函数全解
  • 【Unity2D 2022：UI】创建滚动视图
  • DeepSeek：探索人工智能的新边界
  • 【csp/信奥赛C++语法学习如何入门？】
  • 【DeepSeek论文精读】2. DeepSeek LLM：以长期主义扩展开源语言模型
  • 循环神经网络