目录

1. 二叉搜索树（BST）的退化

知识点

二叉搜索树（Binary Search Tree，BST）是一种二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。 然而，当插入的数据有序时，BST 会退化为链表，此时其查找、插入和删除操作的时间复杂度会从 $O(\log n)$ 退化为 $O(n)$。例如，依次插入 1, 2, 3, 4, 5，BST 会变成一个只有右子节点的链表。

示例

以下是插入有序数据导致 BST 退化的 Python 代码示例：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass BST:def __init__(self):self.root = Nonedef insert(self, val):if not self.root:self.root = TreeNode(val)else:self._insert(self.root, val)def _insert(self, node, val):if val < node.val:if node.left is None:node.left = TreeNode(val)else:self._insert(node.left, val)else:if node.right is None:node.right = TreeNode(val)else:self._insert(node.right, val)# 插入有序数据
bst = BST()
for i in range(1, 6):bst.insert(i)

2. 平衡树的定义

平衡树是一种特殊的二叉搜索树，它通过一些机制保证树的高度始终保持在 $O(\log n)$ 级别，从而使得树的查找、插入和删除操作的时间复杂度稳定在 $O(\log n)$。常见的平衡树有 AVL 树、红黑树等。

3. AVL 树

知识点

AVL 树是一种自平衡的二叉搜索树，它在每个节点中维护一个平衡因子（Balance Factor），平衡因子定义为该节点的左子树的高度减去右子树的高度。AVL 树要求每个节点的平衡因子的绝对值不超过 1，即平衡因子只能是 -1、0 或 1。

不平衡产生的原因

在 AVL 树中插入或删除节点可能会导致树的不平衡，具体有以下四种情况：

• LL 型：在左子树的左子树上插入节点，导致根节点的平衡因子大于 1。
• RR 型：在右子树的右子树上插入节点，导致根节点的平衡因子小于 -1。
• LR 型：在左子树的右子树上插入节点，导致根节点的平衡因子大于1。
• RL 型：在右子树的左子树上插入节点，导致根节点的平衡因子小于 -1。

旋转操作

为了恢复 AVL 树的平衡，需要进行旋转操作，主要有以下两种基本旋转：

• 左旋：用于处理 RR 型不平衡。
• 右旋：用于处理 LL 型不平衡。

还有两种组合旋转：

• LR 旋转：先对左子树进行左旋，再对根节点进行右旋。

• RL 旋转：先对右子树进行右旋，再对根节点进行左旋。

4. AVL 树代码设计

树节点

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightself.height = 1  # 节点的高度，初始为 1

旋转操作

# 右旋
def right_rotate(y):x = y.leftT2 = x.rightx.right = yy.left = T2y.height = max(get_height(y.left), get_height(y.right)) + 1x.height = max(get_height(x.left), get_height(x.right)) + 1return x# 左旋
def left_rotate(x):y = x.rightT2 = y.lefty.left = xx.right = T2x.height = max(get_height(x.left), get_height(x.right)) + 1y.height = max(get_height(y.left), get_height(y.right)) + 1return y# 获取节点的高度
def get_height(node):if not node:return 0return node.height# 获取节点的平衡因子
def get_balance(node):if not node:return 0return get_height(node.left) - get_height(node.right)

插入节点操作

def insert(root, val):if not root:return TreeNode(val)if val < root.val:root.left = insert(root.left, val)else:root.right = insert(root.right, val)root.height = 1 + max(get_height(root.left), get_height(root.right))balance = get_balance(root)# LL 型if balance > 1 and val < root.left.val:return right_rotate(root)# RR 型if balance < -1 and val > root.right.val:return left_rotate(root)# LR 型if balance > 1 and val > root.left.val:root.left = left_rotate(root.left)return right_rotate(root)# RL 型if balance < -1 and val < root.right.val:root.right = right_rotate(root.right)return left_rotate(root)return root

删除节点操作

