Dynamic weighted ancestors
Dynamic weighted ancestors
复制标题
动态加权祖先
DOI：
10.5555/1283383.1283444
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Moshe Lewenstein
中科院分区：
文献类型：
--
作者：
T. Kopelowitz;Moshe Lewenstein
在加权祖先问题中，对一棵加权树进行预处理（权重在节点上，且随树的深度增加），以支持在从查询节点到根的路径上的前驱查询，这些查询被称为加权祖先查询。
由于加权祖先问题出现在众多应用中，该问题已被研究，并且静态树的解决方案是众所周知的。然而，对于支持节点插入的动态版本的问题是否能得到最优解一直是一个未解决的问题。节点插入是指叶子节点插入或边分裂。
在本文中，我们提出了一种动态加权祖先问题的解决方案，该方案在与动态前驱结构相同的时间界限内支持查询和更新操作。
In the weighted ancestor problem one preprocesses a weighted tree (the weights are on the nodes and increase with tree depth) to support predecessor queries, which are called weighted ancestors queries, on the paths from the query node to the root.
Since, the weighted ancestor problem appears in numerous applications, the problem has been studied and solutions for static trees are well known. However, it has been an open question whether this can be solved optimally for the dynamic version of the problem, where node insertions are supported. Node insertions are leaf insertions or edge splittings.
In this paper we present a solution for the dynamic weighted ancestors problem which supports queries and update operations in the same time bounds as those for dynamic predecessor structures.