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 Key-Value 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 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)

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, AVL, 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 Key-Val 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 proper list of Key-Val 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. Could be defined as:

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)

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, +Incr, +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.