The standard library int_binary_map package implements maps from Ints keys to arbitrary value types. This is a pure (side-effect free) datastructure.
The implementation is based on Binary search trees of Bounded Balance, similar to NievergeltReingold, SIAM J. Computing 2 (1), March 1973. The main advantage of these trees is that they keep the size of the tree in the node, giving a constant time size operation.
The bounded balance criterion used is simpler than NR’s alpha. Simply, one subtree must not have more than ‘weight’ times as many elements as the opposite subtree. Rebalancing is guaranteed to reinstate the criterion for weight>2.23, but the occasional incorrect behaviour for weight=2 is not detrimental to performance.
The int_binary_map package implements the Map API.
The int_binary_map package source code is in src/lib/src/int-binary-map.pkg.
See also: int_red_black_map.
See also: int_list_map
See also: int_binary_set.
The above information is manually maintained and may contain errors.
Map?