Kart (key alteration radix tree) is an associative array data structure based on Patricia / critbit / radix trees. The main advantage of a kart is to expand the applicability of Patricia trees to more kinds of key sets. Karts retain the ordering, running time, and storage space characteristics of Patricia trees.

The structure of a kart is the same as that of a Patricia tree. To store a
character string key in a tree, the key must be represented as a bit string.
Each character's numeric value is considered to be a sequence of bits, with
more significant bits occurring earlier in the sequence than less significant
bits. So the key “`Mario`

” is represented as
“`01001101 01100001 01110010 01101001 01101111`

”,
assuming the ASCII character set. (Spaces inserted for readability.) This
is not just a matter of low-level storage; the individual bits are
significant to the algorithm. A Patricia tree containing the keys
“`Green Shell`

”
“`Mario`

”,
“`Mushroom`

”, and
“`Rainbow Road`

”
would look like this:

3

4

“Rainbow Road”

01010010 01100001 01101001 01101110 01100010 01101111 01110111 00100000
01010010 01101111 01100001 01100100
“Green Shell”

01000111 01110010 01100101 01100101 01101110 00100000
01010011 01101000 01100101 01101100 01101100
11

“Mario”

01001101 01100001 01110010 01101001 01101111
“Mushroom”

01001101 01110101 01110011 01101000 01110010 01101111 01101111 01101101
An internal node specifies the index of the first bit at which the keys in
the left subtree differ from the keys in the right subtree. In this example,
all the keys have the first 3 bits the same. The bit at index 3 is where the
differences start; “`Rainbow Road`

” has a 1, so it
belongs in the right subtree of the root node, while all other keys have a 0,
so they belong in the left subtree. Within the left subtree, the next
difference among the remaining keys is at bit 4: “```
Green
Shell
```

” has a 0, so it goes on the left; the others have a 1, so
they go on the right. The last two keys differ at bit 11.
“`Mario`

” has a 0, so it goes on the left;
“`Mushroom`

” has a 1, so it goes on the right.

To search for the key “`Mario`

”, we start at the root
node, and inspect the bit specified in the node. Bit 3 in
“`Mario`

” is 0, so we recurse on the left subtree.
The node at the top of this subtree specifies bit index 4, so we inspect bit
4 of “`Mario`

”; it's 1, so we go to the right subtree.
This brings us to a node that specifies bit 11, which is 0 in
“`Mario`

”, so we go left. Now we arrive at a leaf,
which means this is the only remaining node where
“`Mario`

” might be in the tree. A full key comparison
with this node's key shows that the search key is in the tree.

An unsuccessful search ends either at a leaf with a mismatched key comparison, or at an internal node that has an index that exceeds the range of bits in the search key.

As a storage space optimization, we can replace all but one leaf with an upward link to an internal node, and store the leaf's key in the internal node. This way, there is only one kind of node, and only half as many nodes. Leaf links are detected when the pointed-to node's bit index is less than or equal to the pointing node's index; normally, when following links down the tree, indexes get larger.

The limitation here is that two keys cannot both be stored in the tree if one
is a prefix of the other. At the index where two keys differ, the tree can
only hold keys that have a 0 or 1 at the index, not any which end at the
index. This could be fixed by allowing internal tree nodes to have three
children, but that incurs a storage space penalty for all internal nodes. We
could also use a terminiation character to mark the end of all keys, but then
that character could not be used within a key. So instead, we can apply a
transformation to all keys. The transformed version of the key is not stored
anywhere in memory; individual bits are calculated on the fly. The
transformation works by inserting a 1 bit before each byte of the original
key, and appending a 0 bit after the last byte. The transformed version of
the key is used to search for a key and to decide where in the tree to store
a key. This way, the point at which “`Mario`

” and
“`Mario Circuit`

” differ is represented by a bit where
“`Mario`

” has 0 and “```
Mario
Circuit
```

” has 1:

4

5

“Rainbow Road”

101010010 101100001 101101001 101101110 101100010 101101111 101110111
100100000 101010010 101101111 101100001 101100100 0
“Green Shell”

101000111 101110010 101100101 101100101 101101110 100100000
101010011 101101000 101100101 101101100 101101100 0
13

45

“Mushroom”

101001101 101110101 101110011 101101000 101110010 101101111 101101111
101101101 0
“Mario”

101001101 101100001 101110010 101101001 101101111 0
“Mario Circuit”

101001101 101100001 101110010 101101001 101101111 100100000 101000011
101101001 101110010 101100011 101110101 101101001 101110100 0
The translated bit at position `pos`

in a key `k`

of
length `klen`

can be calculated as:

unsigned int bit(size_t pos, unsigned char const* k, size_t klen) { if (pos/(CHAR_BIT+1)>=klen) return 0; if (pos%(CHAR_BIT+1)==0) return 1; return (((unsigned int)k[pos/(CHAR_BIT+1)])>>(CHAR_BIT-pos%(CHAR_BIT+1)))&(unsigned int)1; }

Since the structure of the tree and the individual nodes is the same as in a
normal Patricia tree, there is no penalty in storage space. The
`bit()`

