整数数据结构简介

位作为整数的一部分

在本模块中，我们回到实现 SSet 的问题。现在不同的是，我们假设存储在 SSet 中的元素是 $w$ 位整数。也就是说，我们需要实现 add(x)、remove(x) 和 find(x)，其中 $x \in \{0, ..., 2^w - 1\}$。不难想到许多应用场景中，数据——至少用于排序数据的关键字——是整数。

我们讨论三种数据结构，每一种都建立在前一种的基础上。第一种结构是 BinaryTrie，它在 $O(w)$ 时间内完成所有三个 SSet 操作。这并不算特别出色，因为 $\{0, ..., 2^w - 1\}$ 的任意子集大小 $n \leq 2^w$，所以 $log\ n \leq w$。其他 SSet 实现均能在 $O(\log n)$ 时间内完成所有操作，因此它们至少和 BinaryTrie 一样快。

第二种结构是 XFastTrie，它通过使用哈希来加速 BinaryTrie 中的搜索。借助这一优化，find(x) 操作可在 $O(\log w)$ 时间内完成。然而，在 XFastTrie 中，add(x) 和 remove(x) 操作仍需 $O(w)$ 时间，且 XFastTrie 所用空间为 $O(n \cdot w)$。

第三种数据结构是 YFastTrie，它使用 XFastTrie 仅存储大约每 w 个元素中的一个样本，并将剩余元素存储在一个标准的 SSet 结构中。这种技巧将 add(x) 和 remove(x) 的运行时间降低到 $O(\log w)$，并将空间减少到 $O(n)$。

示例中的实现可以存储任何类型的数据，只要能为其关联一个整数即可。在代码示例中，变量 ix 始终表示与 x 关联的整数值，方法 in.intValue(x) 将 x 转换为其关联的整数。但在文本中，我们将直接把 x 视作整数处理。

BinaryTrie：一种数字搜索树

BinaryTrie 将一组 $w$ 位整数编码在一个二叉树中。树中所有叶子节点的深度均为 $w$，每个整数都以从根到叶的路径来表示。整数 x 的路径在第 i 层向左转，如果 x 的第 $i$ 个最高位是 0；向右转，如果该位是 1。上图展示了 $w = 4$ 的情况，其中 trie 存储了整数 $3(0011)$、$9(1001)$、$12(1100)$ 和 $13(1101)$。

由于查找路径依赖于 x 的位，因此命名节点 u 的子节点为 u.child[0]（左）和 u.child[1]（右）会很有帮助。这些子指针实际上具有双重用途。由于二叉 trie 中的叶子节点没有子节点，这些指针被用来将叶子节点串成一个双向链表。对于二叉 trie 中的叶子节点 u，u.child[0]（prev）是指链表中位于 u 之前的节点，u.child[1]（next）是指链表中位于 u 之后的节点。一个特殊节点 dummy 被用作链表首尾的哨兵节点。

每个节点 u 还包含一个额外的指针 u.jump。如果 u 的左子节点缺失，则 u.jump 指向 u 子树中最小的叶子节点；如果 u 的右子节点缺失，则 u.jump 指向 u 子树中最大的叶子节点。下图展示了一个 BinaryTrie 的实例，包括跳跃指针和叶子节点处的双向链表。

BinaryTrie 中的 find(x) 操作相当直接。我们尝试沿着 x 的搜索路径在 trie 中前进。如果到达一个叶子节点，则找到了 x。如果到达一个节点 u 无法继续前进（因为 u 缺少某个子节点），则我们跟随 u.jump，这会将我们带到比 x 大的最小叶子节点或比 x 小的最大叶子节点。这两种情况取决于 u 缺少左子节点还是右子节点。前者（缺少左子节点）时，我们已找到目标节点；后者（缺少右子节点）时，我们可以利用链表到达目标节点。

可视化演示

下图展示了上述各种情况。

find() 方法的实现如下：

1class BinaryTrie(BaseSet):
2    class Node(object):
3        def __init__(self):
4            self.child  = new_array(2)
5            self.jump = None
6            self.parent = None
7            self.x = None
8
9    def find(self, x):
10        ix = int(x)
11        u = self.r
12        i = 0
13        while i < w:
14            c = (ix >> w-i-1) & 1
15            if u.child[c] is None: break
16            u = u.child[c]
17            i += 1
18        if i == w: return u.x  # 找到了
19        u = [u.jump, u.jump.next][c]
20        if u is self.dummy: return None
21        return u.x
22        

