自适应哈夫曼树是动态更新结构的编码树，核心区别在于无需预统计频率、边读边编；静态版须扫完全部输入才建树。关键约束是兄弟性质，推荐用索引数组实现而非指针。
什么是自适应哈夫曼树，和静态版根本区别在哪
自适应哈夫曼树（Adaptive Huffman Coding）的核心是动态更新树结构——每次编码/解码一个符号后，立即根据新频次重排树，不需要预先统计全部字符频率。这和 build_tree_from_frequencies() 那种静态建树方式完全不同：后者必须扫完全部输入才能开始编码，而自适应版本边读边编，内存占用恒定、适合流式场景。
关键约束在于：必须满足“兄弟性质”（Sibling Property），即所有节点按权重升序排列时，任一节点与其父节点的编号在数组中必须相邻。违反这点会导致解码端无法同步重建树。
用数组还是指针实现？推荐用索引模拟指针
C++里直接用 new Node 做指针树看似自然，但自适应哈夫曼要求频繁交换节点位置、批量更新父指针——指针操作极易出错，且 swap() 会破坏父子引用关系。更稳妥的做法是用单个 std::vector<node></node> 存储所有节点，每个 Node 只存整数索引：parent、left、right 全是 size_t。
这样做的好处：
-
std::vector::swap()安全，不改索引语义 - 遍历节点时 cache 局部性好，比指针跳转快
- 解码时通过索引查表比解引用指针更稳定
注意：初始树必须只含一个“未定义符号”节点（通常记作 NYT，Not Yet Transmitted），其权重为 0；首次遇到新字符时，才把 NYT 拆成两个子节点——一个存该字符，一个生成新的 NYT。
update() 函数怎么写才不出错
update() 是自适应哈夫曼最易崩的地方，常见错误包括：权重加完没上滤、交换节点后忘了更新子节点的父索引、对 NYT 节点误增权。
标准流程应严格分三步：
- 给当前字符对应叶子节点权重 +1
- 从该节点向上执行“上滤”（upward move）：只要当前节点权重 > 同层右边邻居的权重，就交换二者，并同步修正它们的父节点字段
- 每次交换后，检查并更新涉及节点的
parent字段（尤其注意：被交换节点的子节点的parent也要跟着换）
别省略边界判断：if (node_idx == 0) break; 必须有，否则越界访问 nodes[node_idx-1]。另外，权重相等时不能交换——兄弟性质依赖严格升序，相等会导致解码端树形不一致。
解码端如何保证和编码端完全同步
解码不是“反向走树”那么简单。因为每解一个符号，树结构就变一次，所以解码器必须和编码器用同一套 update 规则，连初始化、NYT 分裂顺序、交换判定条件都得一字不差。
典型坑点：
- 编码端用
weight += 1，解码端却用了weight = 1（漏了累加） - 编码端交换节点前先改父索引，解码端后改，导致某轮树形短暂不合法
- 对
NYT的处理逻辑分支不一致（比如一个用if (node.weight == 0)判，另一个用if (node.symbol == NYT_SYMBOL)）
最保险的做法：把 update() 封装成独立函数，在编码/解码模块中直接共用同一份实现，不要复制粘贴后微调。
自适应哈夫曼真正难的不是算法本身，而是所有状态变更必须原子、可逆、严格左右对称。哪怕一个索引更新漏了，后续整个流就全错，而且这种错误往往延迟几十个符号才暴露。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
