 |
YAP 7.1.0
|
|
YAP 7.1.0
|
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=
| class rb_new/1 |
| class rb_empty/1 |
| class rb_lookup/3 |
rb_lookup(+Key, -Value, +T)
rb_lookup(+ Key,- Value,+ T)
properties: semideterministic
% % Backtrack through all elements with key Key in the Red-Black % tree T, returning for each the value Value
Backtrack through all elements with key Key in the red-black tree T, returning for each the value Value
| class rb_min/3 |
| class rb_max/3 |
| class rb_next/4 |
| class rb_previous/4 |
| class rb_update/4 |
| class rb_update/5 |
| class rb_rewrite/3 |
| class rb_rewrite/4 |
| class rb_apply/4 |
rb_apply(+T, +Key, :G, -TN)
rb_apply(+ T,+ Key,+ G,- TN)
properties: semideterministic
% % If the value associated with key Key is Val0 in T, and if % call(G,Val0,ValF) holds, then TN differs from T only in that Key % is associated with value ValF in tree TN Fails if it cannot % find Key in T, or if call(G,Val0,ValF) is not satisfiable
If the value associated with key Key is Val0 in T, and if call(G,Val0,ValF) holds, then TN differs from T only in that Key is associated with value ValF in tree TN Fails if it cannot find Key in T, or if call(G,Val0,ValF) is not satisfiable
| class rb_delete/3 |
| class rb_delete/4 |
| class rb_del_min/4 |
rb_del_min(+T, -Key, -Val, -TN)
rb_del_min(+ T,- Key,- Val,- TN)
% % Delete the least element from the tree T, returning the key Key, % the value Val associated with the key and a new tree TN
Delete the least element from the tree T, returning the key Key, the value Val associated with the key and a new tree TN
| class rb_del_max/4 |
rb_del_max( +T, -Key, -Val, -TN)
rb_del_max(+ T,- Key,- Val,- TN)
% % Delete the largest element from the tree T, returning the key % Key, the value Val associated with the key and a new tree TN
Delete the largest element from the tree T, returning the key Key, the value Val associated with the key and a new tree TN
| class rb_clone/3 |
rb_clone(+ T,+ NT,+ Nodes)
=Clone= the red-back tree into a new tree with the same keys as the original but with all values set to unbound values Nodes is a list containing all new nodes as pairs K-V
| class rb_fold/4 |
rb_fold(+ T,+ G,+ Acc0, - AccF)
For all nodes Key in the tree T, if the value associated with key Key is V in tree T, if call(G,V,Acc1,Acc2) holds, then if VL is value of the previous node in inorder, call(G,VL,_,Acc0) must hold, and if VR is the value of the next node in inorder, call(G,VR,Acc1,_) must hold
| class rb_insert/4 |
rb_insert(+ T0,+ Key,? Value,+ TF)
Add an element with key Key and Value to the tree T0 creating a new red-black tree TF Duplicated elements are not allowed
Add a new element with key Key and Value to the tree T0 creating a new red-black tree TF Fails is an element with Key exists in the tree
| class rb_key_fold/4 |
rb_key_fold(+ T,+ G,+ Acc0, - AccF)
For all nodes Key in the tree T, if the value associated with key Key is V in tree T, if call(G,Key,V,Acc1,Acc2) holds, then if VL is value of the previous node in inorder, call(G,KeyL,VL,_,Acc0) must hold, and if VR is the value of the next node in inorder, call(G,KeyR,VR,Acc1,_) must hold
| class rb_keys/2 |
| class rb_lookupall/3 |
| class rb_map/3 |
| class rb_partial_map/4 |
1.9.3