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

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

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

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

在本节中，我们将了解什么是 Robin-Hood 哈希方案。此哈希是开放寻址技术之一。它试图通过使用更公平的冲突解决策略来均衡元素的搜索时间。在插入时，如果我们想在位置 xi 插入元素 x，并且已经有元素 y 放在 yj = xi，则两个元素中较新的必须移动。因此，如果 i ≤ j，我们将尝试在位置 xi+1、xi+2 等处插入 x。否则，我们将 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 = ... 阅读更多