def min_value_node(node):current = nodewhile current.left is not None:current = current.leftreturn currentdef delete(root, val):if not root:return rootif val < root.val:root.left = delete(root.left, val)elif val > root.val:root.right = delete(root.right, val)else:if root.left is None:temp = root.rightroot = Nonereturn tempelif root.right is None:temp = root.leftroot = Nonereturn temptemp = min_value_node(root.right)root.val = temp.valroot.right = delete(root.right, temp.val)if root is None:return rootroot.height = 1 + max(get_height(root.left), get_height(root.right))balance = get_balance(root)# LL 型if balance > 1 and get_balance(root.left) >= 0:return right_rotate(root)# RR 型if balance < -1 and get_balance(root.right) <= 0:return left_rotate(root)# LR 型if balance > 1 and get_balance(root.left) < 0:root.left = left_rotate(root.left)return right_rotate(root)# RL 型if balance < -1 and get_balance(root.right) > 0:root.right = right_rotate(root.right)return left_rotate(root)return root

测试代码

root = None
values = [9, 5, 10, 0, 6, 11, -1, 1, 2]
for val in values:root = insert(root, val)root = delete(root, 10)

以上代码实现了 AVL 树的基本操作，包括插入节点、删除节点以及旋转操作来维护树的平衡。

红黑树的定义

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色 ，通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。红黑树必须满足以下五个性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点，空节点）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

代码设计

节点类设计

class RBNode:def __init__(self, key, color='red', left=None, right=None, parent=None):self.key = keyself.color = colorself.left = leftself.right = rightself.parent = parentclass RBTree:def __init__(self):self.NIL = RBNode(None, color='black')self.root = self.NIL

左旋和右旋操作

左旋和右旋操作是红黑树维护平衡的基础操作，用于调整树的结构。

    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, y):x = y.lefty.left = x.rightif x.right != self.NIL:x.right.parent = yx.parent = y.parentif y.parent == self.NIL:self.root = xelif y == y.parent.right:y.parent.right = xelse:y.parent.left = xx.right = yy.parent = x

插入操作

插入操作首先按照二叉搜索树的插入方法将节点插入到合适的位置，然后通过颜色调整和旋转操作来维护红黑树的性质。

    def insert(self, key):new_node = RBNode(key)y = self.NILx = self.rootwhile x != self.NIL:y = xif new_node.key < x.key:x = x.leftelse:x = x.rightnew_node.parent = yif y == self.NIL:self.root = new_nodeelif new_node.key < y.key:y.left = new_nodeelse:y.right = new_nodenew_node.left = self.NILnew_node.right = self.NILnew_node.color = 'red'self.insert_fixup(new_node)def insert_fixup(self, z):while z.parent.color == 'red':if z.parent == z.parent.parent.left:y = z.parent.parent.rightif y.color == 'red':z.parent.color = 'black'y.color = 'black'z.parent.parent.color = 'red'z = z.parent.parentelse:if z == z.parent.right:z = z.parentself.left_rotate(z)z.parent.color = 'black'z.parent.parent.color = 'red'self.right_rotate(z.parent.parent)else:y = z.parent.parent.leftif y.color == 'red':z.parent.color = 'black'y.color = 'black'z.parent.parent.color = 'red'z = z.parent.parentelse:if z == z.parent.left:z = z.parentself.right_rotate(z)z.parent.color = 'black'z.parent.parent.color = 'red'self.left_rotate(z.parent.parent)self.root.color = 'black'

删除操作

