论文标题
算术二进制搜索树：匹配模型中的静态最优性
Arithmetic Binary Search Trees: Static Optimality in the Matching Model
论文作者
论文摘要
通过光学开关和可重构网络设计的最新发展，我们研究了匹配模型中的动态二进制搜索树（BST）。在经典的动态BST模型中，链接遍历和基本重新配置（旋转）的成本为$ O（1）$。但是，在匹配模型中，BST由两个光学开关定义（以抽象的方式表示两个匹配），每个开关（或匹配）重新配置成本为$α$，而链接遍历成本仍然为$ O（1）$。 In this work, we propose Arithmetic BST (A-BST), a simple dynamic BST algorithm that is based on dynamic Shannon-Fano-Elias coding, and show that A-BST is statically optimal for sequences of length $Ω(n α\log α)$ where $n$ is the number of nodes (keys) in the tree.
Motivated by recent developments in optical switching and reconfigurable network design, we study dynamic binary search trees (BSTs) in the matching model. In the classical dynamic BST model, the cost of both link traversal and basic reconfiguration (rotation) is $O(1)$. However, in the matching model, the BST is defined by two optical switches (that represent two matchings in an abstract way), and each switch (or matching) reconfiguration cost is $α$ while a link traversal cost is still $O(1)$. In this work, we propose Arithmetic BST (A-BST), a simple dynamic BST algorithm that is based on dynamic Shannon-Fano-Elias coding, and show that A-BST is statically optimal for sequences of length $Ω(n α\log α)$ where $n$ is the number of nodes (keys) in the tree.
