Searching and inserting in $O(n)$ when $n$ is the size of the key

Question

Edit: The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a trie can search $w$ in $O(n)$ and insert or delete $w$ in $O(|A| n)$. Since in my case $|A|=2$, all these operations are performed in $O(n)$. Hooray !

Context :

I am trying to put an upper bound on the worst case complexity of an algorithm. In that algorithm, I have an arbitrarily big positive integer $n$, and a map in which keys are sequences of bits of length $n$. My algorithm makes use of the INSERT and SEARCH operations in that map. So I am searching for a data structure with the least possible worst case complexity (with respect to $n$) for INSERT and SEARCH.

My first idea was : let's assume that the map is implemented with a red-black tree. Red-black trees perform SEARCH and INSERT in $O(\log m)$ (where $m$ is the number of nodes in the tree). In the context of my algorithm, there is at most $2^n$ different keys, so insert and search should run in $O(n)$.

Problem :

Binary trees usually assume that the keys are integers, which allows to compare two keys in $O(1)$. But since $n$ is not bounded, the length of my sequences can be greater than the encoding size of integers ; then it does not seem correct to just consider that my key can simply be treated as integers and compared in $O(1)$, right?

Question:

Do there exist data structures that would allow me to insert and search in $O(n)$ (worst case) with respect to the size $n$ of the key ?

What I have for now:

1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

2: I have come up with a very simple kind of tree that would perform INSERT and SEARCH in $O(n)$, and I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it). My solution goes like this :

• Keys are only stored in the leaves of the tree, and leaves are at distance $n$ from the root
• When searching or inserting, we recursively go down from the root ; on any given non-leaf node that is at distance $i$ from the root, we look at the $i$-th bit of our key : if it is 1 then go right, if it is 0 then go left.

I did not find any data structure based on this principle, but if it exists, that would be a good solution to my problem.

Answer 1

I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).

What you describe is called a trie. For practical implementation you might take more than one bit at each level (e.g. take two bits and give each node four children).

---

1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

There is potentially room for some subtlety here. If you record for each child node the bit index at which its key differs from the parent's, can you get it down to $O(n)$? I haven't thought through the answer myself, but it seems plausible that you'd essentially get a self-balancing trie-like structure, and might be an interesting exercise to attempt.

---

Finally, if you expect your map to be sparsely populated (i.e. to have much fewer than $2^n$ elements) it might be worth thinking about hashing.