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

当我们尝试实现抽象数据类型字典时，节点与值相关联。字典基本上是一组键，这些键必须是从全序中提取的元素。可能还有其他信息与每个键相关联，但这不会导致任何概念上的理解。如果字典使用树实现，则每个节点将保存唯一的键。这里对于树中的每个节点 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 的年龄是使 x 放在 A[xi] 的最小值 iBrent 方法试图最小化所有元素的总年龄。如果我们插入一个元素 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 = ... 阅读更多

在本节中，我们将了解开放寻址方案中的二次探测技术。有一个普通的哈希函数 h’(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数 h(x) 采用普通的哈希函数 h’(x) 并附加一些其他部分以构成一个二次方程。h´ = (𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑 𝑚我们也可以使用一些常数放置其他二次方程i 的值为 0、1、...、m – 1。因此，我们从 i ... 阅读更多

在本节中，我们将了解开放寻址方案中的线性探测技术。有一个普通的哈希函数 h´(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数 h(x) 采用普通的哈希函数 h’(x) 并附加一些其他部分以构成一个线性方程。h´(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚i 的值为 | = 0、1、...、m – 1。因此，我们从 i = 0 开始，并增加它，直到我们获得一个空闲空间。因此，最初... 阅读更多