数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究数据结构中的动态手指搜索树
- 动态手指搜索数据结构除了手指搜索之外，还应该在由手指给定的位置执行元素的插入和删除操作。
- 手指搜索树定义为 B 树的一种变体，支持在 O(log d) 时间内进行手指搜索，并在 O(1) 时间内进行更新，假设仅维护 O(1) 个可移动手指。
- 遍历 d 个手指位置需要 O(log d) 时间。
- 手指搜索树（即 AVL 树、红黑树）的构建要么考虑固定数量的手指，要么仅支持摊销常数时间内的更新。
- 已经创建了支持任意数量的手指并在最坏情况下更新的构建方法。
- 一种搜索树，它支持在任意位置以最坏情况 O(1) 时间进行更新，但仅支持在 O(log n) 时间内进行搜索。
- 支持 O(log d) 时间搜索和 O(log d n) 时间插入和删除的构建方法。
- 手指搜索树消耗最坏情况常数时间插入和 O(log d n) 时间删除。
- 根据一种对级别链接 (2,4) 树的空间高效的替代方案，允许一个手指，它可以通过与 (2,4) 树相同的性能成本进行处理。在该方案中，不需要级别链接和父指针，而是为手指创建了一个特殊的 O(log n) 空间数据结构（hand），允许有效地遍历手指。
- 伸展树定义为一类自调整二叉搜索树，支持在摊销 O(log n) 时间内进行搜索、插入和删除。即伸展树可以作为高效的手指搜索树来实现。
- 给定 O(n) 的初始化成本，在伸展树中距离上次访问位置 d 的访问的摊销成本为 O(log d)，其中访问包括搜索、插入和删除。
- 请注意，该语句仅在存在一个手指的情况下实现，该手指始终指向上次访问的元素。
- 所有上述构建方法都可以在指针机上应用，其中在元素上唯一允许的操作是比较两个元素。
- 对于随机访问机计算模型 (RAM)，开发了一种具有常数更新时间和 O(log d) 搜索时间的手指搜索树。此结果是通过制表小型树结构实现的，但仅执行元素的比较。
更新于： 2020年1月7日
296 次浏览
广告