Come strutturare un trie bit a bit per eseguire una query di intervallo

Mi chiedo come eseguire una query di intervallo su un trie bit a bit .

Quindi dì che ho un trie come questo.

▲ Black (any shape) is 0.
△ White (any shape) is 1.
■ Black square means there is no value associated with that 0.
□ White square means there is no value associated with that 1.
● Black circle means there is a value associated with the 0.
○ White circle means there is a value associated with the 1.

                      x
         _____________|___________
        |                         |
     ___●___                   ___□___
    |       |                 |       |
   _■      _○                _■       □_
  |       |                 |           |
 _■     __■__           ____●___        ○____
|      |     |         |        |            |
●      ●     □_        ●       _○_        ___□
               |              |   |      |
               ○              ●   ○    __■
                                      |
                                      ●

Quindi abbiamo questi valori:

binary  symbol         decimal
0       (●)            0
0000    (● ■ ■ ●)      0
01      (● ○)          1
0100    (● ○ ■ ●)      4
01011   (● ○ ■ □ ○)    11
100     (□ ■ ●)        4
1000    (□ ■ ● ●)      8
1001    (□ ■ ● ○)      9
10010   (□ ■ ● ○ ●)    18
10011   (□ ■ ● ○ ○)    19
111     (□ □ ○)        7
111100  (□ □ ○ □ ■ ●)  60

Quindi trovare una corrispondenza data una stringa di query è piuttosto semplice. Basta controllare ciascun nodo e andare a sinistra o a destra.

Ma la domanda è, come trovare un intervallo di valori (penso che questo sia intervallo di query ).

Ho pensato che potessi fare questo:

1. Data una query di intervallo di start e end interi (sequenze di bit),
2. Attraversa l'albero per abbinare il nodo start .
3. Quindi spostati lungo un elenco collegato di tutti i nodi foglia finché non trovi il nodo >= end .

Quindi diciamo che stiamo cercando tra 0100 (● ○ ■ ●) (4 in decimale) e 1001 (□ ■ ● ○) (9 in decimale).

                      x
         _____________|___________
        |                         |
     ___●̥___                   ___□̥___
    |       |                 |       |
   _■      _○̥                _■̥       □_
  |       |                 |           |
 _■     __■̥__           ____●̥___        ○____
|      |     |         |        |            |
●      ●̥     □_        ●       _○̥_        ___□
               |              |   |      |
               ○              ●   ○    __■
                                      |
                                      ●

Troviamo il primo cercando 4 ( 0100 (● ○ ■ ●) ) scorrendo come normale. Ora la domanda è: come attraversiamo l'albero da sinistra a destra per fare la query sull'intervallo. Non sono nemmeno sicuro di quali vogliamo nel set di risultati finali.

Credo che una cosa che è sbagliata sia il numero di bit. I valori nel trie dovrebbero probabilmente essere unici (mentre attualmente ci sono 2 4 e 2 0). Ma mi piacerebbe che i numeri più piccoli usino meno bit, quindi non devo semplicemente tenere conto di numeri molto grandi come i numeri a 64 bit e devo fare 64 ricerche per ogni articolo. Se è 0 o 1, dovrebbe idealmente essere 1 ricerca. Allo stesso modo, se è 128 < x < 256 dovrebbe usare 8 bit o 8 ricerche. Ciò comporterebbe comunque un trie con nodi su più livelli. La domanda rimane, come creare la lista concatenata tra i nodi per facilitare una query di intervallo.