prolog::rb_insert_new/4¶

Cormen et al present the algorithm as% (1) standard tree insertion;% (2) from the viewpoint of the newly inserted node:% partially fix the tree;% move upwards% until reaching the root.

%% We do it a little bit different:%% (1) standard tree insertion;% (2) move upwards:% when reaching a black node;% if the tree below may be broken, fix it.% We take advantage of Prolog unification% to do several operations in a single go.% actual insertion% rb_insert_new(+T0, +Key, ?Value, -TN) is semidet.%% Add a new element with key Key and Value to the tree T0 creating a% new red-black tree TN. Fails if Key is a key in T0.

(undocumented)

Private-func:¶

1. prolog::rb_insert_new_4::rb_insert_new/4(int ARG1, int ARG2, int ARG3, int ARG4)():