删除操作首先按照二叉搜索树的删除方法删除节点，然后通过颜色调整和旋转操作来维护红黑树的性质。

    def transplant(self, u, v):if u.parent == self.NIL:self.root = velif u == u.parent.left:u.parent.left = velse:u.parent.right = vv.parent = u.parentdef delete(self, key):z = self.search(key)if z == self.NIL:returny = zy_original_color = y.colorif z.left == self.NIL:x = z.rightself.transplant(z, z.right)elif z.right == self.NIL:x = z.leftself.transplant(z, z.left)else:y = self.minimum(z.right)y_original_color = y.colorx = y.rightif y.parent == z:x.parent = yelse:self.transplant(y, y.right)y.right = z.righty.right.parent = yself.transplant(z, y)y.left = z.lefty.left.parent = yy.color = z.colorif y_original_color == 'black':self.delete_fixup(x)def search(self, key):node = self.rootwhile node != self.NIL and key != node.key:if key < node.key:node = node.leftelse:node = node.rightreturn nodedef minimum(self, node):while node.left != self.NIL:node = node.leftreturn nodedef delete_fixup(self, x):while x != self.root and x.color == 'black':if x == x.parent.left:w = x.parent.rightif w.color == 'red':w.color = 'black'x.parent.color = 'red'self.left_rotate(x.parent)w = x.parent.rightif w.left.color == 'black' and w.right.color == 'black':w.color = 'red'x = x.parentelse:if w.right.color == 'black':w.left.color = 'black'w.color = 'red'self.right_rotate(w)w = x.parent.rightw.color = x.parent.colorx.parent.color = 'black'w.right.color = 'black'self.left_rotate(x.parent)x = self.rootelse:w = x.parent.leftif w.color == 'red':w.color = 'black'x.parent.color = 'red'self.right_rotate(x.parent)w = x.parent.leftif w.right.color == 'black' and w.left.color == 'black':w.color = 'red'x = x.parentelse:if w.left.color == 'black':w.right.color = 'black'w.color = 'red'self.left_rotate(w)w = x.parent.leftw.color = x.parent.colorx.parent.color = 'black'w.left.color = 'black'self.right_rotate(x.parent)x = self.rootx.color = 'black'

黑侄情形、红侄情形、同边、对边

在红黑树的插入和删除操作的修复过程中，会遇到不同的情况，这些情况可以根据兄弟节点及其子节点的颜色和相对位置进行分类：

黑侄情形：兄弟节点的两个子节点都是黑色。在删除操作的修复过程中，遇到黑侄情形时，通常需要将兄弟节点染成红色，并将当前节点上移到其父节点，继续进行修复。

• 红侄情形： 兄弟节点至少有一个红色子节点。此时需要通过旋转和颜色调整来恢复红黑树的性质。
• 同边：以删除操作中当前节点为左子节点为例，如果兄弟节点的红色子节点也是左子节点，称为同边情况。这种情况下，通常需要先对兄弟节点进行一次旋转，将其转换为对边情况。
• 对边：同样以删除操作中当前节点为左子节点为例，如果兄弟节点的红色子节点是右子节点，称为对边情况。对边情况可以通过一次旋转和颜色调整来完成修复。

测试代码

# 测试代码
rb_tree = RBTree()
keys = [5, 3, 7, 2, 4, 6, 8]
for key in keys:rb_tree.insert(key)
rb_tree.delete(3)

以上代码实现了红黑树的基本操作，包括插入、删除等，并处理了各种可能的情况来维护红黑树的性质。

问题起源

Huffman编码（哈夫曼编码）由美国数学家大卫·哈夫曼（David A. Huffman）在1952年提出。当时，哈夫曼在麻省理工学院攻读博士学位，他的老师要求学生们选择一种最有效的编码方式来解决数据压缩问题，否则就要完成一篇学期论文。哈夫曼在尝试多种方法无果后，转而从逆向思维出发，最终提出了哈夫曼编码算法，成功解决了数据压缩问题，并且这种编码方式在信息论、数据压缩等领域得到了广泛应用。

基本概念

Huffman编码是一种变长编码方式，用于无损数据压缩。其核心思想是通过构建最优二叉树（Huffman树），为出现频率不同的字符分配不同长度的编码，出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码，从而减少数据的整体存储空间。

树的定义

Huffman树（哈夫曼树），也称为 最优二叉树，是一种带权路径长度（WPL）最短的二叉树。在Huffman树中，每个叶子节点代表一个字符，节点的权值为该字符在数据中出现的频率。树的带权路径长度是指树中所有叶子节点的权值乘以其到根节点的路径长度之和。

