Bitwise trie with bitmap

A trie is a type of search tree where – unlike for example a B-tree – keys are not stored in the nodes but in the path to leaves.

In a "classic" trie, each node with its child-branches represents one symbol of the alphabet of one position (character) of a key.

There are multiple straight forward approaches to implement such a trie as physical data structure.

To state two: These approaches get worse for larger alphabets, if, for example, the key is a string of Unicode characters.

Bagwell[1] presented a time and space efficient solution for tries named Array Mapped Tree (AMT).

With 64-Bit-CPUs (64-bit computing) a variation is to have a 64-ary trie with only one 64-bit bitmap per node that is able to represent a 6 bit sequence.

In this example implementation for a bitwise trie with bitmap, nodes are placed in an array of long (64-bit) integers.

In addition, nodes, that are replaced, are collected in free lists and their space is recycled.

Set operators for intersection (and), union (or) and difference (minus) are feasible using a flyweight pattern as shown below.

Nonrelevant child nodes don't have to be accessed because the bitmap and a bitwise AND operation allows to determine the result upfront.

, lay in certain range, say [10..50], instead of iterating through the set and checking each entry, this is performed by evaluating