在这里，我们将了解 R 树数据结构。R 树用于高效地存储特殊数据索引。这种结构对于保存特殊数据查询和存储非常有用。R 树有一些现实生活中的应用，例如：多维信息的索引；游戏数据的处理；地理空间坐标的保存；虚拟地图的实现。下面是一个 R 树的例子。相应的 R 树如下所示：R 树的特性：R 树由单个根节点、内部节点和叶节点组成；根节点指向特殊域中最大的区域；父节点包含子节点，其中子节点完全重叠…… 阅读更多

在这里，我们将了解 B 树。B 树是一种专门的 m 叉搜索树，广泛用于磁盘访问。m 阶 B 树最多可以有 m-1 个键和 m 个子节点。它可以在单个节点中存储大量元素，因此高度相对较小。这是 B 树的一大优势。B 树具有 m 叉树的所有属性，还有一些其他属性：B 树中的每个节点最多包含 m 个子节点；除根节点和叶节点外，每个节点至少包含 m/2 个子节点；根节点至少必须有两个…… 阅读更多

合并算法用于将两个已排序的列表合并成一个列表。此算法在不同情况下使用。如果我们想要执行归并排序，那么我们需要将排序后的列表合并成更大的列表。方法很简单。我们取两个列表，有两个指针。第一个指向第一个列表的元素，第二个指向第二个列表的元素。根据它们的值，较小的元素从这两个列表中的一个中取出，然后增加相应列表的指针。此操作将…… 阅读更多

当我们尝试实现抽象数据类型字典时，节点与值关联。字典基本上是一组键，这些键必须是从全序中提取的元素。可能还有其他信息与每个键相关联，但这不会带来任何概念上的理解。如果字典使用树来实现，那么每个节点将保存唯一的键。这里对于树中的每个节点 u，每个键 u.l 都严格小于 u.k。并且 u.r 中的每个键都严格大于 u.k。树根据此不变量进行组织…… 阅读更多

在本节中，我们将了解 Robin Hood 哈希方案。这种哈希是开放寻址技术之一。它尝试通过使用更公平的冲突解决策略来均衡元素的搜索时间。当我们尝试插入元素 x 到位置 xi 时，如果位置 xi 已经存在元素 y，yj = xi，那么两个元素中较新的必须移动。因此，如果 i ≤ j，我们将尝试将 x 插入到位置 xi+1、xi+2 等。否则，我们将 x 存储在…… 阅读更多

在本节中，我们将了解 LCFS 哈希。这是开放寻址策略之一，它改变了冲突解决策略。如果我们检查开放寻址方案中哈希的算法，我们可以发现如果两个元素发生冲突，那么优先级较高的元素将被插入到表中，后续元素必须移动。因此，我们可以说开放寻址方案中的哈希是 FCFS 准则。使用 LCFS（后进先出）方案，任务的执行方式正好相反。当我们插入一个元素时，它将被放置在…… 阅读更多

在本节中，我们将了解非对称哈希技术。在这种技术中，哈希表被分成 d 个块。每个块的长度为 n/d。探测值 xi，0 ≤ i ≤ d，是从 $$\lbrace\frac{i*n}{d}, ..., \frac{(i+1)*n}{d-1}\rbrace$$中均匀抽取的。与多重选择哈希一样，要插入 x，算法检查列表 A[x0]、A[x1]、……、A[xd – 1] 的长度。然后将 x 附加到这些列表中最短的列表中。如果出现平局，则将其插入到索引最小的列表中。根据 Vocking 的说法，预期长度为…… 阅读更多

在这里，我们将了解平衡二叉搜索树。二叉搜索树 (BST) 是二叉树，其左子节点的元素小于根节点，右子节点的元素大于根节点。在 BST 中搜索元素的平均时间复杂度为 O(log n)。这取决于二叉搜索树的高度。为了保持二叉搜索树的属性，有时树会变得倾斜。因此，倾斜的树将如下所示：这实际上是一棵树，但这看起来像一个链表。对于这种类型的树，搜索时间将为…… 阅读更多

在本节中，我们将了解与开放寻址哈希相关的 Brent 方法。此方法是一种启发式方法。它试图最小化在哈希表中成功搜索的平均时间。此方法最初应用于双重哈希技术，但它可以用于任何开放寻址技术，例如线性探测和二次探测。存储在开放寻址哈希表中的元素 x 的年龄是 i 的最小值，这样 x 就被放置在 A[xi] 中。Brent 方法试图最小化所有元素的总年龄。如果我们插入一个元素 x，…… 阅读更多

在本节中，我们将了解开放寻址方案中的双重哈希技术。有一个普通的哈希函数 h´(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，当空间不为空时，实际的哈希函数 h(x) 使用普通的哈希函数 h’(x)，然后执行另一个哈希函数以获得一些空间进行插入。$$h_{1}(x)=x\:mod\:m$$$$h_{2}(x)=x\:mod\:m^{\prime}$$$$h(x, i)=(h^{1}(x)+ih^{2})\:mod\:m$$i 的值为 0, 1, . . ., m – 1。因此，我们从 i = 0 开始，并增加它，直到我们获得一个空闲空间。因此，最初当 i =…… 阅读更多