下图显示了高度受限或深度受限的霍夫曼树。树的深度限制是一个非平凡的问题，大多数现实世界的霍夫曼实现都必须处理这个问题。霍夫曼构造不限制高度或深度。如果限制了，则它不可能是“最优的”。当然，霍夫曼树的最大深度受斐波那契数列限制，但这仍然留下了比所需更大的深度空间。限制霍夫曼树深度的理由是什么？快速的霍夫曼解码器实现查找表。可以实现多个表级别来减轻内存成本，但是非常快速的…… 阅读更多

一个简单的算法：准备n棵初始的霍夫曼树，每棵树都是单个叶子节点。将n棵树放在一个按权重（频率）组织的优先队列中。删除或移除前两棵树（权重最小的两棵树）。组合这两棵树以创建一个新的树，其根与这两棵树作为子节点关联，其权重是两个子树权重的总和。将这棵新树放入优先队列中。重复步骤2-3，直到所有部分霍夫曼树都合并成一棵树为止。这是一个贪婪的…… 阅读更多

霍夫曼编码：霍夫曼编码定义为一种特殊的最佳前缀码，通常用于无损数据压缩。查找或实现此类代码的过程是通过霍夫曼编码进行的，该算法由 David A. Huffman 在麻省理工学院攻读 Sc.D. 期间开发，并发表在 1952 年的论文“一种构造最小冗余码的方法”中。霍夫曼算法的输出可以显示为一个变长代码表，用于编码源符号（例如文件中的字符）。该算法根据估计的概率或……从……创建此表 阅读更多

在虚拟树中，一些边被视为实线，一些被视为虚线。通常的伸展只在实线树中执行。为了在虚拟树中的节点 y 上进行伸展，实现了以下方法。该算法查看树三次，每次查看一次，并对其进行更改。在第一遍中，仅通过在实线树中进行伸展，从节点 y 开始，从 y 到整个树根的路径变为虚线。通过拼接创建此路径为实线。最后在节点 y 上进行伸展现在将创建 y 为树的根。…… 阅读更多

对于给定的森林，我们创建一些给定的边为“虚线”，其余边保持为实线。每个非叶子节点都只与一条指向其子节点的“实线”边关联。所有其他子节点将通过虚线连接。更具体地说，在任何给定的树中，最右边的链接（到其子节点）应保持为实线，而到其其他子节点的所有其他链接都创建为“虚线”。结果，树将被分成一系列实线路径。实线路径的根将连接到其他…… 阅读更多

静态手指定理 - 令 f 被视为称为手指的特定元素。则以下表达式是伸展序列成本的界限 O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j 注意 - |f-i| 表示手指和项目 i 之间项目对称排序中的距离。其中 m 表示对最多具有 n 个节点的树的更新或访问操作的次数。观察到，至少在摊销意义上，在从不超过 n 的树上进行前 m 次操作所花费的时间…… 阅读更多

动态最优性猜想：除了伸展树的已证明性能保证外，还有一个未经证实的猜想引起了极大的兴趣。动态最优性猜想表示此猜想。令任何二叉搜索树算法（例如 B）通过遍历从根到 y 的路径来访问元素 y，成本为 d(y)+1，并且在访问之间可以在树中进行任何旋转，每次旋转的成本为 1。令 B(s) 为 B 执行访问序列 s 的成本。然后，伸展树执行相同访问的成本为 O[n+B(s)]。有…… 阅读更多

自适应归并排序：自适应归并排序执行排序子列表归并排序的合并。但是，初始子列表的大小取决于列表元素之间是否存在排序，而不是具有大小为 1 的子列表。例如，考虑图中的列表。它包含 2 个排序的子列表。子列表 1 包含元素 16、15、14、13。子列表 2 包含元素 9、10、11、12。子列表 1 已排序，但顺序相反。因此，子列表 1 反转如图所示。一旦找到子列表，合并过程就开始了。自适应归并排序开始合并子列表。自适应归并…… 阅读更多

在跳表中，可以从包含元素 b 的节点开始，通过简单地从该点 a 继续搜索来进行元素 a 的手指搜索。请注意，如果 a < b，则搜索向后进行，如果 a > b，则搜索向前进行。向后的情况与跳表中的正常搜索是对称的，但向前的情况实际上更复杂。通常，跳表中的搜索预计会很快，因为列表开头的哨兵被认为是最高的节点。但是，我们的手指可能与…… 阅读更多

确定性搜索树的两种随机化替代方案是随机二叉搜索树、treap 和跳表。treap 和跳表都被定义为优雅的数据结构，其中随机化有助于简单且有效的更新操作。在本节中，我们将解释如何将 treap 和跳表都实现为高效的手指搜索树，而无需更改数据结构。两种数据结构都支持手指搜索，预计消耗 O(log d) 时间，其中期望值是在算法在数据结构构建期间创建的随机选择中获得的。跳表在跳表中，可以…… 阅读更多