Erlang gb_trees 与 General Balanced Trees
查看 Erlang/OTP 28.3.1 中的 gb_trees 源码
General balanced trees.
This module provides Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to unbalanced binary trees, and their performance is better than AVL trees.
官方文档是这样描述的。不过，Arne Andersson's General Balanced Trees 并不是指 AA Tree，而是源自 Arne Andersson 在 1999 年发表的一篇论文。论文讨论了一种性能优于 AVL 树的通用平衡二叉树，其特点如下。
主要特点
零存储开销（Zero Storage Overhead）
每个节点不需要存储平衡因子，只需存储一个总大小和一个删除次数。
更低的摊还重构成本（Lower Amortized Restructuring Cost）
- 对左右子树的高度不敏感，只有树高超过
c log n的界限时才进行干预。 - 论文指出，虽然偶尔需要以稍高的代价重构子树，但维护整棵树的总工作量比 AVL 树更低。
- 对左右子树的高度不敏感，只有树高超过
算法逻辑简单（Simplicity）
General Balanced Trees 只关注一个全局标准：树的高度是否超过
log n。在插入和删除时，只需维护总大小和删除次数，无需进行复杂的平衡因子计算，因此实现更加高效、简洁。
为什么说它比 AVL 树性能更好？
| 特性 | AVL 树 | General Balanced Trees（论文方案） | 优势 |
|---|---|---|---|
| 存储 | 需要存储平衡因子（per-node overhead） | 无节点存储开销，仅需两个全局整数 | 更节省内存，对缓存更友好 |
| 维护策略 | 每次修改都可能触发旋转（strict） | 懒惰重建（lazy/amortized） | 频繁修改时，总旋转或重构工作量更少 |
| 时间复杂度 | 单次操作最坏为 O(log n) | 单次操作摊还为 O(log n) | AVL 保证单次操作的最坏时间；GB 树降低多次操作的总体维护成本 |
