查看源码 gb_trees (stdlib v6.2)
通用平衡树。
此模块提供 Arne Andersson 教授的通用平衡树。与不平衡二叉树相比，它们没有存储开销，并且它们的性能优于 AVL 树。
当且仅当两个键不相等比较（==）时，此模块才认为它们不同。
数据结构
树和迭代器是使用不透明的数据结构构建的，不应在此模块外部进行模式匹配。
删除后不会尝试平衡树。由于删除不会增加树的高度，因此应该没问题。
原始的平衡条件 h(T) <= ceil(c * log(|T|)) 已更改为类似的（但不太等效）条件 2 ^ h(T) <= |T| ^ c。这应该也没问题。
另请参阅
概要
函数
重新平衡 Tree1。
从 Tree1 中删除键为 Key 的节点，并返回新树。假设该键存在于树中，否则崩溃。
如果键存在于树中，则从 Tree1 中删除键为 Key 的节点，否则不执行任何操作。返回新树。
返回一个新的空树。
如果键不存在于树中，则将具有值 Value 的 Key 插入到 Tree1 中，否则将 Tree1 中 Key 的值更新为 Value。返回新树。
将键值元组的有序列表 List 转换为树。该列表不得包含重复的键。
检索 Tree 中与 Key 存储的值。假设该键存在于树中，否则崩溃。
将具有值 Value 的 Key 插入到 Tree1 中，并返回新树。假设该键不存在于树中，否则崩溃。
如果 Key 存在于 Tree 中，则返回 true，否则返回 false。
如果 Tree 是空树，则返回 true，否则返回 false。
返回一个迭代器，该迭代器可用于遍历 Tree 的条目；请参阅 next/1。
返回一个迭代器，该迭代器可用于按 ordered 或 reversed 方向遍历 Tree 的条目；请参阅 next/1。
返回一个迭代器，该迭代器可用于遍历 Tree 的条目；请参阅 next/1。与 iterator/1 返回的迭代器相比，区别在于迭代器从大于或等于 Key 的第一个键开始。
返回一个迭代器，该迭代器可用于按 ordered 或 reversed 方向遍历 Tree 的条目；请参阅 next/1。与 iterator/2 返回的迭代器相比，区别在于迭代器从下一个大于或等于 Key 的第一个键开始。
以有序列表形式返回 Tree 中的键。
返回 {Key2, Value}，其中 Key2 是严格大于 Key1 的最小键，Value 是与此键关联的值。
返回 {Key, Value}，其中 Key 是 Tree 中的最大键，Value 是与此键关联的值。假设该树不为空。
在 Tree 中查找 Key。如果 Key 不存在，则返回 {value, Value} 或 none。
将函数 F(K, V1) -> V2 映射到树 Tree1 的所有键值对。返回一个新的树 Tree2，它与 Tree1 具有相同的键集和新的值集 V2。
返回 {Key, Value, Iter2}，其中 Key 是迭代器 Iter1 引用的下一个键，Iter2 是用于遍历剩余节点的新迭代器，如果没有剩余节点，则返回原子 none。
返回 Tree 中的节点数。
返回 {Key2, Value}，其中 Key2 是严格小于 Key1 的最大键，Value 是与此键关联的值。
返回 {Key, Value}，其中 Key 是 Tree 中的最小键，Value 是与此键关联的值。假设该树不为空。
从键为 Key 的节点返回一个值 Value，并返回一个新的 Tree2，其中不包含具有此值的节点。假设该键存在于树中，否则崩溃。
从键为 Key 的节点返回一个值 Value，并返回一个新的 Tree2，其中不包含具有此值的节点。如果树中不存在具有该键的节点，则返回 error。
返回 {Key, Value, Tree2}，其中 Key 是 Tree1 中的最大键，Value 是与此键关联的值，Tree2 是删除相应节点后的树。假设该树不为空。
返回 {Key, Value, Tree2}，其中 Key 是 Tree1 中的最小键，Value 是与此键关联的值，Tree2 是删除相应节点后的树。假设该树不为空。
将树转换为键值元组的有序列表。
将 Tree1 中的 Key 更新为值 Value，并返回新树。假设该键存在于树中。
以有序列表形式返回 Tree 中的值，按其对应的键排序。不会删除重复项。
类型
函数
重新平衡 Tree1。
请注意，这很少是必要的，但在从树中删除许多节点而没有进一步插入的情况下，可以这样做。然后可以强制重新平衡以最大程度地减少查找时间，因为删除不会重新平衡树。
从 Tree1 中删除键为 Key 的节点，并返回新树。假设该键存在于树中，否则崩溃。
如果键存在于树中，则从 Tree1 中删除键为 Key 的节点，否则不执行任何操作。返回新树。
返回一个新的空树。
如果键不存在于树中，则将具有值 Value 的 Key 插入到 Tree1 中，否则将 Tree1 中 Key 的值更新为 Value。返回新树。
-spec from_orddict(List) -> Tree when List :: [{Key, Value}], Tree :: tree(Key, Value).
将键值元组的有序列表 List 转换为树。该列表不得包含重复的键。
-spec get(Key, Tree) -> Value when Tree :: tree(Key, Value).
检索 Tree 中与 Key 存储的值。假设该键存在于树中，否则崩溃。
将具有值 Value 的 Key 插入到 Tree1 中，并返回新树。假设该键不存在于树中，否则崩溃。
如果 Key 存在于 Tree 中，则返回 true，否则返回 false。
如果 Tree 是空树，则返回 true，否则返回 false。
返回一个迭代器，该迭代器可用于遍历 Tree 的条目；请参阅 next/1。
-spec iterator(Tree, Order) -> Iter when Tree :: tree(Key, Value), Iter :: iter(Key, Value), Order :: ordered | reversed.
返回一个迭代器，该迭代器可用于按 ordered 或 reversed 方向遍历 Tree 的条目；请参阅 next/1。
此实现非常高效；使用 next/1 遍历整个树仅比使用 to_list/1 获取所有元素的列表并遍历该列表慢一点。迭代器方法的主要优点是它不需要一次在内存中构建所有元素的完整列表。
返回一个迭代器，该迭代器可用于遍历 Tree 的条目；请参阅 next/1。与 iterator/1 返回的迭代器相比，区别在于迭代器从大于或等于 Key 的第一个键开始。
-spec iterator_from(Key, Tree, Order) -> Iter when Tree :: tree(Key, Value), Iter :: iter(Key, Value), Order :: ordered | reversed.
返回一个迭代器，该迭代器可用于按 ordered 或 reversed 方向遍历 Tree 的条目；请参阅 next/1。与 iterator/2 返回的迭代器相比，区别在于迭代器从下一个大于或等于 Key 的第一个键开始。
以有序列表形式返回 Tree 中的键。
-spec larger(Key1, Tree) -> none | {Key2, Value} when Key1 :: Key, Key2 :: Key, Tree :: tree(Key, Value).
返回 {Key2, Value}，其中 Key2 是严格大于 Key1 的最小键，Value 是与此键关联的值。
如果不存在这样的对，则返回 none。
-spec largest(Tree) -> {Key, Value} when Tree :: tree(Key, Value).
返回 {Key, Value}，其中 Key 是 Tree 中的最大键，Value 是与此键关联的值。假设该树不为空。
-spec lookup(Key, Tree) -> none | {value, Value} when Tree :: tree(Key, Value).
在 Tree 中查找 Key。如果 Key 不存在，则返回 {value, Value} 或 none。
-spec map(Function, Tree1) -> Tree2 when Function :: fun((K :: Key, V1 :: Value1) -> V2 :: Value2), Tree1 :: tree(Key, Value1), Tree2 :: tree(Key, Value2).
将函数 F(K, V1) -> V2 映射到树 Tree1 的所有键值对。返回一个新的树 Tree2，它与 Tree1 具有相同的键集和新的值集 V2。
-spec next(Iter1) -> none | {Key, Value, Iter2} when Iter1 :: iter(Key, Value), Iter2 :: iter(Key, Value).
返回 {Key, Value, Iter2}，其中 Key 是迭代器 Iter1 引用的下一个键，Iter2 是用于遍历剩余节点的新迭代器，如果没有剩余节点，则返回原子 none。
-spec size(Tree) -> non_neg_integer() when Tree :: tree().
返回 Tree 中的节点数。
-spec smaller(Key1, Tree) -> none | {Key2, Value} when Key1 :: Key, Key2 :: Key, Tree :: tree(Key, Value).
返回 {Key2, Value}，其中 Key2 是严格小于 Key1 的最大键，Value 是与此键关联的值。
如果不存在这样的对，则返回 none。
-spec smallest(Tree) -> {Key, Value} when Tree :: tree(Key, Value).
返回 {Key, Value}，其中 Key 是 Tree 中的最小键，Value 是与此键关联的值。假设该树不为空。
-spec take(Key, Tree1) -> {Value, Tree2} when Tree1 :: tree(Key, _), Tree2 :: tree(Key, _), Key :: term(), Value :: term().
从键为 Key 的节点返回一个值 Value，并返回一个新的 Tree2，其中不包含具有此值的节点。假设该键存在于树中，否则崩溃。
-spec take_any(Key, Tree1) -> {Value, Tree2} | error when Tree1 :: tree(Key, _), Tree2 :: tree(Key, _), Key :: term(), Value :: term().
从键为 Key 的节点返回一个值 Value，并返回一个新的 Tree2，其中不包含具有此值的节点。如果树中不存在具有该键的节点，则返回 error。
-spec take_largest(Tree1) -> {Key, Value, Tree2} when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).
返回 {Key, Value, Tree2}，其中 Key 是 Tree1 中的最大键，Value 是与此键关联的值，Tree2 是删除相应节点后的树。假设该树不为空。
-spec take_smallest(Tree1) -> {Key, Value, Tree2} when Tree1 :: tree(Key, Value), Tree2 :: tree(Key, Value).
返回 {Key, Value, Tree2}，其中 Key 是 Tree1 中的最小键，Value 是与此键关联的值，Tree2 是删除相应节点后的树。假设该树不为空。
-spec to_list(Tree) -> [{Key, Value}] when Tree :: tree(Key, Value).
将树转换为键值元组的有序列表。
将 Tree1 中的 Key 更新为值 Value，并返回新树。假设该键存在于树中。
以有序列表形式返回 Tree 中的值，按其对应的键排序。不会删除重复项。