gb_trees

(https://github.com/erlang/otp/blob/OTP-28.3.1/lib/stdlib/src/gb_trees.erl#L140 "View Source")

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说的不是AAtree的意思，这是Arne Andersson在1999年出的一篇论文，内容讨论优于AVL树的一个通用平衡二叉树，这种树的特点是：

1. 零存储开销 (Zero Storage Overhead)

   1. 不用每个节点都存个平衡因子，只用存一个总大小和一个删除次数

2. 摊还重构成本更低 (Lower Amortized Restructuring Cost)

   1. 对左右子树高度不敏感，需要达到超过了 clogn 的界限才进行干预
   2. 有论文支持虽然偶合有稍微大代价一点的重构子树，但是维护整棵树的总工作量比的avl树要低一些

3. 算法逻辑的简单性 (Simplicity)

   1. General Balanced Trees 只需要关注一个全局标准：树的高度是否超过了 log⁡n，只需要在插入和删除操作时维护两个参数：总大小和删除次数，而无需复杂的平衡因子计算，这使得其在实现上更加高效和简洁。

总结：为什么说它比 AVL 树“性能好”？

表格