find(x) 方法的运行时间主要由沿根到叶路径的遍历决定，因此其时间复杂度为 $O(w)$。

add() 操作

BinaryTrie 中的 add(x) 操作也相对直接，但需要完成大量工作：

1. 它沿着 x 的搜索路径前进，直到到达一个无法继续前进的节点 u。
2. 它从 u 到包含 x 的叶子节点创建搜索路径的剩余部分。
3. 它将包含 x 的节点 u' 添加到叶子的双向链表中（它可以通过步骤1中遇到的最后一个节点 u 的跳跃指针访问 u' 的前驱 pred）。
4. 它沿 x 的搜索路径向上回溯，更新那些跳跃指针应指向 x 的节点的跳跃指针。

下图展示了添加值 2 和 15 的过程。

add() 方法的实现如下：

1class BinaryTrie(BaseSet):
2    class Node(object):
3        def __init__(self):
4            self.child  = new_array(2)
5            self.jump = None
6            self.parent = None
7            self.x = None
8
9    def add(self, x):
10        ix = int(x)
11        u = self.r
12        # 1 - 沿路径查找 ix，直到离开树
13        i = 0
14        while i < w:
15            c = (ix >> w-i-1) & 1
16            if u.child[c] is None: break
17            u = u.child[c]
18            i += 1
19        if i == w: return False  # 已包含 x - 终止
20        pred = [u.jump.prev, u.jump][c]
21        u.jump = None  # u 将很快有两个子节点
22        
23        # 2 - 添加到 ix 的路径
24        while i < w:
25            c = (ix >> w-i-1) & 1
26            u.child[c] = self._new_node()
27            u.child[c].parent = u
28            u = u.child[c]
29            i += 1
30        u.x = x
31            
32        # 3 - 将 u 添加到链表
33        u.prev = pred
34        u.next = pred.next
35        u.prev.next = u
36        u.next.prev = u
37        
38        # 4 - 向上回溯，更新跳跃指针
39        v = u.parent
40        while v is not None:
41            if (v.left is None  
42                    and (v.jump is None or int(v.jump.x) > ix)) \
43                or (v.right is None
44                    and (v.jump is None or int(v.jump.x) < ix)):
45                v.jump = u
46            v = v.parent
47        self.n += 1
48        return True
49    

该方法执行一次向下遍历搜索路径和一次向上回溯。每次步进耗时常数，因此 add(x) 方法的时间复杂度为 $O(w)$。

remove() 操作

remove(x) 操作撤销 add(x) 的工作。与 add(x) 一样，它也需要完成大量工作：

1. 它沿着 x 的搜索路径前进，直到到达包含 x 的叶子节点 u。
2. 它将 u 从双向链表中移除。
3. 它删除 u，然后沿 x 的搜索路径向上删除节点，直到到达一个子节点不在 x 搜索路径上的节点 v。
4. 它从 v 向上走到根节点，更新任何指向 u 的跳跃指针。

下图展示了移除值 9 的过程。

remove() 方法的实现如下：

1class BinaryTrie(BaseSet):
2    class Node(object):
3        def __init__(self):
4            self.child  = new_array(2)
5            self.jump = None
6            self.parent = None
7            self.x = None
8
9    def remove(self, x):
10        ix = int(x)
11        u = self.r
12        # 1 - 找到包含 x 的叶子节点 u
13        i = 0
14        while i < w:
15            c = (ix >> w-i-1) & 1
16            if u.child[c] is None: return False
17            u = u.child[c]
18            i += 1
19        
20        # 2 - 从链表中移除 u
21        u.prev.next = u.next
22        u.next.prev = u.prev
23        v = u
24        
25        # 3 - 删除路径上的节点
26        for i in range(w-1, -1, -1):
27            c = (ix >> w-i-1) & 1
28            v = v.parent
29            v.child[c] = None
30            if v.child[1-c] is not None: break
31            
32        # 4 - 更新跳跃指针
33        pred = u.prev
34        succ = u.next
35        v.jump = [pred, succ][v.left is None]
36        v = v.parent
37        while v is not None:
38            if v.jump is u:
39                v.jump = [pred, succ][v.left is None]
40            v = v.parent
41            
42        self.n -= 1
43        return True

