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)
avl_to_list(
+AVL,
-List)
is_avl(
+AVL)
@<
than any non-variable. 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)
avl_to_list/2
.
avl_range(
+AVL,
-Range)
avl_min(
+AVL,
-Key)
avl_min(
+AVL,
-Key,
-Val)
avl_max(
+AVL,
-Key)
avl_max(
+AVL,
-Key,
-Val)
avl_height(
+AVL,
-Height)
avl_size(
+AVL,
-Size)
portray_avl(
+AVL)
writeq/1
. The
point of this predicate is
to get AVL trees displayed nicely by print/1
.
avl_member(
?Key,
+AVL)
avl_fetch/2
or avl_fetch/3
for that).
The Keys are enumerated in ascending order.
avl_member(
?Key,
+AVL,
?Val)
avl_fetch/3
) for that.
The Keys are enumerated in ascending order.
avl_fetch(
+Key,
+AVL)
avl_fetch(
+Key,
+AVL,
-Val)
avl_member/2
or avl_member/3
for that).
avl_next(
+Key,
+AVL,
-Knext)
avl_next(
+Key,
+AVL,
-Knext,
-Vnext)
avl_fetch(
Knext,
Val,
Vnext)
.
avl_prev(
+Key,
+AVL,
-Kprev)
avl_prev(
+Key,
+AVL,
-Kprev,
-Vprev)
avl_fetch(
Kprev,
AVL,
Vprev)
.
avl_change(
+Key,
?AVL1,
?Val1,
?AVL2,
?Val2)
ord_list_to_avl(
+List,
-AVL)
list_to_avl/2
which takes O(N lg N).
list_to_avl(
+Pairs,
-AVL)
list_to_avl(Pairs, AVL) :- ( foreach(K-V,Pairs), fromto(empty,AVL0,AVL1,AVL) do avl_store(K, AVL0, V, AVL1) ).
avl_store(
+Key,
+OldAVL,
+Val,
+NewAVL)
avl_incr(
+Key,
+OldAVL,
+Inc,
+NewAVL)
avl_delete(
+Key,
+OldAVL,
-Val,
-NewAVL)
avl_del_min(
+OldAVL,
-Key,
-Val,
-NewAVL)
avl_del_max(
+OldAVL,
-Key,
-Val,
-NewAVL)
avl_map(
:Pred,
+AVL)
avl_map(
:Pred,
+OldAVL,
-NewAVL)