function runs in constant time, so there is also no
penalty in runtime complexity. For a tree of `N`

nodes with a
maximum key length of `k`

(`N=O(2`

),
worst-case tree traversal is ^{k})`O(N)`

(the tree may be very
unbalanced), but also `O(k)`

, since each step of the traversal
examines one new bit from the search key. The final full key comparison is
also `O(k)`

. (Analyses of other structures often ignore the cost
of key operations: hash table lookups are often described as being
`O(1)`

in the best case, but this really means `O(k)`

.)
The only penalty of karts, as compared to Patricia trees, is in maximum key
length—a key whose length is the maximum `size_t`

value, or
close to it, can no longer be used, since each key is inflated by (assuming
8-bit bytes) 12.5% in translated form, and the translated length would not be
representable in `size_t`

. In practice, keys of this length are
extremely unlikely.

Only two basic operations are needed on a data type to use it as a key. Each
value of the type must have a single, unique corresponding bit string
representation; one operation fetches the `N`

th bit of the bit
string for a given key value. The other finds the first bit where two keys
differ, or indicates that the keys are equal. No key's bit string
representation may be a prefix of another key's bit string. This can be
ensured by making the bit strings be of the same length for all key values,
or have inserted flag bits at each point where the bit string *might*
end to indicate whether it *does* end there. To support the widest
set of fast operations, the lexicographic order of the bit strings would
match the natural order of the key values. But if entries will always be
looked up using complete, exact keys, and iteration through entries need not
be in any particular order, then the lexicographical order of the bit strings
is not important.

Higher-dimensional compound values can also be used as keys. The
method given above of inserting flag bits indicating the presence of another
array element produces a unique bit string for a given list of element
values, even if the bit strings for different elements are of different
lengths, and even if the elements themselves are compound types. The
`bit()`

function will be more complicated with such complex keys.
The function calculating the `N`

th bit of the outermost array must
first figure out which of its elements to dispatch to, which requires knowing
the length of each element's bit string (a new required operation). Deciding
which element to dispatch to could then be done using a secondary Patricia
tree, keyed with the cumulative lengths of the bit strings of the array
elements. So we lose the simple `O(k)`

tree traversal time, but
the cost of a full key comparison rises even more, so karts remain attractive
compared to other ordered trees that use multiple full key comparisons per
traversal.

This is enough if the structure of all keys in a given tree will be the same, even if the keys are of different sizes. But if two keys may have different structures - being of different types themselves, or being compound types holding elements of different types in the same position - then the bit string for each element must first include a few bits to indicate which type of data is in this slot, followed by the bits encoding the data itself. Likewise for unions.

Bit strings for deep compound structures will grow even longer than for plain strings, with inflation due to inserted marker bits at each level. So the limit for key lengths at the innermost levels of these structures will drop further, or else will lead to using larger integer types as bit addresses.

Other transformations are possible for other kinds of keys. (Normalized) floating-point numbers can be represented like so:

- Negative infinity: all 0 bits.
- Positive infinity: all 1 bits.
- Finite negative numbers: 0, 1, the inverted bits of the exponent, and the inverted bits of the significand.
- Finite positive numbers: 1, 0, the bits of the exponent, and the bits of the significand.
- Zero: 1 followed by all 0 bits.

This encoding makes the lexicographic ordering of the bit strings match the numeric order. NaNs could be represented in a variety of ways, depending on where in the lexicographic order we want them to fall. A one-dimensional array of floating-point numbers could be handled similarly to strings above.

Bignums, like text strings, can be of arbitrary length. But unlike text
strings, they are “right-justified” instead of
“left-justified”. That is, for text strings, their most
significant bits are of equal rank for comparison purposes, and they could be
padded with zeros at the least significant end. For bignums, their
*least* significant bits are of equal rank, and they could be padded
with zeros at the *most* significant end. This makes bignums hard to
handle - if we designate the bit index where two bignums differ as an offset
from the most significant bit between the two of them, then that index will
have to be recalculated if we ever include another key that has more
significant bits than either of the first two.

To avoid this problem, we could use bit indexes that indicate *backward*
offsets from the *least significant end* of the bignums' bit strings.
This means indexes would decrease as we progress down the tree. In the key
transformation, all bit strings would be padded with infinitely many zeros at
the most significant end. Since the key
“`0`

” is considered identical to the key
“`x`

”, we wouldn't need to insert marker bits
to indicate where the key actually ends. However, creating a tree containing
bignum keys mixed with other key types, or compound keys with bignum
elements, is not handled by this bit string transformation.
`x`

Alternatively, we could use bit offsets from the most significant end, where all bit strings are padded out to a length equal to the maximum value of the type used to hold bit indexes. The padded bit strings are then all of the same length, so they can be considered “left-justified” as well as “right-justified”. This way, bit indexes increase as usual as we progress down the tree. But the bit string for a single bignum key occupies the entire space of bit indexes, so we still can't include bignums as elements of compound keys. We can, however, mix bignums with other key types by adding a type code at the beginning of the bit string, and padding bignums out a little less to make room.