blob: 455995046a2b4eb4c737fa4994d5bcbd8e922a59 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
# Data Structures for Integers
## BinaryTrie: A digital search tree
encodes a set of `w` bit integers in a binary tree.
* all leaves have depth `w`.
* each integer is encoded as a root-to-leap path.
The path for the int `x` trusn left at level `i` if the `ith`
msb of `x` is a `0` and turns right if it is a `1`.
* 3 -> 0011
* 9 -> 1001
* 12 -> 1100
* 13 -> 1101
```plaintext
(****)
/ \
(0***) (1***)
/ / \
(00**) (10**) (11**)
\ / /
(001*) (100*) (110*)
\ \ / \
(3:0011) (9:1001) (12:1100) (13:1101)
```
```java
T find(T x) {
int i, c = 0, ix = it.intValue(x);
Node u = r;
for (i = 0; i < w; i++) {
c = (ix >>> w-i-1) & 1;
if (u.child[c] == null) break;
u = u.child[c];
}
if (i == w) return u.x;
u = (c == 0) ? u.jump : u.jump.child[next];
return u == dummy ? null : u.x;
}
```
|
