数据结构中的动态手指搜索树
除了手指搜索之外，动态手指搜索数据结构还应该在手指给定的位置执行元素的插入和删除。
手指搜索树定义为B树的变体，它支持O（log d）时间的手指搜索并在O(1)时间进行更新，假设仅保留O(1)个可移动手指。
遍历手指d位置需要O（log d）时间。
手指搜索树（即AVL树，红黑树）构造要么考虑固定数量的手指，要么仅支持摊销后的恒定时间中的更新。
已经创建了支持任意数量的手指并具有最坏情况更新的构造。
支持在最坏的情况下O(1)时间在任意位置更新的搜索树，但仅支持O（log n）时间的搜索树。
支持O（log d）时间搜索以及O（log dn）时间插入和删除的构造。
手指搜索树消耗最坏情况的恒定时间插入和O（log dn）时间删除。
根据对链接的(2,4)-树的级别的节省空间的替代解决方案，允许使用单个手指，这可以通过与(2,4)-树相同的性能成本来进行。在该解决方案中，不需要级别链接和父指针，而是为手指创建了特殊的O（log n）空间数据结构hand，该手指可以有效地遍历手指。
Splay树定义为一类自调整二进制搜索树，支持在摊销O（log n）时间中进行搜索，插入和删除。该张开树可以被实现为有效的手指搜索树。
在给定O(n)初始化成本的情况下，距离八分树中先前访问的距离d的访问的摊销成本为O（log d），其中访问包括搜索，插入和删除。
注意，该语句仅在一个手指的存在下实现，该手指始终指向最后访问的元素。
所有以上提到的构造都可以应用于指针机，其中对元素的唯一允许操作是两个元素的比较。
对于随机访问机器的计算模型(RAM)，开发了具有恒定更新时间和O（log d）搜索时间的手指搜索树。通过将小树结构制成表格即可获得此结果，但仅执行元素比较。
以上是 数据结构中的动态手指搜索树 的全部内容， 来源链接： utcz.com/z/317056.html
