腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

算法和应用

专栏作者

44

文章

26965

阅读量

9

订阅数

伸展树的先序和后序

密钥管理服务二叉树

摘要：设T是二叉搜索树。我们证明了关于Splay算法行为的两个结果（Sleator和Tarjan 1985）。我们的第一个结果是通过按照T的预订或T的后序的顺序将密钥插入到空的二进制搜索树中需要线性时间。我们的证据使用了这样一个事实，即预订和预订是模式避免的：即它们不包含分别与（2,3,1）和（3,1,2）顺序同构的子序列。模式避免意味着对项目插入方式的某些限制。我们利用这个结构利用一个简单的潜在函数来计算位于未插入节点的访问路径上的插入节点。我们的方法可以扩展到避免更一般模式的排列。其次，如果T是具有相同键的任何其他二元搜索树，如T 和 T'是权重平衡（Nievergelt和Reingold 1973），然后splaying 的T的预订序列或T的后序列从T'开始线性时间。为了证明这一点，我们证明了平衡搜索树的预订和出版物不会以对称的顺序包含许多大的“跳跃”，并利用动态手指定理来利用这一事实（Cole et al.2000）。我们的两个结果都提供了有利于难以捉摸的“动态最优猜想”的进一步证据。

2019-07-18

4240

从Splay到动态优化的新路径

摘要：考虑在二叉搜索树中执行搜索序列的任务。在每次搜索之后，允许算法以与执行的重构量成比例的成本任意地重构树。执行的成本是搜索所花费的时间和使用重组操作优化这些搜索所花费的时间的总和。这个概念是由Sleator和Tarjan通过计算和猜想在（JACM，1985）中引入的。算法Splay是一个严苛的过程，用于在将搜索到的项目移动到树顶部时执行调整。这种被称为“动态最优性”的猜想是，展开的成本总是在用于执行搜索的最佳算法的恒定因子内。这个猜想一直持续到今天。在这项工作中，我们试图为动态最优性猜想的证明奠定基础。

2019-07-18

7240

用于整数规划的行不变参数化算法

数据处理数据分析二叉树

摘要：对整数规划的固定参数可处理性的长期研究最终表明，具有n个变量的整数程序和具有树深d和最大条目D的约束矩阵在时间g（d，D）poly（n）中是可解的。一些函数g，即，当由树深d和D参数化时，固定参数易处理。但是，约束矩阵的树深度取决于其非零项的位置，因此不反映其几何性质，特别是，在行操作下不是不变的。我们考虑通过名为branch-depth的matroid参数对约束矩阵进行参数化，该参数在行操作下是不变的。我们的主要结果断言，矩阵具有分支深度d和最大条目D的整数程序在时间f（d，D）poly（n）中是可解的。由于每个树深度较小的约束矩阵都具有较小的分支深度，因此我们的结果扩展了上述结果。分支深度的参数化不能被更宽松的分支宽度概念所取代。

2019-07-18

6140

无损优先嵌入

嵌入式二叉树

摘要：给定度量空间（X，d）和（Y，ρ）和（X，d）的排序x1，x2，...，xn，嵌入f：X→Y被认为具有优先级失真α（⋅），如果对于X中的任何对xj，x'的不同点，由f对该对提供的失真最多为α（j）。如果Y是一个赋范空间，如果f（xj）可能仅在其第一个β（j）坐标中具有非零项，则认为嵌入具有优先级维度β（⋅）。

2019-07-18

4890

没有更多了

社区活动

腾讯技术创作狂欢月

“码”上创作 21 天，分 10000 元奖品池！

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态