Randomized binary search trees
Randomized binary search trees
复制标题
随机二叉搜索树
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Salvador Roura
中科院分区：
文献类型：
--
作者：
Conrado Martínez;Salvador Roura
本文提出了二叉查找树上的随机化算法，使得：（a）将一组键按任何固定顺序插入到初始空的树中总是产生一棵随机二叉查找树;（B）从随机二叉查找树中删除任何键都产生一棵随机二叉查找树;（c）算法所作的随机选择是基于树的子树的大小;这意味着我们可以支持按秩访问，而无需额外的存储要求或修改数据结构;和（d）任何基本操作的成本，作为访问节点的数量来衡量，与其标准确定性对应物的预期成本相同;因此，所有搜索和更新操作都保证了预期成本O（log n），但现在不考虑对输入分布的任何假设。
In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key from a random binary search tree results in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements or modification of the data structures; and (d) the cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all search and update operations have guaranteed expected cost O(log n), but now irrespective of any assumption on the input distribution.