10.4 AVL Trees—library(avl)
This library module provides an AVL tree implementation of "association
lists". The binary tree is kept balanced, as opposed to
library(assoc)
, which provides similar functionality based on
binary trees that are not kept balanced.
Exported predicates:
empty_avl(
?AVL)

is true when AVL is an empty AVL tree.
avl_to_list(
+AVL,
List)

assumes that AVL is a proper AVL tree, and is true when
List is a list of KeyValue pairs in ascending order with no
duplicate keys specifying the same finite function as AVL.
Use this to convert an AVL to an ordered list.
is_avl(
+AVL)

is true when AVL is a (proper) AVL tree. It checks both the order
condition (that the keys are in ascending order as you go from left
to right) and the height balance condition. This code relies on
variables (to be precise, the first anonymous variable in is_avl/1)
being
@<
than any nonvariable. in strict point of fact you can
construct an AVL tree with variables as keys, but is_avl/1
doesn't
believe it, and it is not good taste to do so.
avl_domain(
+AVL,
Domain)

unifies Domain with the ordered set representation of the domain
of the AVL tree (the keys of it). As the keys are in ascending
order with no duplicates, we just read them off like
avl_to_list/2
.
avl_range(
+AVL,
Range)

unifies Range with the ordered set representation of the range of the
AVL (the values associated with its keys, not the keys themselves).
Note that the cardinality (length) of the domain and the range are
seldom equal, except of course for trees representing intertible maps.
avl_min(
+AVL,
Key)

is true when Key is the smallest key in AVL.
avl_min(
+AVL,
Key,
Val)

is true when Key is the smallest key in AVL and Val is its value.
avl_max(
+AVL,
Key)

is true when Key is the greatest key in AVL.
avl_max(
+AVL,
Key,
Val)

is true when Key is the greatest key in AVL and Val is its value.
avl_height(
+AVL,
Height)

is true when Height is the height of the given AVL tree, that is,
the longest path in the tree has Height 'node's on it.
avl_size(
+AVL,
Size)

is true when Size is the size of the AVL tree, the number of 'node's in it.
portray_avl(
+AVL)

writes an AVL tree to the current output stream in a pretty form so
that you can easily see what it is. Note that an AVL tree written
out this way can NOT be read back in; for that use
writeq/1
. The
point of this predicate is
to get AVL trees displayed nicely by print/1
.
avl_member(
?Key,
+AVL)

is true when Key is one of the keys in the given AVL. This
predicate should be used to enumerate the keys, not to look for
a particular key (use
avl_fetch/2
or avl_fetch/3
for that).
The Keys are enumerated in ascending order.
avl_member(
?Key,
+AVL,
?Val)

is true when Key is one of the keys in the given AVL and Val is
the value the AVL associates with that Key. This predicate should
be used to enumerate the keys and their values, not to look up the
value of a known key (use
avl_fetch/3
) for that.
The Keys are enumerated in ascending order.
avl_fetch(
+Key,
+AVL)

is true when the (given) Key is one of the keys in the (given) AVL.
Use this to test whether a known Key occurs in AVL and you don't
want to know the value associated with it.
avl_fetch(
+Key,
+AVL,
Val)

is true when the (given) Key is one of the keys in the (given) AVL
and the value associated with it therein is Val. It should be
used to look up known keys, not to enumerate keys (use either
avl_member/2
or avl_member/3
for that).
avl_next(
+Key,
+AVL,
Knext)

is true when Knext is the next key after Key in AVL;
that is, Knext is the smallest key in AVL such that Knext @> Key.
avl_next(
+Key,
+AVL,
Knext,
Vnext)

is true when Knext is the next key after Key in AVL and Vnext is the
value associated with Knext in AVL. That is, Knext is the smallest
key in AVL such that Knext @> Key, and
avl_fetch(
Knext,
Val,
Vnext)
.
avl_prev(
+Key,
+AVL,
Kprev)

is true when Kprev is the key previous to Key in AVL;
that is, Kprev is the greatest key in AVL such that Kprev @< Key.
avl_prev(
+Key,
+AVL,
Kprev,
Vprev)

is true when Kprev is the key previous to Key in AVL and Vprev is the
value associated with Kprev in AVL. That is, Kprev is the greatest key
in AVL such that Kprev @< Key, and
avl_fetch(
Kprev,
AVL,
Vprev)
.
avl_change(
+Key,
?AVL1,
?Val1,
?AVL2,
?Val2)

is true when AVL1 and AVL2 are avl trees of exactly the same shape,
Key is a key of both of them, Val1 is the value associated with Key
in AVL1 and Val2 is the value associated with it in AVL2, and when
AVL1 and AVL2 are identical except perhaps for the value they assign
to Key. Use this to change the value associated with a Key which is
already present, not to insert a new Key (it won't).
ord_list_to_avl(
+List,
AVL)

is given a list of KeyVal pairs where the Keys are already in
standard order with no duplicates (this is not checked) and
returns an AVL representing the same associations. This takes
O(N) time, unlike
list_to_avl/2
which takes O(N lg N).
list_to_avl(
+Pairs,
AVL)

is given a list of KeyVal pairs where the Keys are in no particular
order (but are sufficiently instantiated to be told apart) and
returns an AVL representing the same associations. This works by
starting with an empty tree and inserting the elements of the list
into it. This takes O(N lg N) time. Since it is possible to read
off a sorted list in O(N) time from the result, O(N lg N) is as good as
can possibly be done. If the same Key appears more than once in the
input, the last value associated with it will be used.
avl_store(
+Key,
+OldAVL,
+Val,
+NewAVL)

is true when OldAVL and NewAVL define the same finite function
except that NewAVL associates Val with Key. OldAVL need not have
associated any value at all with Key. When it didn't, you can
read this as "insert (Key>Val) into OldAVL giving NewAVL".
avl_incr(
+Key,
+OldAVL,
+Inc,
+NewAVL)

if Key is not present in OldAVL, adds Key>Incr.
if Key>N is present in OldAvl, changes it to Key>N+Incr.
avl_delete(
+Key,
+OldAVL,
Val,
NewAVL)

is true when OldAVL and NewAVL define the same finite function
except that OldAVL associates Key with Val and NewAVL doesn't
associate Key with any value.
avl_del_min(
+OldAVL,
Key,
Val,
NewAVL)

is true when OldAVL and NewAVL define the same finite function
except that OldAVL associates Key with Val and NewAVL doesn't
associate Key with any value and Key precedes all other keys in OldAVL.
avl_del_max(
+OldAVL,
Key,
Val,
NewAVL)

is true when OldAVL and NewAVL define the same finite function
except that OldAVL associates Key with Val and NewAVL doesn't
associate Key with any value and
Key is preceded by all other keys in OldAVL.
avl_map(
:Pred,
+AVL)

is true when AVL is an association tree, and for each Key,
if Key is associated with Value in AVL, Pred(Value) is true.
avl_map(
:Pred,
+OldAVL,
NewAVL)

is true when OldAVL and NewAVL are association trees of the
same shape, and for each Key, if Key is associated with Old in
OldAVL and with New in NewAVL, Pred(Old,New) is true.
Send feedback on this subject.