节点的数量

假设有 $n$ 个不同的字符需要编码，那么构建的Huffman树的节点总数为 $2n-1$。这是因为在构建Huffman树的过程中，每次合并两个节点会产生一个新的父节点，初始有 $n$ 个叶子节点，经过 $n-1$ 次合并操作后，会新增 $n-1$ 个非叶子节点，所以节点总数为 $n+(n-1)=2n-1$。

基本思想

Huffman编码的基本思想是基于字符出现的频率来构建编码。频率高的字符使用较短的编码，频率低的字符使用较长的编码，这样可以使得整个数据的编码长度最短，从而实现数据压缩的目的。通过构建Huffman树，从根节点到每个叶子节点的路径就对应了该叶子节点所代表字符的编码。

构建步骤

1. 统计字符频率：遍历需要编码的数据，统计每个字符出现的频率。
2. 初始化节点：将每个字符及其频率作为一个节点，构建一个节点集合。
3. 构建Huffman树：

• 从节点集合中选取两个频率最小的节点。
  • 创建一个新的内部节点，其频率为这两个节点的频率之和，将这两个节点作为新节点的左右子节点。
  • 将新节点加入节点集合，并从集合中移除原来的两个节点。
  • 重复上述步骤，直到节点集合中只剩下一个节点，这个节点就是Huffman树的根节点。

4. 生成编码：从根节点开始，向左走标记为0，向右走标记为1，直到到达叶子节点，这样从根节点到叶子节点的路径上的标记序列就是该叶子节点所代表字符的Huffman编码。

Huffman码表

Huffman码表是一个映射表，它记录了每个字符与其对应的Huffman编码之间的关系。通过遍历Huffman树，可以生成这个码表。

以下是一个Python实现的示例代码：

import heapq
from collections import defaultdict# 定义Huffman树节点类
class HuffmanNode:def __init__(self, char, freq):self.char = charself.freq = freqself.left = Noneself.right = Nonedef __lt__(self, other):return self.freq < other.freq# 构建Huffman树
def build_huffman_tree(data):# 统计字符频率frequency = defaultdict(int)for char in data:frequency[char] += 1# 初始化优先队列（最小堆）heap = []for char, freq in frequency.items():node = HuffmanNode(char, freq)heapq.heappush(heap, node)# 构建Huffman树while len(heap) > 1:left = heapq.heappop(heap)right = heapq.heappop(heap)merged = HuffmanNode(None, left.freq + right.freq)merged.left = leftmerged.right = rightheapq.heappush(heap, merged)return heap[0]# 生成Huffman码表
def generate_huffman_codes(root, current_code, huffman_codes):if root is None:returnif root.char is not None:huffman_codes[root.char] = current_codereturngenerate_huffman_codes(root.left, current_code + "0", huffman_codes)generate_huffman_codes(root.right, current_code + "1", huffman_codes)# 主函数
def huffman_encoding(data):if len(data) == 0:return "", Noneroot = build_huffman_tree(data)huffman_codes = {}generate_huffman_codes(root, "", huffman_codes)encoded_data = ""for char in data:encoded_data += huffman_codes[char]return encoded_data, huffman_codes# 测试
data = "hello world"
encoded_data, huffman_codes = huffman_encoding(data)
print("Huffman码表:")
for char, code in huffman_codes.items():print(f"{char}: {code}")
print("编码后的数据:", encoded_data)

在上述代码中，首先定义了Huffman树的节点类 HuffmanNode，然后通过 build_huffman_tree
函数构建Huffman树，接着使用 generate_huffman_codes 函数生成Huffman码表，最后在
huffman_encoding 函数中完成数据的编码。通过这个示例，你可以看到如何生成Huffman码表并对数据进行编码。

💖💝亲亲， 创作不易 看完点点专注呀♥❤💕💞