gb_trees

模块

gb_trees

模块摘要

一般平衡的树。

描述

本单元提供Arne Andersson教授的一般平衡树。与不平衡二叉树相比，它们没有存储开销，并且它们的性能比AVL树好。

当且仅当它们不比较equal（==）时，该模块将两个键视为不同。

数据结构

{Size, Tree}

Tree由窗体的节点组成。{Key, Value, Smaller, Bigger}和“空树”节点nil...

删除后不会尝试平衡树。由于删除不会增加树的高度，所以这应该是可以的。

原始平衡条件h（T）<= ceil（c * log（| T |））已经改变为类似的（但不完全等同）条件。^ c。这应该也没关系。

数据类型

tree(Key, Value)

一般平衡的树。

tree() =tree(term(), term())

iter(Key, Value)

一般的平衡树迭代器。

iter() =iter(term(), term())

输出

balance(Tree1) -> Tree2

类型

重新平衡树1。请注意，这是很少需要的，但可以在没有进一步插入的情况下从树中删除多个节点时激发它们。然后可以强制重新平衡以最小化查找时间，因为删除不会重新平衡树。

delete(Key, Tree1) -> Tree2

类型

从Tree1中删除具有键Key的节点并返回新的树。假设密钥存在于树中，否则会崩溃。

delete_any(Key, Tree1) -> Tree2

类型

删除与关键节点Key从Tree1钥匙是否存在于树，否则什么也不做。返回新树。

take(Key, Tree1) -> {Value, Tree2}

类型

返回一个值，其值来自密钥为Key的节点以及没有具有此值的节点的新Tree2。假设带有密钥的节点出现在树中，否则会崩溃。

take_any(Key, Tree1) -> {Value, Tree2} | error

类型

返回一个值，其值来自密钥为Key的节点以及没有具有此值的节点的新Tree2。如果带有键的节点不存在于树中，则返回错误。

empty() -> tree()

返回一个新的空树。

enter(Key, Value, Tree1) -> Tree2

类型

如果密钥不存在于树中，则将具有值的值的值插入到树1中，否则将密钥更新为树值1中的值。返回新树。

from_orddict(List) -> Tree

类型

转一个有序列表List把键值元组变成一棵树。列表不能包含重复的键。

get(Key, Tree) -> Value

类型

检索存储在Key在Tree假设密钥存在于树中，否则崩溃。

insert(Key, Value, Tree1) -> Tree2

类型

镶片Key有价值Value进Tree1并返回新树。假设密钥不存在于树中，否则会崩溃。

s_defined(Key, Tree) -> boolean()

类型

如果Key存在于Tree中，则返回true，否则返回false。

is_empty(Tree) -> boolean()

类型

如果Tree是空树，则返回true，否则返回false。

iterator（Tree)->Iter

类型

返回一个迭代器，该迭代器可用于遍历Tree；见next/1.这一实现非常有效；使用next/1仅略慢于获取所有元素的列表。to_list/1穿越那个。迭代器方法的主要优点是它不需要在内存中同时构建所有元素的完整列表。

iterator_from(Key, Tree) -> Iter

类型

返回可用于遍历条目的迭代器Tree; 见next/1。与返回的迭代器相比，差异在于返回iterator/1大于或等于的第一个键Key。

keys(Tree) -> Key

类型

返回键Tree作为一个有序的名单。

largest(Tree) -> {Key, Value}

类型

返回{Key, Value}，其中Key最大的键为Tree，并且Value是与此键关联的值。假定树不是空的。

lookup(Key, Tree) -> none | {value, Value}

类型

在树中查找关键字。返回{value，Value}，如果Key不存在则返回none。

map(Function, Tree1) -> Tree2

类型

将函数F（K，V1） - > V2映射到树Tree1的所有键值对。使用与Tree1相同的一组键和一组新的值V2返回一个新的树Tree2。

ext(Iter1) -> none | {Key, Value, Iter2}

类型

返回{Key，Value，Iter2}，其中Key是迭代器Iter1引用的最小键，Iter2是用于遍历剩余节点的新迭代器，如果没有剩余节点，则原子为none。

size(Tree) -> integer() >= 0

类型

返回树中的节点数。

smallest(Tree) -> {Key, Value}

类型

返回{Key，Value}，其中Key是树中最小的键，Value是与此键关联的值。假定树不是空的。

take_largest(Tree1) -> {Key, Value, Tree2}

类型

返回{Key，Value，Tree2}，其中Key是Tree1中最大的键，Value是与此键关联的值，Tree2是删除了相应节点的树。假定树不是空的。

take_smallest(Tree1) -> {Key, Value, Tree2}

类型

返回{Key，Value，Tree2}，其中Key是Tree1中最小的键，Value是与此键关联的值，Tree2是删除了相应节点的树。假定树不是空的。

to_list(Tree) -> {Key, Value}

类型

将树转换为键值元组的有序列表。

update(Key, Value, Tree1) -> Tree2

类型

更新Key珍视Value中Tree1并返回新树。假定密钥存在于树中。

values(Tree) -> Value

类型

以有序列表的形式返回值tree，并按其相应的键进行排序。重复不会被删除。

另见

dict(3)，gb_sets(3)