第一部分：二叉树的奥秘
1.1 二叉树基础
什么是二叉树？
二叉树是一种每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。它在数据组织、资源管理等方面有着广泛应用。
二叉树的类型
- 完全二叉树：除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地集中在左侧。
- 满二叉树：一个高度为h，且含有2^h - 1个节点的二叉树。
1.2 二叉树的遍历
想象我们有一个简单的二叉树，其结构如下：
🌳 / \ 🌿 🌾 / 🍃
这棵树的节点分布可以用emoji表示为：根节点是🌳，它的左子节点是🌿，右子节点是🌾；🌿的左子节点是🍃。
前序遍历（根左右）
- 访问根节点：🌳
- 访问左子树：
- 访问🌿
- 访问🌿的左子树：🍃
- 访问右子树：🌾
前序遍历结果：🌳 → 🌿 → 🍃 → 🌾
中序遍历（左根右）
- 访问左子树：
- 访问🌿的左子树：🍃
- 访问🌿
- 访问根节点：🌳
- 访问右子树：🌾
中序遍历结果：🍃 → 🌿 → 🌳 → 🌾
后序遍历（左右根）
- 访问左子树：
- 访问🌿的左子树：🍃
- 访问🌿
- 访问右子树：🌾
- 访问根节点：🌳
后序遍历结果：🍃 → 🌿 → 🌾 → 🌳
层序遍历（逐层从左到右）
- 第一层：🌳
- 第二层：🌿 → 🌾
- 第三层：🍃
层序遍历结果：
- 第一层：🌳
- 第二层：🌿 → 🌾
- 第三层：🍃
1.3 实战演练：构建你的第一个二叉树
让我们动手编写一个简单的二叉树实现，并进行前序遍历：
class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None def preorder_traversal(node): if node: print(node.value, end=' ') preorder_traversal(node.left) preorder_traversal(node.right) # 构建示例二叉树 root = TreeNode('🌳') root.left = TreeNode('🌿') root.right = TreeNode('🌾') root.left.left = TreeNode('🍃') # 前序遍历输出 preorder_traversal(root)
输出结果 🌳 / \ 🌿 🌾 / 🍃
第二部分：探索平衡之美——平衡树
2.1平衡树的定义与重要性
什么是平衡树？
平衡树，顾名思义，是一种内部结构平衡的树。它确保了树的高度保持在一个低水平，从而使得增加、删除、查找等操作都能在对数时间内完成。这种平衡通过确保树的每个节点的左右子树的高度差不超过特定的值来实现。
平衡树的应用场景
平衡树广泛应用于数据库索引、文件系统、网络路由等领域，几乎在任何需要快速数据检索的场合都能见到它的身影。
2.2 AVL树：平衡树的典范
AVL树的定义
AVL树是最早被发明的自平衡二叉搜索树。在AVL树中，任意节点的两个子树的高度最大差别为1，这使得AVL树几乎是完全平衡的。
AVL树的旋转操作详解
为了维持平衡，AVL树引入了旋转操作，主要有四种类型：左旋、右旋、左右旋和右左旋。
- 左旋（Right Rotation） 🔄
当一个节点的左子树比右子树矮时，我们进行左旋。 - 右旋（Left Rotation） 🔄
当一个节点的右子树比左子树矮时，我们进行右旋。 - 左右旋和右左旋 🔄
这是两步操作的组合，用于处理更复杂的不平衡情况。
2.3 实战演练：平衡树的构建与操作
现在，让我们来看看如何构建一个AVL树，并执行基本操作。
构建AVL树的步骤
- 插入节点：像普通的二叉搜索树一样插入节点。
- 检查平衡：插入后，沿着路径向上检查每个节点的平衡。
- 应用旋转：如果发现不平衡，根据不平衡的类型应用适当的旋转操作。
平衡树的插入示例代码：
class TreeNode: def __init__(self, key, height=1): self.key = key self.left = None self.right = None self.height = height class AVLTree: def insert(self, root, key): # 标准的二叉搜索树插入 if not root: return TreeNode(key) elif key < root.key: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) # 更新高度 root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) # 获取平衡因子 balance = self.getBalance(root) # 不平衡调整 # 左左 if balance > 1 and key < root.left.key: return self.rightRotate(root) # 右右 if balance < -1 and key > root.right.key: return self.leftRotate(root) # 左右 if balance > 1 and key > root.left.key: root.left = self.leftRotate(root.left) return self.rightRotate(root) # 右左 if balance < -1 and key < root.right.key: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root def leftRotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y def rightRotate(self, y): x = y.left T2 = x.right x.right = y y.left = T2 y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right)) return x def getHeight(self, root): if not root: return 0 return root.height def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right)
假设我们按顺序插入一系列的键值：9, 5, 10, 0, 6, 11, -1, 1, 2。我们将逐步展示每次插入后的树结构和必要的旋转操作。
首先，初始化AVL树并插入上述键值：
# 初始化AVL树 avl_tree = AVLTree() root = None # 插入键值 keys = [9, 5, 10, 0, 6, 11, -1, 1, 2] for key in keys: root = avl_tree.insert(root, key)
初始状态（空树）：
null
插入9：
插入5：
插入10：
插入0（无需旋转）：
插入6（无需旋转）：
插入11：
插入-1（无需旋转）：
插入1，然后进行旋转调整：
插入2，导致需要进行左右旋转（左旋在5上，然后右旋在9上）：
第三部分：红黑树——自平衡的艺术
红黑树是一种特殊的二叉搜索树，它通过一系列的规则和调整操作来保持树的平衡，确保在最坏的情况下仍能提供良好的时间复杂度。接下来，让我们一起深入探索红黑树的奥秘。
3.1 红黑树的基本原理
红黑树的定义
红黑树是每个节点都带有颜色属性的二叉搜索树，颜色或为红色或为黑色。但它不仅仅是一个普通的二叉搜索树，它通过一系列的性质来维护树的平衡。
红黑树的性质
红黑树维持平衡的关键在于五个基本性质：
- 节点是红色或黑色。
- 根节点是黑色。
- 所有叶子（NIL节点）都是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的。（即红色节点不能相邻）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质共同作用，确保了红黑树的高效性能。
3.2 红黑树的操作精讲
插入操作与调整机制
插入操作可能会破坏红黑树的性质，因此需要通过旋转和重新着色来恢复这些性质。插入操作大致可以分为以下几个步骤：
- 将新节点以红色插入，保证性质5不被破坏。
- 调整树，以恢复其他可能被破坏的性质。
现在展示一个比较难的插入示例：
初始树长这样
现在我们要在这棵树上面插入一个3的点
因为此时3和4都是红色 并且3是左节点 而3的父节点4是一个右子节点 所以要单向向右旋转（就是上图中的4和3节点顺时针旋转）变成下图这样
但是违背了红色节点不能相邻的原则 所以需要调整
就变成这样了 这样就不违反红黑树的性质了
上方的过程我们用代码实现如下
class Node: def __init__(self, value, color="RED"): self.value = value self.left = None self.right = None self.parent = None self.color = color class RedBlackTree: def __init__(self): self.TNULL = Node(value=0, color="BLACK") # TNULL代表NIL节点 self.root = self.TNULL def insert(self, key): # 新节点总是以红色插入 node = Node(key) node.left = self.TNULL node.right = self.TNULL parent = None current = self.root # 找到新节点的插入位置 while current != self.TNULL: parent = current if node.value < current.value: current = current.left else: current = current.right # 设置新节点的父节点 node.parent = parent if parent is None: # 树是空的 self.root = node elif node.value < parent.value: parent.left = node else: parent.right = node node.color = "RED" node.left = self.TNULL node.right = self.TNULL # 调整红黑树 self.fix_insert(node) def rotate_left(self, x): y = x.right x.right = y.left if y.left != self.TNULL: y.left.parent = x y.parent = x.parent if x.parent is None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def rotate_right(self, x): y = x.left x.left = y.right if y.right != self.TNULL: y.right.parent = x y.parent = x.parent if x.parent is None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def fix_insert(self, k): while k != self.root and k.parent.color == "RED": if k.parent == k.parent.parent.right: u = k.parent.parent.left # 叔叔节点 if u.color == "RED": # 情况1：叔叔节点是红色 u.color = "BLACK" k.parent.color = "BLACK" k.parent.parent.color = "RED" k = k.parent.parent else: if k == k.parent.left: # 情况2：当前节点是左孩子 k = k.parent self.rotate_right(k) # 情况3：当前节点是右孩子 k.parent.color = "BLACK" k.parent.parent.color = "RED" self.rotate_left(k.parent.parent) else: # 同上，但方向相反 u = k.parent.parent.right if u.color == "RED": u.color = "BLACK" k.parent.color = "BLACK" k.parent.parent.color = "RED" k = k.parent.parent else: if k == k.parent.right: k = k.parent self.rotate_left(k) k.parent.color = "BLACK" k.parent.parent.color = "RED" self.rotate_right(k.parent.parent) self.root.color = "BLACK"
删除操作
相信这个也是让很多小伙伴头疼的地方
删除操作是红黑树中较为复杂的一部分，因为它可能会破坏红黑树的性质。删除节点后，需要通过一系列的调整来恢复这些性质。删除操作主要分为以下几个步骤：
- 查找并删除节点：首先，我们需要找到要删除的节点。如果该节点有两个子节点，通常的做法是用其后继节点（中序遍历下的下一个节点）来代替它，然后删除后继节点。这样，问题就转化为了删除最多只有一个子节点的节点。
- 调整红黑树：如果被删除的节点或其替代节点是红色，通常不需要进一步的操作，因为红色节点的删除不会影响红黑树的黑高。但如果是黑色节点，那么我们需要进行调整来恢复红黑树的性质。
删除操作可能违反的红黑树性质包括：
- 性质2：根节点是黑色。
- 性质4：红色节点的子节点必须是黑色的。
- 性质5：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
调整过程中，我们需要处理以下几种情况：
情况1：需要删除的节点是红色
1.1如下 
删除22这种情况就不用说 直接删就好了 因为他是叶节点
但如果要删除30
首先 先二分查找找到30
找到以后 往左找 找比他小的
把这个找到的替代品复制一份 赋值到他原来的节点上，然后那个原先的25就去掉了
此时违背了红色节点不能相邻的原则 所以要调整
把22变成黑色 完成
情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色
将兄弟节点染成红色，并将父节点设置为新的当前节点，继续进行调整。
情况3：兄弟节点是黑色，且兄弟的左子节点是红色，右子节点是黑色
将兄弟节点染成红色，兄弟的左子节点染成黑色，并对兄弟节点进行右旋转，这样可以转换为情况4。
情况4：兄弟节点是黑色，且兄弟的右子节点是红色
将兄弟节点染成父节点的颜色，父节点染成黑色，兄弟的右子节点染成黑色，然后对父节点进行左旋转，最后将根节点染成黑色。
下面是一个简化的代码示例，展示了如何处理这些情况：
def fix_delete(self, x): while x != self.root and x.color == "BLACK": if x == x.parent.left: s = x.parent.right if s.color == "RED": s.color = "BLACK" x.parent.color = "RED" self.rotate_left(x.parent) s = x.parent.right if s.left.color == "BLACK" and s.right.color == "BLACK": s.color = "RED" x = x.parent else: if s.right.color == "BLACK": s.left.color = "BLACK" s.color = "RED" self.rotate_right(s) s = x.parent.right s.color = x.parent.color x.parent.color = "BLACK" s.right.color = "BLACK" self.rotate_left(x.parent) x = self.root else: # 同上，但是方向相反 # 这里省略了与上面相似的代码 pass x.color = "BLACK"
查找操作
在红黑树中，查找操作与二叉搜索树相同 其实就是二分查找
🖤 (7) / \ 🔴 (3) 🖤 (18) / \ 🔴 (10) 🔴 (22)
在这个示例中，🖤 表示黑色节点，🔴 表示红色节点。这棵树满足红黑树的性质。
现在我们来搜索值为 10 的节点。
第一步：从根节点开始搜索，比较目标值 10 和当前节点值 7，由于 10 大于 7，因此我们向右子树搜索。
🖤 (7) / \ 🔴 (3) 🖤 (18) / \ 🔴 (10) 🔴 (22) ^
第二步：我们到达节点值为 18 的节点，继续比较目标值 10 和当前节点值 18，由于 10 小于 18，因此我们向左子树搜索。
🖤 (7) / \ 🔴 (3) 🖤 (18) / \ 🔴 (10) 🔴 (22) ^
第三步：我们到达节点值为 10 的节点，发现目标值和当前节点值相等，搜索结束，找到了目标节点。
下面是实现的代码
class Node: def __init__(self, key, color='Red'): self.key = key self.color = color self.left = None self.right = None class RedBlackTree: def __init__(self): self.root = None def search(self, key): return self._search(self.root, key) def _search(self, node, key): if not node or node.key == key: return node if key < node.key: return self._search(node.left, key) return self._search(node.right, key)
遍历操作
🖤 (7) / \ 🔴 (3) 🖤 (18) / \ 🔴 (10) 🔴 (22)
中序遍历
的顺序是 3, 7, 10, 18, 22。
步骤：
- 访问节点 3
- 访问节点 7
- 访问节点 10
- 访问节点 18
- 访问节点 22
前序遍历
前序遍历按照根左右的顺序访问节点。
步骤：
- 访问节点 7
- 访问节点 3
- 访问节点 18
- 访问节点 10
- 访问节点 22
后序遍历
后序遍历按照左右根的顺序访问节点。
步骤：
- 访问节点 3
- 访问节点 10
- 访问节点 22
- 访问节点 18
- 访问节点 7
