YAP 7.1.0
Red-Black Trees

More...

## Detailed Description

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=

## ◆ rb_new/1

 class rb_new/1

rb_new(-T)

rb_new(? T)

properties: deterministic

create an empty tree % % Create a new Red-Black tree % %

Deprecated:
Use rb_empty/1

Create a new tree

## ◆ rb_empty/1

 class rb_empty/1

rb_empty(?T)

rb_empty(? T)

properties: semideterministic

% % Succeeds if T is an empty Red-Black tree

Succeeds if tree T is empty

## ◆ rb_lookup/3

 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

## ◆ rb_min/3

 class rb_min/3

rb_min(+T, -Key, -Value)

rb_min(+ T,- Key,- Value)

properties: semideterministic

% % Key is the minimum key in T, and is associated with Val

Key is the minimum key in T, and is associated with Val

## ◆ rb_max/3

 class rb_max/3

rb_max( +T, -Key, -Value)

rb_max(+ T,- Key,- Value)

properties: semideterministic

% % Key is the maximal key in T, and is associated with Val

Key is the maximal key in T, and is associated with Val

## ◆ rb_next/4

 class rb_next/4

rb_next(+T, +Key, -Next,-Value)

rb_next(+ T, + Key,- Next,- Value)

properties: semideterministic

% % Next is the next element after Key in T, and is associated with % Val

Next is the next element after Key in T, and is associated with Val

## ◆ rb_previous/4

 class rb_previous/4

rb_previous(+T, +Key, -Previous, -Value)

rb_previous(+ T, + Key,- Previous,- Value)

properties: semideterministic

% % Previous is the previous element after Key in T, and is % associated with Val

Previous is the previous element after Key in T, and is associated with Val

## ◆ rb_update/4

 class rb_update/4

rb_update(+T, +Key, +NewVal, -TN)

rb_update(+ T,+ Key,+ NewVal,- TN)

properties: semideterministic

%%

Tree TN is tree T, but with value for Key associated with NewVal Fails if it cannot find Key in T

## ◆ rb_update/5

 class rb_update/5

rb_update(+T, +Key, ?OldVal, +NewVal, -TN)

properties: semideterministic

% % Tree TN is tree T, but with value for Key associated with % NewVal Fails if it cannot find Key in T

## ◆ rb_rewrite/3

 class rb_rewrite/3

rb_rewrite(+T, +Key, +NewVal)

properties: semideterministic

%%

## ◆ rb_rewrite/4

 class rb_rewrite/4

rb_rewrite(+T, +Key, ?OldVal, +NewVal)

properties: semideterministic

% % Tree T has value for Key associated with % NewVal Fails if it cannot find Key in T

## ◆ rb_apply/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

## ◆ rb_delete/3

 class rb_delete/3

rb_delete(+T, +Key, -TN)

rb_delete(+ T,+ Key,- TN)

%%

Delete element with key Key from the tree T, returning a new tree TN

## ◆ rb_delete/4

 class rb_delete/4

rb_delete(+T, +Key, -Val, -TN)

rb_delete(+ T,+ Key,- Val,- TN)

% % Delete element with key Key from the tree T, returning the value % Val associated with the key and a new tree TN

Delete element with key Key from the tree T, returning the value Val associated with the key and a new tree TN

## ◆ rb_del_min/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

## ◆ rb_del_max/4

 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

## ◆ rb_clone/3

 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

## ◆ rb_fold/4

 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

## ◆ rb_insert/4

 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

## ◆ rb_key_fold/4

 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

## ◆ rb_keys/2

 class rb_keys/2

rb_keys(+ T,+ Keys)

Keys is an infix visit with all keys in tree T Keys will be sorted, but may be duplicate

## ◆ rb_lookupall/3

 class rb_lookupall/3

rb_lookupall(+ Key,- Value,+ T)

Lookup all elements with key Key in the red-black tree T, returning the value Value

## ◆ rb_map/3

 class rb_map/3

rb_map(+ T,+ G,- TN)

For all nodes Key in the tree T, if the value associated with key Key is Val0 in tree T, and if `call(G,Val0,ValF)` holds, then the value associated with Key in TN is ValF Fails if or if `call(G,Val0,ValF)` is not satisfiable for all Var0

## ◆ rb_partial_map/4

 class rb_partial_map/4

rb_partial_map(+ T,+ Keys,+ G,- TN)

For all nodes Key in Keys, if the value associated with key Key is Val0 in tree T, and if `call(G,Val0,ValF)` holds, then the value associated with Key in TN is ValF Fails if or if `call(G,Val0,ValF)` is not satisfiable for all Var0 Assumes keys are not repeated

## ◆ rb_size/2

 class rb_size/2

rb_size(+ T,- Size)

Size is the number of elements in T

## ◆ rb_visit/2

 class rb_visit/2

rb_visit(+ T,- Pairs)

Pairs is an infix visit of tree T, where each element of Pairs is of the form K- Val