定理：BinaryTrie 实现了 $w$ 位整数的 SSet 接口。BinaryTrie 在每次操作 add(x)、remove(x)、find(x) 上的时间复杂度为 $O(w)$。存储 $n$ 个值的 BinaryTrie 所用空间为 $O(n \cdot w)$。

现在我们创建一个 BinaryTrie 类的实例并对其进行简单测试。

1from utils import new_array, w, binfmt
2from base import BaseSet
3# 主类
4class BinaryTrie(BaseSet):
5    class Node(object):
6        def __init__(self):
7            self.child  = new_array(2)
8            self.jump = None
9            self.parent = None
10            self.x = None
11
12        @property
13        def left(self):
14            return self.child[0]
15
16        @left.setter
17        def left(self, u):
18            self.child[0] = u
19
20        @property
21        def right(self):
22            return self.child[1]
23
24        @right.setter
25        def right(self, u):
26            self.child[1] = u
27
28        @property
29        def prev(self):
30            return self.child[0]
31
32        @prev.setter
33        def prev(self, u):
34            self.child[0] = u
35
36        @property
37        def next(self):
38            return self.child[1]
39
40        @next.setter
41        def next(self, u):
42            self.child[1] = u
43            
44        def __str__(self):
45            return "{" + str(self.x) + "}"
46    # 创建新节点的函数
47    def _new_node(self):
48        return BinaryTrie.Node()
49    # 初始化函数
50    def __init__(self):
51        super(BinaryTrie, self).__init__()
52        self._initialize()
53        
54    def _initialize(self):
55        self.dummy = self._new_node()
56        self.dummy.prev = self.dummy.next = self.dummy
57        self.r = self._new_node()
58        self.r.jump = self.dummy
59        self.n = 0
60    # 重置值的函数
61    def clear(self):
62        self._initialize()
63    # 添加值的函数   
64    def add(self, x):
65        ix = int(x)
66        u = self.r
67        # 1 - 沿路径查找 ix，直到离开树
68        i = 0
69        while i < w:
70            c = (ix >> w-i-1) & 1
71            if u.child[c] is None: break
72            u = u.child[c]
73            i += 1
74        if i == w: return False  # 已包含 x - 终止
75        pred = [u.jump.prev, u.jump][c]
76        u.jump = None  # u 将很快有两个子节点
77        
78        # 2 - 添加到 ix 的路径
79        while i < w:
80            c = (ix >> w-i-1) & 1
81            u.child[c] = self._new_node()
82            u.child[c].parent = u
83            u = u.child[c]
84            i += 1
85        u.x = x
86            
87        # 3 - 将 u 添加到链表
88        u.prev = pred
89        u.next = pred.next
90        u.prev.next = u
91        u.next.prev = u
92        
93        # 4 - 向上回溯，更新跳跃指针
94        v = u.parent
95        while v is not None:
96            if (v.left is None  
97                    and (v.jump is None or int(v.jump.x) > ix)) \
98                or (v.right is None
99                    and (v.jump is None or int(v.jump.x) < ix)):
100                v.jump = u
101            v = v.parent
102        self.n += 1
103        return True
104    # 查找值的函数
105    def find(self, x):
106        ix = int(x)
107        u = self.r
108        i = 0
109        while i < w:
110            c = (ix >> w-i-1) & 1
111            if u.child[c] is None: break
112            u = u.child[c]
113            i += 1
114        if i == w: return u.x  # 找到了
115        u = [u.jump, u.jump.next][c]
116        if u is self.dummy: return None
117        return u.x
118    # 删除值的函数 
119    def remove(self, x):
120        ix = int(x)
121        u = self.r
122        # 1 - 找到包含 x 的叶子节点 u
123        i = 0
124        while i < w:
125            c = (ix >> w-i-1) & 1
126            if u.child[c] is None: return False
127            u = u.child[c]
128            i += 1
129        
130        # 2 - 从链表中移除 u
131        u.prev.next = u.next
132        u.next.prev = u.prev
133        v = u
134        
135        # 3 - 删除路径上的节点
136        for i in range(w-1, -1, -1):
137            c = (ix >> w-i-1) & 1
138            v = v.parent
139            v.child[c] = None
140            if v.child[1-c] is not None: break
141            
142        # 4 - 更新跳跃指针
143        pred = u.prev
144        succ = u.next
145        v.jump = [pred, succ][v.left is None]
146        v = v.parent
147        while v is not None:
148            if v.jump is u:
149                v.jump = [pred, succ][v.left is None]
150            v = v.parent
151            
152        self.n -= 1
153        return True
154    # 检查以 u 为根的子树的一致性（深度为 d）
155    def _check(self):
156        u = self.dummy.next
157        i = 0
158        while u is not self.dummy:
159            assert(u.next.prev is u)
160            u = u.next
161            i += 1
162        assert(i == self.n)
163        self._check_it()  
164    # 辅助函数
165    def _check_it(self, u=None, d=0, prefix=0):
166        if u is None: u = self.r
167        if d == w:
168            assert(u.x == prefix)
169        else:
170            assert(u is self.r or u.left is not None or u.right is not None)
171            if u.left is None and u.right is not None:
172                # TODO: 检查 u.jump.x 是否符合 prefix
173                val = prefix << w-d-1
174                assert(u.jump.x is not None)
175                assert(u.jump.x >> w-d == prefix)
176                assert(u.jump.x >> w-d-1 == (prefix << 1)|1)
177            if u.right is None and u.left is not None:
178                assert(u.jump.x is not None)
179                assert(u.jump.x >> w-d == prefix)
180                assert(u.jump.x >> w-d-1 == (prefix << 1))
181            if u.left is not None and u.right is not None:
182                assert(u.jump is None)
183            if u.left is not None:
184                self._check_it(u.left, d+1, prefix << 1)
185            if u.right is not None:
186                self._check_it(u.right, d+1, (prefix << 1) | 1)
187    # 迭代器函数
188    def __iter__(self):
189        u = self.dummy.next
190        while u != self.dummy:
191            yield u.x
192            u = u.next
193
194if __name__ == "__main__":
195    bt = BinaryTrie()
196    # 添加值
197    bt.add(5)
198    bt.add(3)
199    bt.add(8)
200    bt.add(7)
201    bt.add(2)
202    bt.add(1)
203    
204    print("添加 5, 3, 8, 7, 2 和 1 后的 Binary Trie：")
205    print(bt)
206    
207    print("查找 5: ", bt.find(5))
208    print("查找 2: ", bt.find(2))
209    print("查找 10: ", bt.find(10))
210    # 删除值
211    bt.remove(5)
212    bt.remove(7)
213    bt.remove(1)
214    
215    print("删除 5, 7 和 1 后的 Binary Trie：")
216    print(bt)
217    
218    print("查找 5: ", bt.find(5))
219    print("查找 7: ", bt.find(7))
220    print("查找 1: ", bt.find(1))

说明

让我们从 main() 开始解释。

• 第 195 行：创建一个新的 BinaryTrie 类实例并存储在变量 bt 中。BinaryTrie 类设计用于使用二叉 trie 数据结构存储整数集合。

• 第 197–202 行：通过调用 bt 上的 add() 方法将整数 5、3、8、7、2 和 1 添加到二叉 trie 中。每次调用 add() 都会在二叉 trie 中创建一个新节点，并将要添加的整数插入到 trie 中。

• 第 207–209 行：调用 bt 上的 find() 方法来搜索值 5、2 和 10。find() 方法在二叉 trie 中搜索指定值的节点，若找到则返回 True，否则返回 False。

• 第 211–213 行：通过调用 bt 上的 remove 方法将整数 5、7 和 1 从二叉 trie 中移除。每次调用 remove() 都会从二叉 trie 中移除指定值的节点。

• 第 218–220 行：再次调用 find() 方法在更新后的二叉 trie 中搜索值 5、7 和 1。由于这些值已在上一步中被移除，因此 find() 方法对每个值都将返回 False。