数据结构笔记2
一、红黑树（Red-Black Tree）
1. 背景
平衡二叉树（AVL）虽能保证查询复杂度稳定在O(logN)，但旋转调整过于复杂，性能消耗较大；红黑树作为折中方案，兼顾稳定性和维护成本，是“最优二叉搜索树”。
2. 理论基础与来源
（1）数据结构演进逻辑：哈希表拉链法查询复杂度可达O(N) → 引入二叉搜索树（BST），但BST不稳定，最坏退化为链表 → 平衡二叉树（AVL）解决稳定性，但旋转复杂 → 红黑树（折中方案），源于多叉树家族的2-3-4树（四阶B树）。
（2）2-3-4树核心：从下向上构建，节点可实现“升级”（如二节点升级为三节点），插入数据时通过“向上挤压中间值”维持树形结构，为红黑树的构建提供底层逻辑。
3. 核心特性与性能优势
（1）五大核心特性（必须满足）：
所有节点非红即黑；
根节点必为黑色；
叶子节点（NIL节点，空节点）必为黑色；
红色节点的子节点必须是黑色（即不能出现两个连续的红色节点）；
从根节点到任意叶子节点的路径上，黑色节点的数目完全相同。
（2）性能优势：
平衡要求宽松：仅要求“最长路径长度不超过最短路径长度的2倍”，无需像AVL树那样严格维持左右子树高度差≤1；
维护成本低：减少了旋转调整的次数，兼顾O(logN)的查询/插入/删除复杂度，是实际应用中最优的二叉搜索树。
二、哈夫曼编码（Huffman Coding）
1. 学习背景（解决的核心问题）
解决定长编码空间浪费、变长编码解码歧义的问题，核心应用于数据压缩，实现“高频字符占用空间少、低频字符占用空间多”的高效编码。
2. 编码方式对比（核心区别）
定长编码：如ASCII码，每个字符固定占用8位，优点是解码简单，缺点是高频字符存在大量冗余，压缩率低；
普通变长编码：自定义编码长度（高频字符短、低频字符长），可减少总比特数，但存在解码歧义（无法确定编码截取边界），无法准确还原原始数据。
3. 哈夫曼树构建与编码原理
（1）哈夫曼树定义：带权路径长度（WPL）最小的二叉树，权值对应字符出现频率。
（2）构建策略（关键步骤）：每次选取权值最小的两个节点合并，生成一个新节点（新节点权值=两个子节点权值之和），重复此过程，直至所有节点合并为一棵完整的树；核心原则是“权值大的节点离根节点更近”。
（3）压缩原理：
编码规则：哈夫曼树中，左路径编码为0，右路径编码为1，每个字符的编码为“从根节点到该节点的路径组合”；
核心优势：编码为前缀码（任意一个字符的编码都不是另一个字符编码的前缀），解决了解码歧义；高频字符编码短、低频字符编码长，压缩率可达60%-75%。
三、B树（B-Tree）及其应用场景
1. 学习背景（解决的核心问题）
针对磁盘I/O延迟高的特性，优化数据库、文件系统的存储结构，核心目标是减少磁盘I/O次数，提升系统性能。
2. 存储介质速度差异（核心前提）
速度层级（从快到慢）：CPU（0.2纳秒）→ 内存（20纳秒）→ 磁盘（3.5毫秒，约10^6纳秒）；
性能瓶颈：CPU不直接访问磁盘，需通过内存加载磁盘数据，因此磁盘I/O操作是系统性能的主要瓶颈，减少I/O次数是核心优化方向。
3. B树结构优势与应用逻辑
（1）核心结构优势：多叉树结构，单个节点可存储大量键值（Key）和指针，大幅降低树高；
示例：1000条数据，二叉搜索树（红黑树）树高约10层，需10次磁盘I/O；B树通过增加分支数，树高可降至3层左右，仅需3次I/O，大幅提升效率。
（2）设计核心逻辑（性能权衡）：
牺牲少量CPU计算时间：B树节点内部需对键值进行多次比较（CPU纳秒级操作）；
换取磁盘I/O指数级减少：磁盘I/O为毫秒级操作，减少I/O次数对性能的提升远大于CPU计算的消耗；
主要应用：数据库索引、文件系统，适配大量数据的存储与高效查询。
四、总结
红黑树：折中平衡与维护成本，最优二叉搜索树，适用于内存中数据的高效操作；
哈夫曼编码：基于哈夫曼树的前缀编码，核心用于数据压缩，兼顾高效与无歧义；
B树：多叉结构降低树高，减少磁盘I/O，适用于数据库、文件系统等磁盘存储场景。