Certified Map

This package provides a map that can be used by Internet Computer canisters to implement certified queries.

Features

Implementation Details

The canister uses an augmented Red-Black binary search tree to store the entries. Each node of the search tree is annotated with the root hash of the hash tree built from the subtree rooted at this node. Each time the tree is rotated or modified, the corresponding hashes are recomputed in O(1) time.