Represent a binary search tree by:Assume the provided For equality-type values, call
sml
datatype ('k, 'v) dict = Empty
| Branch of ('k, 'v) dict * 'k * 'v * ('k, 'v) dict;lookup d key returns NONE or SOME value, and update d (key, value) returns the updated binary search tree. Traverse the first dictionary, retaining only a key with the same value in the second:sml
fun intersection equal d1 d2 =
let
fun visit Empty result = result
| visit (Branch (left, key, value, right)) result =
let
val r1 = visit left result
val r2 =
case lookup d2 key of
NONE => r1
| SOME other =>
if equal (value, other)
then update r1 (key, value)
else r1
in
visit right r2
end
in
visit d1 Empty
end;intersection (op =) d1 d2. An explicit value comparison parameter also handles values for which Standard ML does not define built-in equality. This distinguishes absent keys from defined values without reserving a sentinel value.Every inserted entry belongs to both input dictionaries with the same value, so the result agrees with each. Conversely, each common equal-valued entry is visited in
d1, found in d2, and inserted. Any dictionary agreeing with both can contain only those entries. Thus the result is exactly the largest common dictionary, not merely an intersection of key sets. If d1 has entries, lookup height is , and maximum result-tree height during insertion is , the time complexity is for constant-cost comparisons. Logarithmic heights require a balancing assumption; an ordinary unbalanced binary search tree can have linear height. Articles by others on the same topic
There are currently no matching articles.