|Did you know ...||Search Documentation:|
|library(rbtrees): Red black trees|
Red-Black trees are balanced search binary trees. They are named because nodes can be classified as either red or black. The code we include is based on "Introduction to Algorithms", second edition, by Cormen, Leiserson, Rivest and Stein. The library includes routines to insert, lookup and delete elements in the tree.
A Red black tree is represented as a term
where Nil is the Nil-node, a node shared for each nil-node in the tree.
Any node has the form
colour(Left, Key, Value, Right),
where colour is one of
Warning: instantiation of keys
Red-Black trees depend on the Prolog standard order of terms to organize the keys as a (balanced) binary tree. This implies that any term may be used as a key. The tree may produce wrong results, such as not being able to find a key, if the ordering of keys changes after the key has been inserted into the tree. The user is responsible to ensure that variables used as keys or appearing in a term used as key that may affect ordering are not unified, with the exception of unification against new fresh variables. For this reason, ground terms are safe keys. When using non-ground terms, either make sure the variables appear in places that do not affect the standard order relative to other keys in the tree or make sure to not unify against these variables as long as the tree is being used.
==)/2). Time complexity is O(log N) in the number of elements in the tree.
==)/2). This predicate may fail or give unexpected results if Key is not sufficiently instantiated.
rb_update(Tree, Key, NewVal, NewTree)but also unifies OldVal with the value associated with Key in Tree.
call(G,Val0,ValF)holds, then NewTree differs from Tree only in that Key is associated with value ValF in tree NewTree. Fails if it cannot find Key in Tree, or if
call(G,Val0,ValF)is not satisfiable.
rb_visit(Tree, Pairs), member(Key-Value, Pairs)
Leaves a choicepoint even if Key is instantiated; to avoid a choicepoint, use rb_lookup/3.
rb_delete(Tree, Key, NewTree), but also unifies Val with the value associated with Key in Tree.
call(Goal, Value)is true for all nodes in T.
call(G,Val0,ValF)holds, then the value associated with Key in NewTree is ValF. Fails if
call(G,Val0,ValF)is not satisfiable for all Val0. If G is non-deterministic, rb_map/3 will backtrack over all possible values from
call(G,Val0,ValF). You should not depend on the order of tree traversal (currently: key order).
call(Pred, Key-Value, State1, State2)
Determinism depends on Goal.
call(G,Val0,ValF)holds, then the value associated with Key in NewTree is ValF, otherwise it is the value associated with the key in Tree. Fails if Key isn't in Tree or if
call(G,Val0,ValF)is not satisfiable for all Val0 in Keys. Assumes keys are sorted and not repeated (fails if this is not true).