User:SmallSheepJoseph/X-fast trie
| X-fast trie | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 类型 | Trie | ||||||||||||||||||||||||||||
| 发明时间 | 1982 | ||||||||||||||||||||||||||||
| 发明者 | Dan Willard | ||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||
在计算机科学中， x-fast trie是一种用于存储有界域中的整数的数据结构。它支持精确查询和前置或后继查询，时间复杂度为O (n log M)，使用O(n log M)空间，其中n是存储值的数量， M是域中的最大值。该结构由Dan Willard于 1982 年提出， 同时提出的还有更复杂的y-fast trie 树，目的是提高van Emde Boas 树的空间使用率，同时保留O(n log M)查询时间。
结构
[编辑]
x-fast trie 是一种按位 trie ：一种二叉树，其中每个子树存储的二进制表示都以公共前缀开头的值。每个内部节点都标有其子树中值的公共前缀，通常，左子节点在前缀末尾添加 0，而右子节点添加 1。 0 到M之间的整数的二进制表示 − 1 使用⌈log 2 M ⌉ 位，因此 trie 的高度为O （log M）。
x-fast trie 中的所有值都存储在叶子节点中。仅当内部节点的子树中有叶子时才会存储。如果内部节点没有左子节点，它会存储指向其右子树中最小叶子的指针，称为后代指针。同样，如果它没有右孩子，它会将指向其左子树中最大叶子的指针存储起来。每个叶子节点都存储指向其前任节点和后继节点的指针，从而形成一个双向链表。最后，每个级别都有一个哈希表，其中包含该级别上的所有节点。这些哈希表共同构成了级别搜索结构 (LSS)。为了保证最坏情况的查询时间，这些哈希表应该使用动态完美哈希或布谷鸟哈希。
总空间使用量为O(n log M)，因为每个元素都有一个长度为O （log M）。[來源請求][需要引用]
操作
[编辑]与vEB树 (van Emde Boas tree)类似，x-fast 树支持有序关联数组的操作。这包括通常的关联数组操作，以及另外两个排序操作，前驅和後繼 ：
- 查找（ k ）：查找与给定键关联的值
- 尋找後繼（ k ）：查找具有大于或等于给定键的最小键的键/值对
- 尋找前驅（ k ）：查找小于或等于给定键的最大键的键/值对
- 插入（ k ， v ）：插入给定的键/值对
- 删除（ k ）：删除具有给定键的键/值对
寻找
[编辑]通过在LSS [0] 中查找k ，可以在常数时间内找到与数据结构中的键k关联的值，LSS [0] 是所有叶子上的哈希表。
例如，如果我们在上图中寻找 4，我们将执行以下步骤：
- 步骤1：将十进制4转换为二进制，即100。
- 第 2 步：从根开始，并尝试遵循到达每一级的路径。 100 的第一位数字是 1，因此沿着根的正确路径（1）到达节点“1”。
- 步骤3：重复步骤2，100的第二位是0，因此沿着节点“1”的左边路径（0）走到节点“10”。
- 步骤4：重复步骤3，100的第3位是0，因此沿着节点“10”左边的路径（0）走到节点“100”。
继任者和前任
[编辑]要找到键k的后继或前任，我们首先找到A k ，即k的最低祖先。这是 trie 中与k具有最长公共前缀的节点。为了找到A k ，我们在层级上执行二分查找。我们从h /2 级开始，其中h是 trie 的高度。在每一级，我们使用正确长度的前缀k来查询层级搜索结构中相应的哈希表。如果不存在具有该前缀的节点，我们就知道A k一定处于更高级别，并将搜索限制在这些级别上。如果具有该前缀的节点确实存在，则A k不能位于更高级别，因此我们将搜索限制在当前级别和较低级别。
一旦我们找到k的最低祖先，我们就知道它的一个子树中有叶子（否则它不会在字典树中），并且k应该在另一个子树中。因此，后代指针指向k的后继或前任。根据我们要寻找的对象，我们可能需要在链表中向前或向后移动一步，到达下一个或上一个叶子节点。
由于 trie 的高度为O （对数 M ），二分查找最低祖先需要O （log 日志 M ）时间。此后，可以在常数时间内找到后继或前任，因此总查询时间为O （log 日志 中号）。
例如，如果我们要寻找上图中 3 的前任，我们将执行以下步骤：
- 步骤1：将十进制4转换为二进制，即011。
- 第 2 步：从根开始，并尝试遵循到达每一级的路径。 011 的第一位数字是 0，因此沿着根的左侧路径（0）到达节点“0”。
- 步骤3：重复步骤2，011的第二位数字是1，因此尝试按照正确的路径（1）进行操作。但是，节点“0”没有正确路径，因此请按照指针指向节点“001”。
- 步骤4：001小于011，所以它代表011的前身。因此，3 的前身是 1（001）。
插入
[编辑]要插入一个键值对 ( k, v )，我们首先找到k的前任和后继。然后，我们为k创建一个新叶子节点，将其插入到后继节点和前任节点之间的叶子链表中，并赋予它一个指向v的指针。接下来，我们从根节点向下走到新叶子节点，沿途创建必要的节点，将它们插入到相应的哈希表中，并在必要时更新后代指针。
由于我们必须遍历 trie 的整个高度，因此这个过程需要O （log M ）时间。
删除
[编辑]要删除键k ，我们使用叶子上的哈希表找到它的叶子。我们将它从链接列表中删除，但要记住哪个是后继，哪个是前任。然后我们从叶子节点走到树的根节点，删除所有子树仅包含k的节点，并在必要时更新后代指针。过去指向k 的后代指针现在将指向k的后继或前任，具体取决于缺少哪个子树。
与插入类似，这需要O （log M ）的时间，因为我们必须遍历 trie 的每一层。
讨论
[编辑]Willard 引入 x-fast tries 主要是为了介绍y-fast tries ，它提供相同的查询时间，同时仅使用O ( n ) 空间，并允许在O (log 日志 M ）时间。
通过在各层级进行二分搜索之前使用指数搜索，并且不仅查询当前前缀x ，还查询其后继x + 1、x-fast tries 可以在O （log 日志 Δ ），其中Δ是查询值与其前任或后继值之间的差值。
参考
[编辑]引用错误：在<references>标签中name属性为“PaperWillard”的参考文献没有在文中使用
引用错误：在<references>标签中name属性为“PaperKementsietsidis”的参考文献没有在文中使用
引用错误：在<references>标签中name属性为“PaperBose”的参考文献没有在文中使用
<references>标签中name属性为“NotesSchulz”的参考文献没有在文中使用外部链接
[编辑][[Category:树结构]]