Did you know ... Search Documentation:
rbtrees.pl -- Red black trees
PublicShow source

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 t(Nil, Tree), 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 red or black.

author
- Vitor Santos Costa, Jan Wielemaker, Samer Abdallah
See also
- "Introduction to Algorithms", Second Edition Cormen, Leiserson, Rivest, and Stein, MIT Press
Source rb_new(-Tree) is det
Create a new Red-Black tree Tree.
deprecated
- Use rb_empty/1.
Source rb_empty(?Tree) is semidet
Succeeds if Tree is an empty Red-Black tree.
Source rb_lookup(+Key, -Value, +Tree) is semidet
True when Value is associated with Key in the Red-Black tree Tree. The given Key may include variables, in which case the RB tree is searched for a key with equivalent, as in (==)/2, variables. Time complexity is O(log N) in the number of elements in the tree.
Source rb_min(+Tree, -Key, -Value) is semidet
Key is the minimum key in Tree, and is associated with Val.
Source rb_max(+Tree, -Key, -Value) is semidet
Key is the maximal key in Tree, and is associated with Val.
Source rb_next(+Tree, +Key, -Next, -Value) is semidet
Next is the next element after Key in Tree, and is associated with Val.
Source rb_previous(+Tree, +Key, -Previous, -Value) is semidet
Previous is the previous element after Key in Tree, and is associated with Val.
Source rb_update(+Tree, +Key, +NewVal, -NewTree) is semidet
Source rb_update(+Tree, +Key, ?OldVal, +NewVal, -NewTree) is semidet
Tree NewTree is tree Tree, but with value for Key associated with NewVal. Fails if it cannot find Key in Tree.
Source rb_apply(+Tree, +Key, :G, -NewTree) is semidet
If the value associated with key Key is Val0 in Tree, and if 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.
Source rb_in(?Key, ?Value, +Tree) is nondet
True when Key-Value is a key-value pair in red-black tree Tree. Same as below, but does not materialize the pairs.
rb_visit(Tree, Pairs), member(Key-Value, Pairs)
Source rb_insert(+Tree, +Key, ?Value, -NewTree) is det
Add an element with key Key and Value to the tree Tree creating a new red-black tree NewTree. If Key is a key in Tree, the associated value is replaced by Value. See also rb_insert_new/4.
Source rb_insert_new(+Tree, +Key, ?Value, -NewTree) is semidet
Add a new element with key Key and Value to the tree Tree creating a new red-black tree NewTree. Fails if Key is a key in Tree.
Source rb_delete(+Tree, +Key, -NewTree)
Source rb_delete(+Tree, +Key, -Val, -NewTree)
Delete element with key Key from the tree Tree, returning the value Val associated with the key and a new tree NewTree.
Source rb_del_min(+Tree, -Key, -Val, -NewTree)
Delete the least element from the tree Tree, returning the key Key, the value Val associated with the key and a new tree NewTree.
Source rb_del_max(+Tree, -Key, -Val, -NewTree)
Delete the largest element from the tree Tree, returning the key Key, the value Val associated with the key and a new tree NewTree.
Source rb_visit(+Tree, -Pairs)
Pairs is an infix visit of tree Tree, where each element of Pairs is of the form Key-Value.
Source rb_map(+T, :Goal) is semidet
True if call(Goal, Value) is true for all nodes in T.
Source rb_map(+Tree, :G, -NewTree) is semidet
For all nodes Key in the tree Tree, if the value associated with key Key is Val0 in tree Tree, and if 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.
Source rb_fold(:Goal, +Tree, +State0, -State) is det
Fold the given predicate over all the key-value pairs in Tree, starting with initial state State0 and returning the final state State. Pred is called as
call(Pred, Key-Value, State1, State2)
Source rb_clone(+TreeIn, -TreeOut, -Pairs) is det
`Clone' the red-back tree TreeIn into a new tree TreeOut with the same keys as the original but with all values set to unbound values. Pairs is a list containing all new nodes as pairs K-V.
Source rb_partial_map(+Tree, +Keys, :G, -NewTree)
For all nodes Key in Keys, if the value associated with key Key is Val0 in tree Tree, and if call(G,Val0,ValF) holds, then the value associated with Key in NewTree is ValF. Fails if or if call(G,Val0,ValF) is not satisfiable for all Val0. Assumes keys are not repeated.
Source rb_keys(+Tree, -Keys)
Keys is unified with an ordered list of all keys in the Red-Black tree Tree.
Source list_to_rbtree(+List, -Tree) is det
Tree is the red-black tree corresponding to the mapping in List, which should be a list of Key-Value pairs. List should not contain more than one entry for each distinct key.
Source ord_list_to_rbtree(+List, -Tree) is det
Tree is the red-black tree corresponding to the mapping in list List, which should be a list of Key-Value pairs. List should not contain more than one entry for each distinct key. List is assumed to be sorted according to the standard order of terms.
Source rb_size(+Tree, -Size) is det
Size is the number of elements in Tree.
Source is_rbtree(@Term) is semidet
True if Term is a valide Red-Black tree.
To be done
- Catch variables.
Source rb_update(+Tree, +Key, +NewVal, -NewTree) is semidet
Source rb_update(+Tree, +Key, ?OldVal, +NewVal, -NewTree) is semidet
Tree NewTree is tree Tree, but with value for Key associated with NewVal. Fails if it cannot find Key in Tree.
Source rb_delete(+Tree, +Key, -NewTree)
Source rb_delete(+Tree, +Key, -Val, -NewTree)
Delete element with key Key from the tree Tree, returning the value Val associated with the key and a new tree NewTree.