檢視原始碼 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 中，否則將 Key 的值更新為 Tree1 中的 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。傳回 {value, Value}，如果不存在 Key，則傳回 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 中，否則將 Key 的值更新為 Tree1 中的 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。傳回 {value, Value}，如果不存在 Key，則傳回 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 中的值傳回為有序列表，並依其對應的鍵排序。不會移除重複項。